Thuat Toan RadixSort

Ý tưởng: 

 Thuật giải sắp xếp theo phương pháp cơ số không quan tâm đến việc so sánh giá trị
của các phần tử như các thuật giải trước. RadixSort sử dụng cách thức phân loại các con
số trong dãy và thứ tự phân loại con con số này để tạo ra thứ tự cho các phần tử. Đây là
cách tiếp cận khác so với các phương pháp sắp xếp trước là so sánh các giá trị của các
phần tử. Thuật giải dựa trên ý tưởng chính là sắp xếp từng con số của một dãy các số.

 Để sắp xếp dãy a[1], a[2],..., a[n] giải thuật RadixSort thực hiện như sau:
 Xem mỗi phần tử a[i] trong dãy a[1]...a[n] là một số nguyên có tối đa m chữ số
 Lần lượt phân loại các chữ số theo hàng đơn vị, hàng chục, hàng trăm...Tại mỗi
bước phân loại ta sẽ nối các dãy con từ danh sách đã phân loại theo thứ tự 0 ® 9.
Sau khi phân loại xong ở hàng thứ m cao nhất ta sẽ thu được danh sách các phần
tử được sắp.
Thuật toán :

Bước 1 : k = 0; // k là chữ số phân loại, k = 0 hàng đơn vị, k = 1 hàng chục...
 Bước 2 : // Tạo các dãy chứa phần tử phân loại B[0]...B[9]
Khởi tạo B[0]...B[9] rỗng, chưa chứa phần tử nào, B[i] sẽ chứa các phần tử có chữ
số thứ k là i.
 Bước 3 :
o For i=1 to n do
 Đặt a[i] vào dãy B[j] với j là chữ số thứ k của a[i].
o Nối B[0], B[1],..., B[9] lại theo đúng trình tự thành a.
 Bước 4 :
o k = k +1
o Nếu k < m: Þ Bước 2. // m là số lượng chữ số tối đa của các số
trong mảng
o Ngược lại: Þ Dừng.

 Mảng a[MAX] chứa các phần tử của mảng cần sắp tăng.
 Mảng B[10][MAX] chứa các dãy số được phân tạm thời theo các
con số. Ví dụ B[0] chứa các phần tử có con số ở hàng đơn vị .Khi đó với mỗi dòng của B thì sẽ phân các phần tử có con số ở hàng thứ i (i từ 0 - 9), các giá trị cột j sẽ lần lượt chứa các phần tử có cùng con số ở hàng thứ i.
 Mảng Len[10] chứa số lượng các phần tử của các dòng B[i].  Tại mỗi bước
trước khi phân các phần tử vào mảng B thì các Len[i] được khởi tạo là 0.
 Ví dụ : Cho dãy:



Phân lô theo hàng đơn vị:

12	0701
11	1725
10	0999
9	9170
8	3252
7	4518
6	7009
5	1424
4	0428
3	1239										0999
2	8425						1725			4518	7009
1	7013	9170	0701	3252	7013	1424	8425			0428	1239
CS	A	0	1	2	3	4	5	6	7	8	9
		Các lô B dùng để phân loại

Phân lô theo hàng chục:

12	0999
11	7009
10	1239
9	4518
8	0428
7	1725
6	8425
5	1424
4	7013			0428
3	3252			1725
2	0701	7009	4518	8425
1	9170	0701	7013	1424	1239		3252		9170		0999
CS	A	0	1	2	3	4	5	6	7	8	9

Phân lô theo hàng trăm:

12	0999
11	9170
10	3252
9	1239
8	0428
7	1725
6	8425
5	1424
4	4518
3						0428
2	7009	7013		3252		8425			1725
1	0701	7009	9170	1239		1424	4518		0701		0999
CS	A	0	1	2	3	4	5	6	7	8	9

Phân lô theo hàng ngàn:

12	0999
11	1725
10	0701
9	4518
8	0428
7	8425
6	1424
5	3252
4	1239
3	9170	0999	1725
2	7013	0701	1424						7013
1	7009	0428	1239		3252	4518			7009	8425	9170
CS	A	0	1	2	3	4	5	6	7	8	9

Lấy các phần tử từ các lô B0, B1, ., B9 nối lại thành a:

12	9170
11	8425
10	7013
9	7009
8	4518
7	3252
6	1725
5	1424
4	1239
3	0999
2	0701
1	0428
CS	A	0	1	2	3	4	5	6	7	8	9

Cài đặt:

void RadixSort(long a[], int n)

{

int i, j, d;

int h = 10; // biến để lấy các con số, bắt đầu từ hàng đơn vị

long B[10][MAX]; // mảng hai chiều chứa các phần tử phân lô

int Len[10]; // kích thước của từng mảng B[i]

// MAXDIGIT là số con số tối đa của các phần tử a[i]

for(d = 0; d < MAXDIGIT; d++)

{

// khởi tạo kích thước các dãy B[i] là 0

for( i = 0; i < 10; i++)

Len[i] = 0;

// thực hiện phân lô các phần tử theo con số hàng thứ d tính từ cuối

for(i = 0; i < n; i++) // duyệt qua tất cả các phần tử của mảng

{

digit = (a[i] % h) / (h/ 10); // lấy con số theo hàng h

// đưa vào dãy (lô) B[digit] ở cột Len[digit]

B[digit][Len[digit]++] = a[i];

}// end for i

// thực hiện nối lại tuần tự từ B[0] – đến B[9] vào mảng a[] ban đầu

num = 0; // chỉ số bắt đầu cho mảng a[]

for(i = 0; i < 10; i++) // duyệt qua các dãy từ B[0] – đến B[9]

{

// lấy từng phần tử của từng dãy B[i]

for(j =0; j < Len[i]; j++)

a[num++] = B[i][j];

}// end for i

h *= 10; // qua hàng kế tiếp.

}// end for d

}// end RadixSort