RADIX SORT

RADIX SORT

การเรียงแบบนี้เราจะใช้แต่ละตำแหน่งตัวเลขของแต่ละคีย์ โดยเริ่มตั้งแต่ตำแหน่งนัยสำคัญน้อยที่สุด (least significant digit) การเรียงก็ง่ายมาก ขั้นแรกให้เตรียมถัง 10 ถัง ("ถัง"ในที่นี้อาจเป็นคิวหรืออาร์เรย์ก็ได้) แล้วในแต่ละเที่ยวของการเรียงจะโยนค่าคีย์ไปเข้าแต่ละถังตามค่าตัวเลขในแต่ละตำแหน่ง)

สมมติให้ชุดคีย์ที่จะเรียงมีดังนี้
156,425,679,128,420,067,772,895,835

การเรียงเที่ยวที่ 1 การจ่ายค่าคีย์ไปตามถังต่าง ๆ ตามค่าตัวเลขที่ตำแหน่งขวาสุด
156 425 679 128 420 067 772 895 825



ถังที่ 0 420
ถังที่ 1
ถังที่ 2 772
ถังที่ 3
ถังที่ 4
ถังที่ 5 425 895 825
ถังที่ 6 156
ถังที่ 7 067
ถังที่ 8 128
ถังที่ 9 679

เมื่ออ่านค่าในแต่ละถังออกมาตามลำดับจะได้ค่าต่าง ๆ ดังนี้
420 772 425 895 825 156 067 128 679

การเรียงเที่ยวที่ 2
420 772 425 895 825 156 067 128 679

ถังที่ 0
ถังที่ 1
ถังที่ 2 420 425 825 128
ถังที่ 3
ถังที่ 4
ถังที่ 5 156
ถังที่ 6 067
ถังที่ 7 772 679
ถังที่ 8
ถังที่ 9 895

เมื่ออ่านค่าต่าง ๆ ในแต่ละถังออกมาตามลำดับจะได้
420 425 825 128 156 067 772 679 895

การเรียงเที่ยวที่ 3 ในเที่ยวนี้เราจะพิจารณาตำแหน่งซ้ายสุด
420 425 825 128 156 067 772 679 895

ถังที่ 0 067
ถังที่ 1 128 156
ถังที่ 2
ถังที่ 3
ถังที่ 4 420 425
ถังที่ 5
ถังที่ 6 679
ถังที่ 7 772
ถังที่ 8 825 895
ถังที่ 9

เมื่ออ่านค่าต่างๆ ในแต่ละถังออกมาจะได้ชุดคีย์ที่เรียงแล้วเป็นดังนี้
067 128 156 420 425 679 772 825 895



* เครติด [Only admins are allowed to see this link]