際際滷

際際滷Share a Scribd company logo

Bai4 binsort

H畛 L畛i
H畛 L畛i
1 of 28
Download to read offline
C畉u tr炭c d畛 li畛u v Thu畉t gi畉i S畉p x畉p Bin Sorts
Bi 2- C叩c i畛m tr畛ng y畉u Quicksort S畛 d畛ng t畛t cho h畉u h畉t c叩c h畛 th畛ng, ( k畛 c畉 tr動畛ng h畛p h畛 th畛ng c坦 th畛i gian th畛c hi畛n kh担ng b畛 rng bu畛c) Heap Sort Ch畉m h董n quick sort, nh動ng b畉o 畉m O(n log n) D湛ng cho c叩c h畛 th畛ng th畛i gian th畛c (nh畛ng h畛 th畛ng b畛 ph棚 ph叩n v畛 th畛i gian th畛c hi畛n)
S畉p x畉p (Sorting) B但y gi畛 ch炭ng ta 達 bi畉t m畛t vi thu畉t to叩n s畉p x畉p sau: Selection O(n2) Insertion O(n2) Bubble O(n2) Heap O(n log n) B畉o 畉m Quick O(n log n) Th畛i gian th畛c hi畛n nhanh nh畉t! Li畛u ch炭ng ta c坦 th畛 lm t畛t h董n?
S畉p x畉p T畛t h董n O(n log n) ? N畉u t畉t c畉 ch炭ng ta bi畉t v畛 tr畉t t畛 s畉p x畉p c畛a c叩c kh坦a? Kh担ng! Tuy nhi棚n, N畉u ch炭ng ta t鱈nh to叩n 動畛c m畛i 畛a ch畛 c畛a t畛ng kh坦a (th畛i gian l m畛t h畉ng s畛) th狸 Thu畉t to叩n bin sort s畉 cung c畉p hi畛u su畉t t畛t h董n.
S畉p x畉p - Bin Sort Gi畉 thi畉t T畉t c畉 c叩c kh坦a n畉m trong m畛t mi畛n gi叩 tr畛 nh畛 v x叩c 畛nh V鱈 d畛 C叩c s畛 nguy棚n thu畛c 0-99 C叩c k箪 t畛 thu畛c A-z, 0-9 t nh畉t, c坦 m畛t s畛 (ch畛 s畛) 畛ng v畛i m畛i gi叩 tr畛 c畛a kh坦a Bin sort C畉p m畛t t炭i (bin) 畛 ch畛a m畛i gi叩 tr畛 c畛a kh坦a Th動畛ng l t畛ng ph畉n t畛 trong d達y s畛 V畛i m畛i s畛, Tr鱈ch ch畛n kh坦a T鱈nh to叩n s畛 th畛 t畛 c畛a t炭i t動董ng 畛ng 畛ng n坦 畉t n坦 vo trong t炭i K畉t th炭c!
S畉p x畉p - Bin Sort: Ph但n t鱈ch T畉t c畉 c叩c kh坦a 畛u n畉m trong m畛t mi畛n gi叩 tr畛 nh畛 v x叩c 畛nh. C坦 m gi叩 tr畛 kh坦a ti畛m nng t nh畉t, c坦 m畛t gi叩 tr畛 s畛 畛ng v畛i m畛i kh坦a Bin sort C畉p ph叩t m畛t t炭i (bin) cho m畛i gi叩 tr畛 c畛a kh坦a O(m) Th動畛ng l t畛ng ph畉n t畛 trong m畉ng V畛i t畛ng gi叩 tr畛 s畛, n l畉n Tr鱈ch ch畛n kh坦a O(1) T鱈nh to叩n s畛 th畛 t畛 c畛a t炭i t動董ng 畛ng O(1) G叩n n坦 vo trong t炭i O(1) x n O(n) K畉t th炭c! O(n) + O(m) = O(n+m) = O(n) if n >> m Tr畉ng th叩i kh坦a
S畉p x畉p - Bin Sort: Caveat Mi畛n x叩c 畛nh c畛a kh坦a T畉t c畉 c叩c kh坦a 畛u n畉m trong m畛t o畉n nh畛 v x叩c 畛nh C坦 m gi叩 tr畛 kh坦a ti畛m nng N畉u i畛u ki畛n ny kh担ng th鱈ch h畛p, VD: m >> n, th狸 bin sort l O(m) V鱈 d畛 Kh坦a l m畛t s畛 nguy棚n 32-bit, m = 232 R探 rng, kh担ng c坦 c叩ch no 畛 s畉p x畉p 鱈t nh畉t 1000 s畛 nguy棚n. H董n n畛a, ch炭ng t担i kh担ng 畛 kh担ng gian cho c叩c t炭i (bin)! Bin sort 叩nh 畛i kh担ng gian cho t畛c 畛!
Sorting - Bin Sort v畛i c叩c b畉n sao C坦 鱈t nh畉t m畛t mi畛n nh畛 畛ng v畛i m畛i gi叩 tr畛 c畛a kh坦a Bin sort C畉p ph叩t m畛t bin cho m畛i gi叩 tr畛 c畛a kh坦a O(m) Th動畛ng l m畛t ph畉n t畛 trong m畛t m畉ng M畉ng c畛a c叩c danh s叩ch ph畉n t畛 V畛i m畛i s畛 (ch畛 s畛 - item), n l畉n Tr鱈ch ch畛n kh坦a O(1) T鱈nh to叩n s畛 th畛 t畛 t炭i (bin) t動董ng 畛ng O(1) B畛 xung n坦 vo danh s叩ch O(1) x n O(n) Gh辿p danh s叩ch O(m) K畉t th炭c! O(n) + O(m) = O(n+m) = O(n) if n >> m N畛i l畛ng?
Sorting T畛ng qu叩t c畛a Bin Sort Radix sort Bin sort trong c叩c giai o畉n V鱈 d畛 Giai o畉n 1 S畉p x畉p d畛a vo s畛 c坦 箪 ngh挑a t畛i thi畛u 36 9 0 25 1 49 64 16 81 4 0 1 2 3 4 5 6 7 8 9 0 1 81 64 4 25 36 16 9 49
Sorting - Generalised Bin Sort Radix sort - Bin sort trong c叩c giai o畉n Giai o畉n 1 S畉p x畉p d畛a vo s畛 c坦 箪 ngh挑a t畛i thi畛u Giai o畉n 2 S畉p x畉p d畛a vo ph畉n l畛n s畛 c坦 箪 ngh挑a 0 1 2 3 4 5 6 7 8 9 0 1 81 64 4 25 36 16 9 49 0 1 2 3 4 5 6 7 8 9 0
Sorting - Generalised Bin Sort Radix sort - Bin sort trong c叩c giai o畉n Giai o畉n 1 S畉p x畉p d畛a vo s畛 c坦 箪 ngh挑a t畛i thi畛u Giai o畉n 2 S畉p x畉p d畛a vo ph畉n l畛n s畛 c坦 箪 ngh挑a 0 1 2 3 4 5 6 7 8 9 0 1 81 64 4 25 36 16 9 49 0 1 2 3 4 5 6 7 8 9 0 1 C畉n th畉n khi b畛 Xung sau khi 達 t畛n t畉i c叩c s畛 trong Bin!
Sorting - Generalised Bin Sort Radix sort - Bin sort trong c叩c giai o畉n Giai o畉n 1 S畉p x畉p d畛a vo s畛 c坦 箪 ngh挑a t畛i thi畛u Giai o畉n 2 S畉p x畉p d畛a vo ph畉n l畛n s畛 c坦 箪 ngh挑a 0 1 2 3 4 5 6 7 8 9 0 1 81 64 4 25 36 16 9 49 0 1 2 3 4 5 6 7 8 9 0 1 81
Sorting - Generalised Bin Sort Radix sort - Bin sort trong c叩c giai o畉n Giai o畉n 1 S畉p x畉p d畛a vo s畛 c坦 箪 ngh挑a t畛i thi畛u Giai o畉n 2 S畉p x畉p d畛a vo ph畉n l畛n s畛 c坦 箪 ngh挑a 0 1 2 3 4 5 6 7 8 9 0 1 81 64 4 25 36 16 9 49 0 1 2 3 4 5 6 7 8 9 0 1 8164
Sorting T畛ng qu叩t c畛a Bin Sort Radix sort - Bin sort trong c叩c giai o畉n Giai o畉n 1 S畉p x畉p d畛a vo s畛 c坦 箪 ngh挑a t畛i thi畛u Giai o畉n 2 S畉p x畉p d畛a vo ph畉n l畛n s畛 c坦 箪 ngh挑a 0 1 2 3 4 5 6 7 8 9 0 1 81 64 4 25 36 16 9 49 0 1 2 3 4 5 6 7 8 9 0 1 4 8164
1 2 3 4 5 6 7 8 9 816425 3616 49 Sorting - Generalised Bin Sort Radix sort -Bin sort trong c叩c giai o畉n Giai o畉n 1 S畉p x畉p d畛a vo s畛 c坦 箪 ngh挑a t畛i thi畛u Giai o畉n 2 S畉p x畉p d畛a vo ph畉n l畛n s畛 c坦 箪 ngh挑a 0 1 2 3 4 5 6 7 8 9 0 1 81 64 4 25 36 16 9 49 0 0 1 4 9 Ch炭 箪 r畉ng: Bin 0 ph畉i th畛c s畛 l畛n
1 2 3 4 5 6 7 8 9 816425 3616 49 Sorting - Generalised Bin Sort Radix sort - Bin sort trong c叩c giai o畉n Giai o畉n 1 S畉p x畉p d畛a vo s畛 c坦 箪 ngh挑a t畛i thi畛u Giai o畉n 2 S畉p x畉p d畛a vo ph畉n l畛n s畛 c坦 箪 ngh挑a 0 1 2 3 4 5 6 7 8 9 0 1 81 64 4 25 36 16 9 49 0 0 1 4 9 Kh担ng gian c畉n thi畉t cho m畛i giai o畉n l bao nhi棚u? n items m bins
Sorting T畛ng qu叩t c畛a Bin Sort Radix sort Ph但n t鱈ch Giai o畉n 1 S畉p x畉p d畛a vo s畛 c坦 箪 ngh挑a t畛i thi畛u T畉o m bins O(m) C畉p ph叩t n items O(n) Giai o畉n 2 T畉o m bins O(m) C畉p ph叩t n items O(n) Cu畛i c湛ng Li棚n k畉t m bins O(m) T畉t c畉 c叩c b動畛c th畛c hi畛n tu畉n t畛, v狸 th畉 b畛 xung T畛ng O(3m+2n) O(m+n) O(n) cho m<<n
Sorting - Radix Sort Ph但n t鱈ch Radix sort T畛ng qu叩t V畛 c董 b畉n: m畛i giai o畉n c坦 th畛 ph湛 h畛p v畛i c叩c ki畛u d畛 li畛u kh叩c nhau. C叩c s畛 nguy棚n C叩c gi叩 tr畛 c董 s畛 10, 16, 100, C叩c thnh ph畉n d畛 li畛u kh担ng c湛ng ki畛u d畛 li畛u V畉n l O(n) n畉u n >> si v畛i m畛i i struct date { int day; /* 1 .. 31 */ int month; /* 1 .. 12 */ int year; /* 0 .. 99 */ } G 1 - s1=31 bins G 2 - s2=12 bins G 3 - s3=100 bins
Radix Sort - Analysis Generalised Radix Sort Algorithm radixsort( A, n ) { for(i=0;i<k;i++) { for(j=0;j<s[i];j++) bin[j] = EMPTY; for(j=0;j<n;j++) { move A[i] to the end of bin[A[i]->fi] } for(j=0;j<s[i];j++) concat bin[j] onto the end of A; } } O( si ) O( n ) O( si ) For each of k radices
Radix Sort - Analysis Generalised Radix Sort Algorithm radixsort( A, n ) { for(i=0;i<k;i++) { for(j=0;j<s[i];j++) bin[j] = EMPTY; for(j=0;j<n;j++) { move A[i] to the end of bin[A[i]->fi] } for(j=0;j<s[i];j++) concat bin[j] onto the end of A; } } O( si ) O( n ) O( si ) Clear the si bins for the ith radix
Radix Sort - Analysis Generalised Radix Sort Algorithm radixsort( A, n ) { for(i=0;i<k;i++) { for(j=0;j<s[i];j++) bin[j] = EMPTY; for(j=0;j<n;j++) { move A[i] to the end of bin[A[i]->fi] } for(j=0;j<s[i];j++) concat bin[j] onto the end of A; } } O( si ) O( n ) O( si ) Move element A[i] to the end of the bin addressed by the ith field of A[i]
Radix Sort - Analysis Generalised Radix Sort Algorithm radixsort( A, n ) { for(i=0;i<k;i++) { for(j=0;j<s[i];j++) bin[j] = EMPTY; for(j=0;j<n;j++) { move A[i] to the end of bin[A[i]->fi] } for(j=0;j<s[i];j++) concat bin[j] onto the end of A; } } O( si ) O( n ) O( si ) Concatenate si bins into one list again
Radix Sort Ph但n t鱈ch Total k v嘆ng l畉p, 2si + n cho m畛i v嘆ng Nh動 v畉y k l m畛t h畉ng s畛 T畛ng qu叩t, N畉u keys thu畛c (0, bk-1) Keys l nh畛ng s畛 k-digit base-b si = b for all k 畛 ph畛c t畉p O(n+kb) = O(n) O( si + n ) = O(kn + si ) = O(n + si ) i=1 i=1 i=1 k kk
Radix Sort Ph但n t鱈ch ? B畉t c畛 t畉p key no c滴ng c坦 th畛 叩nh x畉 v畛 (0, bk-1) ! Nh動 v畉y ch炭ng ta th動畛ng xuy棚n 畉t 畛 ph畛c t畉p s畉p x畉p O(n)? N畉u k l m畛t h畉ng s畛, 炭ng nh動 v畉y.
Radix Sort Ph但n t鱈ch Nh動ng, n畉u k 動畛c ph辿p tng c湛ng v畛i n Vd n坦 l畉y logbn c叩c s畛 c坦 b ch畛 s畛 c董 s畛 畛 bi畛u di畛n n Nh動 v畉y ch炭ng ta c坦: k = log n, si = 2 (say) S畉p x畉p Radix kh担ng t畛t h董n so v畛i quicksort O( 2 + n ) = O(n log n + 2 ) = O(n log n + 2 log n ) = O(n log n ) i=1 i=1 log n log n
Radix Sort Ph但n t鱈ch Radix sort kh担ng t畛t h董n quicksort M畛t c叩ch nh狸n nh畉n kh叩c l: Ch炭ng t担i c坦 th畛 gi畛 k constant nh動 n l畉n l畉p if ch炭ng t担i cho ph辿p sao ch辿p keys keys n畉m trong (0, bk ), bk < n nh動ng n畉u c叩c keys ph畉i l duy nh畉t, th狸 k ph畉i tng theo n V畛i hi畛u su畉t O(n), C叩c keys h畉i n畉m trong m畛t mi畛n gi畛i h畉n x叩c 畛nh.
Radix Sort - Realities Radix sort s畛 d畛ng nhi畛u b畛 nh畛 n si v湛ng 畛nh v畛 cho m畛i giai o畉n Trong t畛c t畉, i畛u ny s畉 r畉t kh坦 畛 畉t 動畛c O(n) Chi ph鱈 qu畉n l箪 b畛 nh畛 畉nh h動畛ng nhi畛u 畉n l畛i 鱈ch Th叩ch th畛c: Thi畉t k畉 m畛t radix sort t畛ng qu叩t, n坦 ch畉y nhanh h董n so v畛i qsort tr棚n SGIs! Ch動 箪: B畉n c畉n ph畉i c坦 nh畛ng thu畉t to叩n hi畛u qu畉 v畛 c畉p ph叩t, 畛nh v畛 b畛 nh畛!
BIN SORTS i畛m ch畛 y畉u Bin Sorts If t畛n t畉i m畛t hm chuy畛n 畛i m畛t kh坦a v畛 m畛t 畛a ch畛 t動董ng 畛ng (vd m畛t s畛 nguy棚n nh畛) and s畛 l動畛ng c叩c 畛a ch畛 (= s担 l動畛ng bins) l kh担ng l畛n l畉m then ch炭ng ta 畉t 動畛c 畛 ph畛c t畉p s畉p x畉p O(n) Nh動ng nh畛 r畉ng th畛c s畛 n坦 l O(n + m) S畛 l動畛ng bins, m, ph畉i l m畛t h畉ng s畛 v nh畛 (constant and small).

More Related Content

Bai4 binsort

  • 1. C畉u tr炭c d畛 li畛u v Thu畉t gi畉i S畉p x畉p Bin Sorts
  • 2. Bi 2- C叩c i畛m tr畛ng y畉u Quicksort S畛 d畛ng t畛t cho h畉u h畉t c叩c h畛 th畛ng, ( k畛 c畉 tr動畛ng h畛p h畛 th畛ng c坦 th畛i gian th畛c hi畛n kh担ng b畛 rng bu畛c) Heap Sort Ch畉m h董n quick sort, nh動ng b畉o 畉m O(n log n) D湛ng cho c叩c h畛 th畛ng th畛i gian th畛c (nh畛ng h畛 th畛ng b畛 ph棚 ph叩n v畛 th畛i gian th畛c hi畛n)
  • 3. S畉p x畉p (Sorting) B但y gi畛 ch炭ng ta 達 bi畉t m畛t vi thu畉t to叩n s畉p x畉p sau: Selection O(n2) Insertion O(n2) Bubble O(n2) Heap O(n log n) B畉o 畉m Quick O(n log n) Th畛i gian th畛c hi畛n nhanh nh畉t! Li畛u ch炭ng ta c坦 th畛 lm t畛t h董n?
  • 4. S畉p x畉p T畛t h董n O(n log n) ? N畉u t畉t c畉 ch炭ng ta bi畉t v畛 tr畉t t畛 s畉p x畉p c畛a c叩c kh坦a? Kh担ng! Tuy nhi棚n, N畉u ch炭ng ta t鱈nh to叩n 動畛c m畛i 畛a ch畛 c畛a t畛ng kh坦a (th畛i gian l m畛t h畉ng s畛) th狸 Thu畉t to叩n bin sort s畉 cung c畉p hi畛u su畉t t畛t h董n.
  • 5. S畉p x畉p - Bin Sort Gi畉 thi畉t T畉t c畉 c叩c kh坦a n畉m trong m畛t mi畛n gi叩 tr畛 nh畛 v x叩c 畛nh V鱈 d畛 C叩c s畛 nguy棚n thu畛c 0-99 C叩c k箪 t畛 thu畛c A-z, 0-9 t nh畉t, c坦 m畛t s畛 (ch畛 s畛) 畛ng v畛i m畛i gi叩 tr畛 c畛a kh坦a Bin sort C畉p m畛t t炭i (bin) 畛 ch畛a m畛i gi叩 tr畛 c畛a kh坦a Th動畛ng l t畛ng ph畉n t畛 trong d達y s畛 V畛i m畛i s畛, Tr鱈ch ch畛n kh坦a T鱈nh to叩n s畛 th畛 t畛 c畛a t炭i t動董ng 畛ng 畛ng n坦 畉t n坦 vo trong t炭i K畉t th炭c!
  • 6. S畉p x畉p - Bin Sort: Ph但n t鱈ch T畉t c畉 c叩c kh坦a 畛u n畉m trong m畛t mi畛n gi叩 tr畛 nh畛 v x叩c 畛nh. C坦 m gi叩 tr畛 kh坦a ti畛m nng t nh畉t, c坦 m畛t gi叩 tr畛 s畛 畛ng v畛i m畛i kh坦a Bin sort C畉p ph叩t m畛t t炭i (bin) cho m畛i gi叩 tr畛 c畛a kh坦a O(m) Th動畛ng l t畛ng ph畉n t畛 trong m畉ng V畛i t畛ng gi叩 tr畛 s畛, n l畉n Tr鱈ch ch畛n kh坦a O(1) T鱈nh to叩n s畛 th畛 t畛 c畛a t炭i t動董ng 畛ng O(1) G叩n n坦 vo trong t炭i O(1) x n O(n) K畉t th炭c! O(n) + O(m) = O(n+m) = O(n) if n >> m Tr畉ng th叩i kh坦a
  • 7. S畉p x畉p - Bin Sort: Caveat Mi畛n x叩c 畛nh c畛a kh坦a T畉t c畉 c叩c kh坦a 畛u n畉m trong m畛t o畉n nh畛 v x叩c 畛nh C坦 m gi叩 tr畛 kh坦a ti畛m nng N畉u i畛u ki畛n ny kh担ng th鱈ch h畛p, VD: m >> n, th狸 bin sort l O(m) V鱈 d畛 Kh坦a l m畛t s畛 nguy棚n 32-bit, m = 232 R探 rng, kh担ng c坦 c叩ch no 畛 s畉p x畉p 鱈t nh畉t 1000 s畛 nguy棚n. H董n n畛a, ch炭ng t担i kh担ng 畛 kh担ng gian cho c叩c t炭i (bin)! Bin sort 叩nh 畛i kh担ng gian cho t畛c 畛!
  • 8. Sorting - Bin Sort v畛i c叩c b畉n sao C坦 鱈t nh畉t m畛t mi畛n nh畛 畛ng v畛i m畛i gi叩 tr畛 c畛a kh坦a Bin sort C畉p ph叩t m畛t bin cho m畛i gi叩 tr畛 c畛a kh坦a O(m) Th動畛ng l m畛t ph畉n t畛 trong m畛t m畉ng M畉ng c畛a c叩c danh s叩ch ph畉n t畛 V畛i m畛i s畛 (ch畛 s畛 - item), n l畉n Tr鱈ch ch畛n kh坦a O(1) T鱈nh to叩n s畛 th畛 t畛 t炭i (bin) t動董ng 畛ng O(1) B畛 xung n坦 vo danh s叩ch O(1) x n O(n) Gh辿p danh s叩ch O(m) K畉t th炭c! O(n) + O(m) = O(n+m) = O(n) if n >> m N畛i l畛ng?
  • 9. Sorting T畛ng qu叩t c畛a Bin Sort Radix sort Bin sort trong c叩c giai o畉n V鱈 d畛 Giai o畉n 1 S畉p x畉p d畛a vo s畛 c坦 箪 ngh挑a t畛i thi畛u 36 9 0 25 1 49 64 16 81 4 0 1 2 3 4 5 6 7 8 9 0 1 81 64 4 25 36 16 9 49
  • 10. Sorting - Generalised Bin Sort Radix sort - Bin sort trong c叩c giai o畉n Giai o畉n 1 S畉p x畉p d畛a vo s畛 c坦 箪 ngh挑a t畛i thi畛u Giai o畉n 2 S畉p x畉p d畛a vo ph畉n l畛n s畛 c坦 箪 ngh挑a 0 1 2 3 4 5 6 7 8 9 0 1 81 64 4 25 36 16 9 49 0 1 2 3 4 5 6 7 8 9 0
  • 11. Sorting - Generalised Bin Sort Radix sort - Bin sort trong c叩c giai o畉n Giai o畉n 1 S畉p x畉p d畛a vo s畛 c坦 箪 ngh挑a t畛i thi畛u Giai o畉n 2 S畉p x畉p d畛a vo ph畉n l畛n s畛 c坦 箪 ngh挑a 0 1 2 3 4 5 6 7 8 9 0 1 81 64 4 25 36 16 9 49 0 1 2 3 4 5 6 7 8 9 0 1 C畉n th畉n khi b畛 Xung sau khi 達 t畛n t畉i c叩c s畛 trong Bin!
  • 12. Sorting - Generalised Bin Sort Radix sort - Bin sort trong c叩c giai o畉n Giai o畉n 1 S畉p x畉p d畛a vo s畛 c坦 箪 ngh挑a t畛i thi畛u Giai o畉n 2 S畉p x畉p d畛a vo ph畉n l畛n s畛 c坦 箪 ngh挑a 0 1 2 3 4 5 6 7 8 9 0 1 81 64 4 25 36 16 9 49 0 1 2 3 4 5 6 7 8 9 0 1 81
  • 13. Sorting - Generalised Bin Sort Radix sort - Bin sort trong c叩c giai o畉n Giai o畉n 1 S畉p x畉p d畛a vo s畛 c坦 箪 ngh挑a t畛i thi畛u Giai o畉n 2 S畉p x畉p d畛a vo ph畉n l畛n s畛 c坦 箪 ngh挑a 0 1 2 3 4 5 6 7 8 9 0 1 81 64 4 25 36 16 9 49 0 1 2 3 4 5 6 7 8 9 0 1 8164
  • 14. Sorting T畛ng qu叩t c畛a Bin Sort Radix sort - Bin sort trong c叩c giai o畉n Giai o畉n 1 S畉p x畉p d畛a vo s畛 c坦 箪 ngh挑a t畛i thi畛u Giai o畉n 2 S畉p x畉p d畛a vo ph畉n l畛n s畛 c坦 箪 ngh挑a 0 1 2 3 4 5 6 7 8 9 0 1 81 64 4 25 36 16 9 49 0 1 2 3 4 5 6 7 8 9 0 1 4 8164
  • 15. 1 2 3 4 5 6 7 8 9 816425 3616 49 Sorting - Generalised Bin Sort Radix sort -Bin sort trong c叩c giai o畉n Giai o畉n 1 S畉p x畉p d畛a vo s畛 c坦 箪 ngh挑a t畛i thi畛u Giai o畉n 2 S畉p x畉p d畛a vo ph畉n l畛n s畛 c坦 箪 ngh挑a 0 1 2 3 4 5 6 7 8 9 0 1 81 64 4 25 36 16 9 49 0 0 1 4 9 Ch炭 箪 r畉ng: Bin 0 ph畉i th畛c s畛 l畛n
  • 16. 1 2 3 4 5 6 7 8 9 816425 3616 49 Sorting - Generalised Bin Sort Radix sort - Bin sort trong c叩c giai o畉n Giai o畉n 1 S畉p x畉p d畛a vo s畛 c坦 箪 ngh挑a t畛i thi畛u Giai o畉n 2 S畉p x畉p d畛a vo ph畉n l畛n s畛 c坦 箪 ngh挑a 0 1 2 3 4 5 6 7 8 9 0 1 81 64 4 25 36 16 9 49 0 0 1 4 9 Kh担ng gian c畉n thi畉t cho m畛i giai o畉n l bao nhi棚u? n items m bins
  • 17. Sorting T畛ng qu叩t c畛a Bin Sort Radix sort Ph但n t鱈ch Giai o畉n 1 S畉p x畉p d畛a vo s畛 c坦 箪 ngh挑a t畛i thi畛u T畉o m bins O(m) C畉p ph叩t n items O(n) Giai o畉n 2 T畉o m bins O(m) C畉p ph叩t n items O(n) Cu畛i c湛ng Li棚n k畉t m bins O(m) T畉t c畉 c叩c b動畛c th畛c hi畛n tu畉n t畛, v狸 th畉 b畛 xung T畛ng O(3m+2n) O(m+n) O(n) cho m<<n
  • 18. Sorting - Radix Sort Ph但n t鱈ch Radix sort T畛ng qu叩t V畛 c董 b畉n: m畛i giai o畉n c坦 th畛 ph湛 h畛p v畛i c叩c ki畛u d畛 li畛u kh叩c nhau. C叩c s畛 nguy棚n C叩c gi叩 tr畛 c董 s畛 10, 16, 100, C叩c thnh ph畉n d畛 li畛u kh担ng c湛ng ki畛u d畛 li畛u V畉n l O(n) n畉u n >> si v畛i m畛i i struct date { int day; /* 1 .. 31 */ int month; /* 1 .. 12 */ int year; /* 0 .. 99 */ } G 1 - s1=31 bins G 2 - s2=12 bins G 3 - s3=100 bins
  • 19. Radix Sort - Analysis Generalised Radix Sort Algorithm radixsort( A, n ) { for(i=0;i<k;i++) { for(j=0;j<s[i];j++) bin[j] = EMPTY; for(j=0;j<n;j++) { move A[i] to the end of bin[A[i]->fi] } for(j=0;j<s[i];j++) concat bin[j] onto the end of A; } } O( si ) O( n ) O( si ) For each of k radices
  • 20. Radix Sort - Analysis Generalised Radix Sort Algorithm radixsort( A, n ) { for(i=0;i<k;i++) { for(j=0;j<s[i];j++) bin[j] = EMPTY; for(j=0;j<n;j++) { move A[i] to the end of bin[A[i]->fi] } for(j=0;j<s[i];j++) concat bin[j] onto the end of A; } } O( si ) O( n ) O( si ) Clear the si bins for the ith radix
  • 21. Radix Sort - Analysis Generalised Radix Sort Algorithm radixsort( A, n ) { for(i=0;i<k;i++) { for(j=0;j<s[i];j++) bin[j] = EMPTY; for(j=0;j<n;j++) { move A[i] to the end of bin[A[i]->fi] } for(j=0;j<s[i];j++) concat bin[j] onto the end of A; } } O( si ) O( n ) O( si ) Move element A[i] to the end of the bin addressed by the ith field of A[i]
  • 22. Radix Sort - Analysis Generalised Radix Sort Algorithm radixsort( A, n ) { for(i=0;i<k;i++) { for(j=0;j<s[i];j++) bin[j] = EMPTY; for(j=0;j<n;j++) { move A[i] to the end of bin[A[i]->fi] } for(j=0;j<s[i];j++) concat bin[j] onto the end of A; } } O( si ) O( n ) O( si ) Concatenate si bins into one list again
  • 23. Radix Sort Ph但n t鱈ch Total k v嘆ng l畉p, 2si + n cho m畛i v嘆ng Nh動 v畉y k l m畛t h畉ng s畛 T畛ng qu叩t, N畉u keys thu畛c (0, bk-1) Keys l nh畛ng s畛 k-digit base-b si = b for all k 畛 ph畛c t畉p O(n+kb) = O(n) O( si + n ) = O(kn + si ) = O(n + si ) i=1 i=1 i=1 k kk
  • 24. Radix Sort Ph但n t鱈ch ? B畉t c畛 t畉p key no c滴ng c坦 th畛 叩nh x畉 v畛 (0, bk-1) ! Nh動 v畉y ch炭ng ta th動畛ng xuy棚n 畉t 畛 ph畛c t畉p s畉p x畉p O(n)? N畉u k l m畛t h畉ng s畛, 炭ng nh動 v畉y.
  • 25. Radix Sort Ph但n t鱈ch Nh動ng, n畉u k 動畛c ph辿p tng c湛ng v畛i n Vd n坦 l畉y logbn c叩c s畛 c坦 b ch畛 s畛 c董 s畛 畛 bi畛u di畛n n Nh動 v畉y ch炭ng ta c坦: k = log n, si = 2 (say) S畉p x畉p Radix kh担ng t畛t h董n so v畛i quicksort O( 2 + n ) = O(n log n + 2 ) = O(n log n + 2 log n ) = O(n log n ) i=1 i=1 log n log n
  • 26. Radix Sort Ph但n t鱈ch Radix sort kh担ng t畛t h董n quicksort M畛t c叩ch nh狸n nh畉n kh叩c l: Ch炭ng t担i c坦 th畛 gi畛 k constant nh動 n l畉n l畉p if ch炭ng t担i cho ph辿p sao ch辿p keys keys n畉m trong (0, bk ), bk < n nh動ng n畉u c叩c keys ph畉i l duy nh畉t, th狸 k ph畉i tng theo n V畛i hi畛u su畉t O(n), C叩c keys h畉i n畉m trong m畛t mi畛n gi畛i h畉n x叩c 畛nh.
  • 27. Radix Sort - Realities Radix sort s畛 d畛ng nhi畛u b畛 nh畛 n si v湛ng 畛nh v畛 cho m畛i giai o畉n Trong t畛c t畉, i畛u ny s畉 r畉t kh坦 畛 畉t 動畛c O(n) Chi ph鱈 qu畉n l箪 b畛 nh畛 畉nh h動畛ng nhi畛u 畉n l畛i 鱈ch Th叩ch th畛c: Thi畉t k畉 m畛t radix sort t畛ng qu叩t, n坦 ch畉y nhanh h董n so v畛i qsort tr棚n SGIs! Ch動 箪: B畉n c畉n ph畉i c坦 nh畛ng thu畉t to叩n hi畛u qu畉 v畛 c畉p ph叩t, 畛nh v畛 b畛 nh畛!
  • 28. BIN SORTS i畛m ch畛 y畉u Bin Sorts If t畛n t畉i m畛t hm chuy畛n 畛i m畛t kh坦a v畛 m畛t 畛a ch畛 t動董ng 畛ng (vd m畛t s畛 nguy棚n nh畛) and s畛 l動畛ng c叩c 畛a ch畛 (= s担 l動畛ng bins) l kh担ng l畛n l畉m then ch炭ng ta 畉t 動畛c 畛 ph畛c t畉p s畉p x畉p O(n) Nh動ng nh畛 r畉ng th畛c s畛 n坦 l O(n + m) S畛 l動畛ng bins, m, ph畉i l m畛t h畉ng s畛 v nh畛 (constant and small).