Radix Sort

Thuật toán Radix Sort

1.   Ý tưởng

–        Ý tưởng của thuật toán này cũng tương tự như quick sort. trong trường hợp đặc biệt mảng cần sắp xếp là các số nguyên, ta biểu diễn các phần tử của mảng ở dạng nhị phân rồi tiến hành chia mảng thành 2 phần dựa trên các bít nhị phân của nó: phần đầu gồm những số có bit cao nhất băng 0, phần còn lại có bít cao nhất bằng 1 (ta gọi bit này là bit z). dễ nhận thấy rằng tất cả các phần tử của phần đầu sẽ nhỏ hơn các phần tử ở phần cuối.
sau đó quá trình lại được tiếp tục (đệ quy) bằng cách sắp xếp tương tự đối với từng phần, tất nhiên bit để căn cứ so sánh lúc này sẽ là bit z-1 (z là bit cao nhất). cứ như vậy đến khi sắp xếp căn cứ vào bit 0 thì quá trình sắp xếp hoàn tất và ta có mảng được sắp xếp.

–        Sắp xếp theo cơ số (radix sort) dựa trên tính chất "số" của các khóa. Trong giải thuật sắp xếp theo cơ số, ta không chỉ so sánh giá trị của các khóa, mà so sánh các thành phần của khóa. Giả sử các khóa là các số biểu diễn theo hệ ghi số cơ số M. Khi đó sắp xếp theo cơ số sẽ so sánh từng k

–        Chúng ta mô tả cách sắp này khi cơ số M=10. Giả sử phải sắp các hồ sơ đánh số bởi 3 chữ số thập phân. Đầu tiên ta chia các hồ sơ vào các đống có cùng chữ số hàng trăm (đồng thới xếp các đống theo thứ tự của chữ số hàng trăm), trong mỗi đống con lại phân chia theo chữ số hàng chục, cuối cùng trong mỗi đống có cùng chữ số hàng trăm và hàng chục, sắp xếp theo thứ tự của chữ số hàng đơn vị.

–        Trong máy tính, đương nhiên việc sắp xếp theo cơ số nhị phân (cơ số 2) hoặc cơ số là lũy thừa của 2 là thuận lợi nhất. Trong trường hợp cơ số 2, việc phân hoạch tương tự như phân hoạch trong Quick Sort, chỉ khác ở chỗ cách chọn phần tử chốt.

2.   Mô tả thuật toán bằng mã giả

for int i = d; i>= 1; i--        //d là các phần tử của mảng A

for int 1= 1;i>= n; i++

                       insert(B[A[i]], A[i])

                        remove(A,i)

            for int i=0; i<=m-1; i++    // Một mảng n phần tử số A có miền giá trị [0,m-1]

                        while (B[i] <> empty)

                                    insert(A, i)

            return array A

3.   Mã nguồn C++

void *radixsort(int l, int r, int b)

/* sắp xếp đoạn [l,r] dựa theo bit b */

{
int i, j;
if (l >= r) return;
i = l; j = r;
do {
while (((i < j) && ((a[i]>>b) & 1)) == 0) ++i; /* tìm phần tử có bit b = 1 từ đầu đoạn */
while (((i < j) && ((a[j]>>b) & 1)) == 1) --j; /* tìm phần tử có bit b = 0 từ cuối đoạn */
temp = a[i]; /* đổi chỗ chúng */
a[i] = a[j];
a[j] = temp;
} while (i != j); /* đến khi phân đoạn xong */
if (((a[j] >> b) & 1) == 0) ++j; /* j là điểm bắt đầu đoạn có bit b = 1 */
if (b > 0) { /* chưa xét tới bit cuối cùng */
radixsort(l, j-1, b-1);
radixsort(j, r, b-1);
}