Home » , » Thuat Toan RadixSort

Thuat Toan RadixSort

Written By 1 on Chủ Nhật, 20 tháng 5, 2012 | 18:07

Ý 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

0 nhận xét:

Đăng nhận xét