Sắp xếp theo cơ số

Trong khoa học máy tính, thuật toán sắp xếp theo cơ số là một thuật toán sắp xếp không so sánh. Thuật toán này được thực hiện dựa trên ý tưởng nếu một dãy số đã được sắp xếp hoàn chỉnh thì từng chữ số cũng sẽ được sắp xếp hoàn chỉnh dựa trên giá trị của các chữ số đó. Thuật toán này yêu cầu dãy cần được sắp xếp có thể so sánh thứ tự các vị trí vì thế sắp xếp theo cơ số không giới hạn ở tập số nguyên (ta có thể dễ dàng đưa dạng xâu về cơ số nhị phân).

Sắp xếp theo cơ số nhị phân sửa

Trong bài này chỉ giới thiệu giải thuât Sắp xếp theo cơ số nhị phân. Giả sử chúng ta cần sắp xếp danh sách $a[1..n]$ , trong đó các phần tử là các số tự nhiên biểu diễn bằng 31 bit. Các bit được đánh số thứ tự từ phải sang trái bằng các số 0..30. Để đọc được bit thứ k của số tự nhiên x cần có một hàm GetBit(x,k). Hàm này có thể có sẵn trong ngôn ngữ lập trình, trong trường hợp không có sẵn nó có thể viết nhờ toán tử LShift (dịch trái) và toán tử AndBit. (Trong nhiều ngôn ngữ lập trình, từ khóa của toán tử AndBit trùng từ khóa với toán tử and theo nghĩa toán tử logic).

Function GetBit(Int: x,k) 
Return LShift(x,k) AndBit 1.

Để sắp xếp (phân chia) danh sách theo bit thứ k của danh sách, ta tìm phần tử đầu tiên bên trái của danh sách có bit thứ k là 1 và phần tử đầu tiên bên phải có bit thứ k là 0 rồi đổi chỗ (Swap) cho nhau. Quá trình tiếp tục cho đến khi con trỏ hai đầu gặp nhau. Khi đó vị trí của hai con trỏ gặp nhau chia danh sách thành hai danh sách con: đanh sách đầu chứa các phần tử có bit thứ k bằng 0, danh sách sau chứa các phần tử có bit thứ k bằng 1.
Bằng lời giải đệ quy, tiếp tục phân chia các danh sách con này theo bit thứ k-1.. cho đến bit thứ 0.

Mã giả sửa

Procedure RadixSort(list: a, int:s,e, k){

 Var Int i:=s,j:=e
   While i<j and k>=0 {  
   While GetBit(a[i],k)=0 do i:=i+1 
   While GetBit(a[j],k)=1 do j:=j-1
      Swap(a[i],a[j])         
  }
  If GetBit(a[i],k)=0 then i:=i+1
  }
  RadixSort(a,s,j,k-1)
  RadixSort(a,j+1,s,k-1)
  }

Lời gọi RadixSort(a,1,n,30) sẽ sắp xếp toàn bộ danh sách a[1..n].

Ví dụ sửa

Xét ví dụ sau đây.

$a=(2,6,3,7,4,5,1)$

Các số trong danh sách đều có thể biểu diễn bằng số nhị phân 3 bit. Bảng sau đây cho biểu diễn nhị phân của từng số trong danh sách

2	6	3	7	4	5	1
010	110	011	111	100	101	001

Với k = 2 việc phân chia theo bit thứ 2 tiến hành đổi chỗ a[2]=6 cho a[7]=1, và phân chia danh sách a thành hai danh sách a[1..3] và a[4..7]

2	1	3	---	7	4	5	6
010	001	011	---	111	100	101	110

Sau đó thuật toán đưa danh sách a[4..7] vào stack và tiến hành phân chia danh sách a[1..3] theo bit thứ k = 1, bằng cách đổi chỗ a[1] = 2 cho a[2] = 1,thành a[1..1] và a[2..3]

1	--	2	3	---	7	4	5	6
001	--	010	011	---	111	100	101	110

Tiếp theo là phân chia danh sách a[2..3] theo bit thứ 0 thành a[2..2] và a[3..3]

1	-	2	-	3	---	7	4	5	6
001	-	010	-	011	---	111	100	101	110

Đến đây việc sắp xếp danh sách a[1..3] hoàn thành. Thuật toán tiếp lấy a[4..7] từ trong stack ra để sắp xếp theo cách phân chia như trên, lần lượt là quá trình phân chia như sau:

1	--	2	-	3	---	5	4	--	7	6
001	--	010	-	011	---	101	100	--	111	110

1	--	2	-	3	---	4	-	5	--	6	-	7
001	--	010	-	011	---	100	-	101	--	110	-	111

Sắp xếp theo cơ số

Mục lục