Radix Sort

RADIX SORT Thành viên nhóm THQL 1-K32: 2. Nguyễn Huy Cường 3. Nguyễn Văn Đức 4. Lê Duy Tiến 5. Phạm Hồng Tín

Giới Thiệu 1. 2. 3.

MSD (Most Significan Digit) LSD (Least Significan Digit) Three-way Radix Quicksort

Ý tư ởn g t huật t oá n 



Sắp xếp dựa trên cơ số (bit, nhóm bit hoặc kí tự) Chuyển các giá trị trong mảng về hệ nhị phân

1. MSD a. Ý tưở ng thậ t to án : + Xét bit đầu tiên bên trái + Chia ra thành 2 mảng con :  Mảng con bên trái chứa giá trị 0  Mảng con bên phải chứa giá trị 1 + Xét tiếp bit thứ hai trên từng mảng con và cũng thực hiện chia nhỏ ra thành các mảng con bên trái và bên phải + Tiếp tục cho đến bit cuối cùng

Ví dụ : Hệ thập phân: Hệ nhị phân : Bước 1 : Bước 2 : Bước 3 :

1 001 0 01 00 1 | 001 | 1

3 011 0 11 01 1 010 | 2

5 7 6 101 111 110 0 10 | 1 01 1 11 01 0 | 10 1 | 11 1 011 | 101 | 110 | 3 5 6

2 010 1 10 11 0 111 7

b.C ài đặ t : Cô ng cụ h ỗ t rợ :  Phép Dịch bit (>>,<<)  Phép And bit (&) Ph ươ ng Phá p : + Lấy ra bit đầu tiên bên trái của tất cả phần tử trong mảng + Cho i=l . j=r + a[i]=0 thì tăng i lên 1,a[i]=1 thì dừng + a[j]=1 thì giảm j xuống 1,a[j]=0 thì dừng + Nếu i=j thì dừng nếu không thì đổi chỗ vị trí 2 phần tử. + Xét tiếp tới bit cuối cùng

Code static void radixsort(int[] a, int l, int r, int b) { int i = l, j = r; if (l >= r) return; while(true) { while ((i < j) && ((a[i] >> b) & 1) == 0) ++i; while ((i < j) && ((a[j] >> b) & 1) == 1) --j; if (i >= j) break; exch(a,i,j); } if (((a[j] >> b) & 1) == 0) ++j; if (b > 0) { radixsort(a, l, j - 1, b - 1); radixsort(a, j, r, b - 1); } }

c.Đ ộ phứ c t ạp  Sắp xếp mảng n ptử theo z bit ,độ phức tạp trung bình của MSD là O(n.min(n,log2n)).Trong trường hợp xấu nhất O(n.z)

2. LSD a. Ý tưởng thu ật toá n :  

     



Sắp xếp theo cơ số từ nhỏ đến lớn. VD: Sắp xếp mảng số thập phân theo hàng đơn vị trước ,rồi tới hàng chục ,hàng trăm…. Cho danh sách : 122 , 289 , 1110 , 2 B1: 1110 , 122 , 2 , 289 B2: 02 , 1110 , 122 , 289 B3: 002 , 1110 , 122 , 289 B4: 0002 , 01 22 , 0289 , 111 0 Sau B1 các ptử trong mảng sẽ theo thứ tự 1 chữ số ngoài cùng bên phải. Sau B2 các ptử trong mảng sẽ theo thứ tự 2 chữ số ngoài cùng bên phải.

b. Cài đặ t : Phươ ng Pháp :  



Chia các phần tử thành các nhóm 4 bit. Sắp xếp mảng theo các nhóm 4 bit đi từ phải sang trái. Tiếp tục sắp xếp theo nhóm 4 bit kế tiếp từ phải qua trái , các sắp xếp tiếp theo dựa trên mảng số được sắp xếp ở bước trước đó.



122



289



1110

0 7 10 0000|0111|1010 1 2 1 0001|0010|0001 4 5 6 0100|0101|0110 0



2

0

2

0000|0000|0010



B1: + Xét nhóm 4 bit đầu tiên bên phải + Đổi ra số thập phân tương ứng

122  10 289  1 1110  6 2 2

1  2  6  10 

289 2 1110 122



B2: + Xét nhóm 4 bit tiếp theo + Đổi ra số thập phân tương ứng

289  2 2 0 1110  5 122  7

0 2 5 7

   

2 289 1110 122



B3: + Xét nhóm 4 bit tiếp theo (cuối cùng) + Đổi ra số thập phân tương ứng

2 0 289  1 1110  4 122  0

0 0 1 4

   

2 122 289 1110

Code static void RadixSort(int[] a) { int[] t = new int[a.Length]; int r = 4; int b = 32; int[] count = new int[1 << r]; int[] pref = new int[1 << r]; int groups = (int)Math.Ceiling((double)b / (double)r); // mask =15,nhi phan la 1111 int mask = (1 << r) - 1;

for (int c = 1, shift = 0; c <= groups; c++, shift += r) { for (int j = 0; j < count.Length; j++) count[j] = 0; for (int i = 0; i < a.Length; i++) count[(a[i] >> shift) & mask]++; pref[0] = 0; for (int i = 1; i < count.Length; i++) pref[i] = pref[i - 1] + count[i - 1]; for (int i = 0; i < a.Length; i++) t[pref[(a[i] >> shift) & mask]++] = a[i]; t.CopyTo(a, 0); }

c.Đ ộ phứ c t ạp 

Thời gian để sắp xếp n ptử với w byte là n.w,do đó thuật toán có độ phức tạp O(n.w) bất kể dữ liệu đầu vào.

Three-Way Quick Sort a. Ý tưởng thu ật toá n : Tương tự Quick Sort nhưng sẽ chia mảng thành 3 phần: +Mảng con trái : gồm các ptử nhỏ hơn khóa +Mảng con giữa : gồm các ptử bằng khóa +Mảng con phải : gồm các ptử lớn hơn khóa

    

Chọn v=a[r] làm khóa để phân đoạn. Dùng quick sort chia thành 2 mảng con. Mảng con trái:đưa các ptử bằng khóa ra đầu dãy Mảng con phải:đưa các ptử bằng khóa ra cuối dãy. Sau đó đưa khóa và các ptử bằng nó vào đúng vị trí trong dãy.

Code static void quicksort(int[] a, int l, int r) { if (r <= l) return; int v = a[r]; int i = l - 1, j = r, p = l - 1, q = r, k; for (; ; ) { while (less(a[++i], v)) ; while (less(v, a[--j])) if (j == l) break; if (i >= j) break; exch(a, i, j); if (equal(a[i], v)) { p++; exch(a, p, i); } if (equal(a[j],v)) { q--; exch(a, q, j); } } exch(a, i, r); j = i - 1; i = i + 1; for (k = l; k <= p; k++, j--) exch(a, k, j); for (k = r - 1; k >= q; k--, i++) exch(a, k, i); quicksort(a, l, j); quicksort(a, i, r); }

3.Three-way radix quicksort Ý tư ởn g th uậ t to án : 

 





Sắp xếp danh sách chứa các ptử kiểu chuỗi theo từng ký tự ttương ứng.(Sắp xếp danh sách các tên). Chọn khóa là ký tự đầu tiên bên trái của a[r] Dùng giải thuật 3 way quick sort sắp xếp theo ký tự đầu tiên bên trái. Gọi đệ quy cho màng con trái và phải theo ký tự đầu tiên của khóa của mỗi mảng. Gọi đệ quy cho mảng con giữa theo ký tự thú 2 của khóa.

 static bool less(String s, String t, int d) { if (t.Length <= d) return false; if (s.Length <= d) return true; return s[d] < t[d]; } Hàm less xét s[d] có nhỏ hơn t[d] hay không. Nếu độ dài t<=d  không tồn tại t[d] false Nếu độ dài s<=d không tồn tại s[d] true Nếu độ dài 2 chuỗi lớn hơn d thì trả về KQ phép so sánh s[d]
Code

static void StrSort(String[] a, int l, int r, int d) { if (r <= l) return; String v = a[r]; int i = l - 1, j = r, p = l - 1, q = r, k; while (true) { while (less(a[++i], v, d)) ; while (less(v, a[--j], d)) if (j == l) break; if (i >= j) break; exch(a, i, j); if (equal(a[i], v, d)) exch(a, ++p, i); if (equal(v, a[j], d)) exch(a, --q, j); }

if (p == q) if (v.Length > d) StrSort(a, l, r, d + 1); if (p == q) return; if (less(a[i], v, d)) i++; for (k = l; k <= p; k++, j--) exch(a, k, j); for (k = r; k >= q; k--, i++) exch(a, k, i); StrSort(a, l, j, d); if (v.Length >= d) StrSort(a, j + 1, i - 1, d + 1); StrSort(a, i, r, d); }

c.Đ ộ phứ c t ạp 

3-way radix sort trung bình sử dụng 2N.lnN phép so sánh để sắp xếp mảng có N ptử.

So sánh thời gian thực hiện

MS D và LSD sử dụn g ng ẫu nhi ên cá c số từ 1 100.000.000

Thr ee-w ay sử dụng các chu ỗi ngẫu nh iên từ 1 32 ký tự. Cấu h ìn h má y thực hi ện: CPU d uo core 2G hz , RAM 2 Ghz , ngô n ng ữ lập trì nh C# 2005 Số ptử

Thuật toán

1.000.000 5.000.000 10.000.000 100.000.000

MSD 1s 3.2s 5.4s 57s

LSD 0.97s 2.5s 3s 23s

Three-Way 4.7s 27s 56s Báo lỗi không đủ bộ nhớ.