Bài giảng Cấu trúc dữ liệu 1 - Chương 2: Tìm kiếm và sắp xếp - Lương Trần Hy Hiến

Nội dung text: Bài giảng Cấu trúc dữ liệu 1 - Chương 2: Tìm kiếm và sắp xếp - Lương Trần Hy Hiến

1. Đại Học Sư Phạm Tp. Hồ Chí Minh Tìm kiếm & Sắp xếp Muïc tieâu: CẤU TRÚC DỮ LIỆU 1 • Giôùi thieäu moät soá thuaät toaùn tìm kieám vaø saép xeáp noäi. CẤU TRÚC DỮ LIỆU 1 • Phaân tích, ñaùnh giaù ñoä phöùc taïp cuûa caùc giaûi thuaät tìm kieám, saép xeáp. Noäi dung: • Nhu caàu tìm kieám vaø saép xeáp döõ lieäu trong moät heä thoáng thoâng tin. Chương 2: Tìm kiếm & Sắp xếp • Caùc giaûi thuaät tìm kieám noäi. • Caùc giaûi thuaät saép xeáp noäi. 2 Tìm kiếm Caùc giaûi thuaät tìm kieám noäi Baøi toaùn: Tìm vò trí xuaát hieän cuûa phaàn töû coù • Tìm tuần tự giaù trò x treân danh saùch ñaëc a • Tìm nhị phân Caùc giaûi thuaät •Taäp döõ lieäu ñöôïc löu tröõ laø daõy soá a1, a2, ,aN tìm kieám noäi int a[N]; •Khoaù caàn tìm laø x int x; 3 4
2. Tìm kieám tuaàn töï Tìm kieám tuaàn töï • Böôùc 1: i = Vò trí ñaàu; • Ví duï: Cho daõy soá a • Böôùc 2: Neáu a[i] = x : Tìm thaáy. Döøng, vò trí 1228516415 xuaát hieän: i • Giaù trò caàn tìm: 8 • Böôùc 3 : i = Vò trí keá(i);// xeùt tieáp phaàn töû keá trong maûng • i = 1 • Böôùc 4: Neáu i >Vò trí cuoái: //Heát maûng Khoâng tìm thaáy. Döøng. Ngöôïc laïi: Laëp laïi Böôùc 2. 5 6 TTìììmm kiekieáááámm tuatuaàààànn ttöïöï Tìm kieám tuaàn töï • i = 2 int LinearSearch(int a[], int N, int x) { for (int i=0; (i<N)&&(a[i]!=x ); i++); if (i<N) return i; // a[i] laø phaàn töû coù khoaù x return -1; // tìm heát maûng nhöng khoâng coù x • i = 3 } 7 8
3. Tìm kieám tuaàn töï Tìm kieám tuaàn töï • Caûi tieán caøi ñaët: duøng phöông phaùp “đặt lính int LinearSearch(int a[], int N, int x) canh” { // maûng goàm N phaàn töû töø a[0] a[N-1] – Ñaët theâm moät phaàn töû coù giaù trò x vaøo cuoái maûng a[N] = x; // theâm lính canh vaøo cuoái daõy – Baûo ñaûm luoân tìm thaáy x trong maûng for (int i=0; (a[i]!=x); i++); – Sau ñoù döïa vaøo vò trí tìm thaáy ñeå keát luaän. if (i<N) return i; // a[i] laø phaàn töû coù khoaù x return -1; // tìm heát maûng nhöng khoâng coù x } 9 10 Tìm kieám tuaàn töï Tìm kieám tuaàn töï • Ñaùnh giaù giaûi thuaät: Nhaän xeùt: – Giaûi thuaät tìm tuyeán tính khoâng phuï thuoäc vaøo thöù töï cuûa caùc phaàn töû trong danh saùch, do vaäy ñaây laø phöông phaùp toång quaùt nhaát ñeå tìm kieám treân moät danh saùch baát kyø. – Moät thuaät toaùn coù theå ñöôïc caøi ñaët theo nhieàu caùch khaùc nhau, kyõ thuaät caøi ñaët aûnh höôûng ñeán toác ñoä thöïc hieän cuûa thuaät toaùn. • Vaäy giaûi thuaät tìm tuaàn töï coù ñoä phöùc taïp tính toaùn caáp n: T(n) = O(n) 11 12
4. Tìm kieám nhò phaân Tìm kieám nhò phaân • Ñoái vôùi nhöõng daõy ñaõ sắp thöù töï (giaû söû thöù töï • YÙ töôûng cuûa giaûi thuaät laø taïi moãi böôùc tieán taêng), caùc phaàn töû trong daõy coù quan heä haønh so saùnh x vôùi phaàn töû naèm ôû vò trí giöõa ≤ ≤ cuûa daõy tìm kieám hieän haønh, döïa vaøo keát quaû ai -1 ai ai+1  so saùnh naøy ñeå quyeát ñònh giôùi haïn daõy tìm Neáu x > ai thì x chæ coù theå xuaát hieän trong ñoaïn [a ,a ] cuûa daõy kieám ôû böôùc keá tieáp laø nöûa treân hay nöûa döôùi i+1 N cuûa daõy tìm kieám hieän haønh  Neáu x x: //tìm x trong daõy con aleft amid -1 right = mid - 1; Ngöôïc laïi //tìm x trong daõy con amid +1 aright left = mid + 1; //Heát laëp Böôùc 3: Döøng, khoâng tìm thaáy. 15 16
5. Tìm kieám nhò phaân Tìm kieám nhò phaân • left = 1, right = 8, mid = 4 • left = 5, right = 8, mid = 6 17 18 Tìm kieám nhò phaân Tìm kieám nhò phaân int BinarySearch(int a[],int N,int x ) • Ñaùnh giaù giaûi thuaät: { int left =0, right = N-1, midle; while (left <= right) { midle = (left + right)/2; if (x == a[midle]) return midle;//Tìm thaáy x taïi mid if (x<a[midle])right = midle -1; • Giaûi thuaät tìm nhò phaân coù ñoä phöùc taïp else left = midle +1; } tính toaùn caáp logn: return -1; // trong daõy khoâng coù x T(n) = O(log n) } 2 19 20
6. Tìm kieám nhò phaân Tìm kieám nhò phaân Nhaän xeùt: Nhaän xeùt: – Giaûi thuaät tìm nhò phaân döïa vaøo quan heä giaù trò – Khi muoán aùp duïng giaûi thuaät tìm nhò phaân caàn cuûa caùc phaàn töû maûng ñeå ñònh höôùng trong quaù phaûi xeùt ñeán thôøi gian saép xeáp daõy soá ñeå thoûa trình tìm kieám, do vaäy chæ aùp duïng ñöôïc cho ñieàu kieän daõy soá coù thöù töï. Thôøi gian naøy khoâng nhöõng daõy ñaõ coù thöù töï. nhoû, vaøkhi daõy soábieán ñoäng caàn phaûi tieán haønh – Giaûi thuaät tìm nhò phaân tieát kieäm thôøi gian hôn saép xeáp laïi => khuyeát ñieåm chính cho giaûi thuaät raát nhieàu so vôùi giaûi thuaät tìm tuaàn töï do tìm nhò phaân. – Caàn caân nhaéc nhu caàu thöïc teá ñeå choïn moät trong Tnhò phaân (n) = O(log 2 n) aj, thì ta goïi ñoù laø moät nghòch döïa treân noäi dung thoâng tin löu giöõ taïi moãi theá. phaàn töû. • Maûng chöa saép xeáp seõ coù nghòch theá. • Löu yù: Thöù töï ñöôïc ñeà caäp ôû ñaây laø moät thöù • Maûng ñaõ coù thöù töï seõ khoâng chöùa nghòch theá. töï toång quaùt. ≤ ≤ ≤ a0 a1 an • Ví duï: Haõy ñònh nghóa moät thöù töï ñeå daõy soá sau laø daõy taêng theo thöù töï naøy. 1 3 5 7 222010623 24
7. Caùc phöông phaùp saép xeáp thoâng duïng Selection sort – YÙ töôûng • Selection sort • Shell sort • Nhaän xeùt: Maûng coù thöù töï thì Phöùc taïïp hôn • Insertion sort • Heap sortHieääu quaûû cao ai = min(ai, ai+1, , an-1)  • Interchange sort • Quick sort YÙ töôûng: moâ phoûng moät trong nhöõng caùch saép xeáp töï nhieân nhaát trong thöïc teá: • • Bubble sort Merge sort – Choïn phaàn töû nhoû nhaát trong N phaàn töû ban ñaàu, • Shaker sort • Radix sort ñöa phaàn töû naøy veà vò trí ñuùng laø ñaàu daõy hieän haønh • • Binary Insertion – Xem daõy hieän haønh chæ coøn N-1 phaàn töû cuûa daõy sort Lôùùp thuaäät toaùùn ban ñaàu, baét ñaàu töø vò trí thöù 2; laëp laïi quaù trình khaùùc treân cho daõy hieän haønh ñeán khi daõy hieän haønh Ñôn giaûûn, chæ coøn 1 phaàn töû. Chi phí cao 25 26 Selection sort – Thuaät toaùn Selection sort – Ví duï //input: daõy (a, N) //output: daõy (a, N) ñaõ ñöôïc saép xeáp Find MinPos(1, 8) Swap(ai, amin) • Böôùc 1 : i = Vò trí ñaàu; min • Böôùc 2 : Tìm phaàn töû a[min] nhoû nhaát trong daõy 1 2345678 hieän haønh töø a[i] ñeán a[N] 12 2 8 5 1 6 4 15 • Böôùc 3 : Neáu min ≠ i: Hoaùn vò a[min] vaø a[i] • Böôùc 4 : Neáu i chöa laø Vò trí cuoái i » i = Vò trí keá(i); » Laëp laïi Böôùc 2 Ngöôïc laïi: Döøng. //N phaàn töû ñaõ naèm ñuùng vò trí. 27 28
8. Selection sort – Ví duï Selection sort – Ví duï Find MinPos(2, 8) Swap(ai, amin) Find MinPos(3, 8) Swap(ai, amin) min min 1 2345678 1 2345678 1 2 8 5 12 6 4 15 1 2 8 5 12 6 4 15 i i 29 30 Selection sort – Ví duï Selection sort – Ví duï Find MinPos(4, 8) Swap(ai, amin) Find MinPos(5, 8) Swap(ai, amin) min min 1 2345678 1 2345678 1 2 4 5 12 6 8 15 1 2 4 5 12 6 8 15 i i 31 32
9. Selection sort – Ví duï Selection sort – Ví duï Find MinPos(6, 8) Swap(ai, amin) Find MinPos(7, 8) Swap(ai, amin) min min 1 2345678 1 2345678 1 2 4 5 6 12 8 15 1 2 4 5 6 8 12 15 i i 33 34 Selection sort Selection sort – Ñaùnh giaù giaûi thuaät void SelectionSort(int a[],int N ) { • Soá laàn hoaùn vò (moät hoaùn vò baèng 3 pheùp int min; // chæ soá phaàn töû nhoû nhaát trong daõy hieän haønh for (int i=0; i<N-1 ; i++) gaùn) phuï thuoäc vaøo tình traïng ban ñaàu { cuûa daõy soá min = i; for(int j = i+1; j < N ; j++) if (a[j] < a[min]) min = j; // ghi nhaän vò trí phaàn töû nhoû nhaát if (min != i) Swap(a[min], a[i]); } } 35 36
10. Selection sort – Ñaùnh giaù giaûi thuaät Insertion Sort – YÙ töôûng • ÔÛû löôït thöù i, caàn (N-i) laàn so saùnh ñeå xaùc • Nhaän xeùt: moïi daõy a1 , a2 , , an luoân coù i-1 phaàn töû ñònh phaàn töû nhoû nhaát hieän haønh. ñaàu tieân a1 , a2 , ,ai-1 ñaõ coù thöù töï (2 ≤ i). YÙ töôûng chính: tìm caùch cheøn phaàn töû a vaøo vò trí • Soá löôïng pheùp so saùnh khoâng phuï thuoäc vaøo i thích hôïp cuûa ñoaïn ñaõ ñöôïc saép ñeå coù daõy môùi a1 , tình traïng cuûa daõy soá ban ñaàu. a2 , ,ai trôû neân coù thöù töï. – Vò trí naøy chính laø pos thoûa a ≤ a <a (1≤pos≤i). • Trong moïi tröôøng hôïp, soá laàn so saùnh laø: pos-1 i pos Chi tieát hôn: n−1 n(n −1) – Daõy ban ñaàu a1 , a2 , , an, xem nhö ñaõ coù ñoaïn goàm moät ∑(n − i) = phaàn töû a1 ñaõ ñöôïc saép. i=1 2 – Theâm a2 vaøo ñoaïn a1 seõ coù ñoaïn a1 a2 ñöôïc saép – Theâm a3 vaøo ñoaïn a1 a2 ñeå coù ñoaïn a1 a2 a3 ñöôïc saép – Tieáp tuïc cho ñeán khi theâm xong aN vaøo ñoaïn a1 a2 aN-1 seõ 37 coù daõy a1 a2 aN ñöôïc saép. 38 Insertion Sort – Thuaät toaùn Insertion Sort – Ví duï //input: daõy (a, N) //output: daõy (a, N) ñaõ ñöôïc saép xeáp • Böôùc 1: i = 2; // giaû söû coù ñoaïn a[1] ñaõ ñöôïc saép • Böôùc 2: x = a[i]; Tìm vò trí pos thích hôïp trong ñoaïn 1 2345678 a[1] 12 2 8 5 1 6 4 15 ñeán a[i] ñeå cheøn x vaøo • Böôùc 3: Dôøi choã caùc phaàn töû töø a[pos] ñeán a[i-1] sang phaûi 1 vò trí ñeå daønh choå cho x • Böôùc 4: a[pos] = x; // coù ñoaïn a[1] a[i] ñaõ ñöôïc saép • Böôùc 5: i = i+1; Neáu i ≤ n : Laëp laïi Böôùc 2. Ngöôïc laïi : Döøng. 39 40
11. Insertion Sort – Ví duï Insertion Sort – Ví duï Insert a2 into (1, 2) Insert a3 into (1, 3) pos pos 1 2345678 1 2345678 122 2 8 5 1 6 4 15 2 128 8 5 1 6 4 15 i i x x 41 42 Insertion Sort – Ví duï Insertion Sort – Ví duï Insert a4 into (1, 4) Insert a5 into (1, 5) pos pos 1 2345678 1 2345678 2 58 12 5 1 6 4 15 12 5 8 12 1 6 4 15 i i x x 43 44
12. Insertion Sort – Ví duï Insertion Sort – Ví duï Insert a6 into (1, 6) Insert a7 into (1, 7) pos pos 1 2345678 1 2345678 1 2 5 68 12 6 4 15 1 2 45 6 8 12 4 15 i i x x 45 46 Insertion Sort – Ví duï Insertion Sort – Ví duï Insert a8 into (1, 8) pos pos 1 2345678 1 2345678 1 2 4 5 6 8 12 15 1 2 4 5 6 8 12 15 i x 47 48
13. Insertion Sort – Caøi ñaët Insertion Sort – Nhaän xeùt void InsertionSort(int a[], int N ) { • Khi tìm vò trí thích hôïp ñeå cheøn a[i] vaøo ñoaïn int pos, i; a[0] ñeán a[i-1], do ñoaïn ñaõ ñöôïc saép  coù theå int x;//löu tröõ a[i] traùnh bò ghi ñeø khi dôøi choã caùc phaàn töû. söû duïng giaûi thuaät tìm nhò phaân ñeå thöïc hieän  for(int i=1 ; i 0)&&(a[pos-1]>x);pos ) khoâng laøm giaûm soá laàn dôøi choã. a[pos] = a[pos-1]; • Ngoaøi ra, coù theå caûi tieán giaûi thuaät cheøn tröïc a[pos] = x;// cheøn x vaøo daõy tieáp vôùi phaàn töû caàm canh ñeå giaûm ñieàu kieän } kieåm tra khi xaùc ñònh vò trí pos. } 49 50 Binary Insertion Sort – Caøi ñaët Insertion Sort – Ñaùnh giaù giaûi thuaät void BInsertionSort(int a[], int N ) • Caùc pheùp so saùnh xaûy ra trong moãi voøng laëp tìm vò trí { int l,r,m,i; int x;//löu tröõ giaù trò a[i] traùnh bò ghi ñeø khi dôøi choã caùc phaàn thích hôïp pos. Moãi laàn xaùc ñònh vò trí pos ñang xeùt töû. khoâng thích hôïp  dôøi choã phaàn töû a[pos-1] ñeán vò trí for(int i=1 ; i l ; j ) a[j] = a[j-1]; // dôøi choã caùc phaàn töû seõ ñöùng sau x a[l] = x; // cheøn x vaøo daõy } } 51 52
14. Interchange Sort – YÙ töôûng • Nhaän xeùt: Ñeå saép xeáp moät daõy soá, ta coù theå xeùt caùc nghòch theá coù trong daõy vaø laøm trieät tieâu daàn chuùng ñi.  YÙ töôûng chính: – Xuaát phaùt töø ñaàu daõy, tìm taát caû nghòch theá chöùa phaàn töû naøy, trieät tieâu chuùng baèng caùch ñoåi choã phaàn töû naøy vôùi phaàn töû töông öùng trong caëp nghòch theá. Phương pháp đổi chỗ trực tiếp – Laëp laïi xöû lyù treân vôùi caùc phaàn töû tieáp theo Interchange Sort trong daõy 54 Interchange Sort – Thuaät toaùn Interchange Sort – Ví duï //input: daõy (a, N) //output: daõy (a, N) ñaõ ñöôïc saép xeáp • Böôùc 1 : i = 1; // baét ñaàu töø ñaàu daõy j • Böôùc 2 : j = i+1; //tìm caùc caëp phaàn töû 1 2345678 a[j] i 121 2 8 5 1 6 4 15 • Böôùc 3 : Trong khi j ≤ N thöïc hieän • Neáu a[j]<a[i]: a[i]↔a[j]; i •j = j+1; • Böôùc 4 : i = i+1; – Neáu i < n: Laëp laïi Böôùc 2. – Ngöôïc laïi: Döøng. 55 56
15. Interchange Sort – Ví duï Interchange Sort – Ví duï j j 1 2345678 1 2345678 1 122 8 5 2 6 4 15 1 2 124 8 5 6 4 15 i i 57 58 Interchange Sort – Ví duï Interchange Sort – Ví duï j 1 2345678 1 2345678 1 2 4 125 8 6 5 15 1 2 4 5 6 8 12 15 i 59 60
16. Interchange Sort - Caøi ñaët Interchange Sort Ñaùnh giaù giaûi thuaät void InterchangeSort(int a[], int N) • Soá löôïng caùc pheùp so saùnh xaûy ra khoâng phuï { thuoäc vaøo tình traïng cuûa daõy soá ban ñaàu int i, j; • Soá löôïng pheùp hoaùn vò thöïc hieän tuøy thuoäc for (i = 0 ; i<N-1 ; i++) vaøo keát quaû so saùnh for (j =i+1; j < N ; j++) if(a[j]< a[i]) //neáu coù nghòch theá thì ñoåi choã Swap(a[i],a[j]); } 61 62 Bubble sort – YÙ töôûng • YÙ töôûng chính: – Xuaát phaùt töø cuoái (ñaàu) daõy, ñoåi choã caùc Phương pháp nổi bọt caëp phaàn töû keá caän ñeå ñöa phaàn töû nhoû Bubble sort (lôùn) hôn trong caëp phaàn töû ñoù veà vò trí ñuùng ñaàu (cuoái) daõy hieän haønh, sau ñoù seõ khoâng xeùt ñeán noù ôû böôùc tieáp theo, – ÔÛ laàn xöû lyù thöù i coù vò trí ñaàu daõy laø i – Laëp laïi xöû lyù treân cho ñeán khi khoâng coøn caëp phaàn töû naøo ñeå xeùt. 64
17. Bubble sort – Thuaät toaùn Bubble Sort – Ví duï //input: daõy (a, N) //output: daõy (a, N) ñaõ ñöôïc saép xeáp j • Böôùc 1 : i = Vò trí ñaàu; 1 2345678 • Böôùc 2 : j = Vò trí cuoái;//Duyeät töø cuoái daõy ngöôïc veà vò trí i 121 2 8 5 1 6 4 15 – Trong khi (j > i) thöïc hieän: • Neáu a[j]<a[j-1]: a[j]↔a[j-1];//xeùt caëp phaàn töû keá caän i • j = Vò trí tröôùc(j); • Böôùc 3 : i = Vò trí keá(i); // laàn xöû lyù keá tieáp – Neáu i = Vò trí cuoái: Döøng. // Heát daõy. – Ngöôïc laïi : Laëp laïi Böôùc 2. 65 66 Bubble Sort – Ví duï Bubble Sort – Ví duï j j 1 2345678 1 2345678 1 122 2 8 5 4 6 15 1 2 124 4 8 5 6 15 i i 67 68
18. Bubble Sort – Ví duï Bubble Sort – Ví duï j j 1 2345678 1 2345678 1 2 4 125 8 5 6 15 1 2 4 5 126 8 6 15 i i 69 70 Bubble Sort – Ví duï Bubble Sort – Ví duï j j 1 2345678 1 2345678 1 2 4 5 6 128 8 15 1 2 4 5 6 8 12 15 i i 71 72
19. Bubble sort - Caøi ñaët Bubble sort - Ñaùnh giaù giaûi thuaät • Soá löôïng caùc pheùp so saùnh xaûy ra khoâng phuï void BubbleSort(int a[], int N) thuoäc vaøo tình traïng cuûa daõy soá ban ñaàu { int i, j; • Soá löôïng pheùp hoaùn vò thöïc hieän tuøy thuoäc vaøo keát quaû so saùnh for (i = 0 ; i i ; j ) if(a[j]< a[j-1]) Swap(a[j], a[j-1]); } 73 74 Bubble sort - Ñaùnh giaù giaûi thuaät Bubble sort – Caûi tieán • Giaûi thuaät ShakerSort: • Khuyeát ñieåm: – Döïa treân nguyeân taéc ñoåi choã tröïc tieáp – Khoâng nhaän dieän ñöôïc tình traïng daõy ñaõ coù thöù töï hay coù thöù töï töøng phaàn. – Tìm caùch khaéc phuïc caùc nhöôïc ñieåm cuûa BubleSort – Caùc phaàn töû nhoû ñöôïc ñöa veà vò trí ñuùng raát • Trong moãi laàn saép xeáp, duyeät maûng theo 2 löôït nhanh, trong khi caùc phaàn töû lôùn laïi ñöôïc töø 2 phía khaùc nhau : ñöa veà vò trí ñuùng raát chaäm. – Löôït ñi: ñaåy phaàn töû nhoû veà ñaàu maûng – Löôït veà: ñaåy phaàn töû lôùn veà cuoái maûng • Ghi nhaän laïi nhöõng ñoaïn ñaõ saép xeáp nhaèm tieát kieäm caùc pheùp so saùnh thöøa. 75 76
20. Giaûi thuaät ShakerSort Giaûi thuaät ShakerSort //input: daõy (a, N) • Böôùc 2 : //output: daõy (a, N) ñaõ ñöôïc saép xeáp – Böôùc 2b : j = l ; // ñaåy phaàn töû lôùn veà cuoái maûng • Böôùc 1 : • Trong khi (j a[j+1]: a[j] ↔ a[j+1]; – k = n; // ghi nhaän laïi vò trí k xaûy ra hoaùn vò sau cuøng » k = j;//löu laïi nôi xaûy ra hoaùn vò // ñeå laøm cô sôû thu heïp ñoaïn l ñeán r – j = j+1; • Böôùc 2 : • r = k; //loaïi bôùt caùc phaàn töû ñaõ coù thöù töï ôû cuoái daõy – Böôùc 2a : j = r ; // ñaåy phaàn töû nhoû veà ñaàu maûng • Trong khi (j > l) : • Böôùc 3 : Neáu l < r: Laëp laïi Böôùc 2. – Neáu a[j]<a[j-1]: a[j] ↔ a[j-1]; » k = j; //löu laïi nôi xaûy ra hoaùn vò – j = j-1; • l = k; //loaïi bôùt caùc phaàn töû ñaõ coù thöù töï ôû ñaàu daõy 77 78 Saép xeáp caây - Heap sort Sắp xếp cây - Heap sort • Khi tìm phaàn töû nhoû nhaát ôû böôùc i, phöông • Xét dãy số : 5 2 6 4 8 1 phaùp saép xeáp choïn tröïc tieáp khoâng taän duïng • Giả sử các phần tử của dãy được bố trí ñöôïc caùc thoâng tin ñaõ coù ñöôïc do caùc pheùp so theo quan hệ so sánh và tạo thành sơ saùnh ôû böôùc i-1. đồ dạng cây: • Giaûi thuaät Heap Sort khaéc phuïc nhöôïc ñieåm naøy baèng caùch choïn ra ñöôïc moät caáu truùc döõ lieäu cho pheùp tích luõy caùc thoâng tin veà söï so saùnh giaù trò caùc phaàn töû trong quaù trình saép xeáp. 79 80
21. Saép xeáp caây - Heap sort Saép xeáp caây - Heap sort • Phaàn töû ôû möùc i chính laø phaàn töû lôùn trong caëp • Loaïi boû 8 ra khoûi caây vaø theá vaøo caùc choã phaàn töû töông öùng ôû möùc i+1 troáng giaù trò -∞ ñeå tieän vieäc caäp nhaät laïi caây : ⇒ phaàn töû ôû möùc 0 (nuùt goác cuûa caây) luoân laø phaàn töû lôùn nhaát cuûa daõy. • Neáu loaïi boû phaàn töû goác ra khoûi caây (nghóa laø ñöa phaàn töû lôùn nhaát veà ñuùng vò trí), thì vieäc caäp nhaät caây chæ xaûy ra treân nhöõng nhaùnh lieân quan ñeán phaàn töû môùi loaïi boû, coøn caùc nhaùnh khaùc ñöôïc baûo toaøn, nghóa laø böôùc keá tieáp coù theå söû duïng laïi caùc keát quaû so saùnh ôû böôùc hieän taïi. 81 82 Saép xeáp caây - Heap sort Saép xeáp caây - Heap sort • Toaøn boä nhaùnh traùi cuûa caây cuõ ñöôïc baûo • Tieán haønh nhieàu laàn vieäc loaïi boû phaàn töû goác cuûa toaøn caây cho ñeán khi taát caû caùc phaàn töû cuûa caây ñeàu laø - ∞, khi ñoù xeáp caùc phaàn töû theo thöù töï loaïi boû treân ⇒ Böôùc keá tieáp ñeå choïn ñöôïc phaàn töû lôùn caây seõ coù daõy ñaõ saép xeáp. nhaát hieän haønh laø 6, chæ caàn laøm theâm • Ñeå caøi ñaët thuaät toaùn hieäu quaû, caàn phaûi toå chöùc moät pheùp so saùnh 1 vôùi 6. moät caáu truùc löu tröõ döõ lieäu coùkhaûnaêng theåhieän ñöôïc quan heä cuûa caùc phaàn töû trong caây vôùi n oâ nhôù thay vì 2n-1 nhö trong ví duï. • Khaùi nieäm heap vaø phöông phaùp saép xeáp Heapsort do J.Williams ñeà xuaát ñaõ giaûi quyeát ñöôïc caùc khoù khaên treân. 83 84
22. Saép xeáp caây - Heap sort Ví duï daõy laø heap: • Ñònh nghóa heap: 1 2345678 – Heap laø moät daõy caùc phaàn töû aleft, aleft+1, , aright thoaû caùc quan heä: ≥ • ai a2i ≥ 15 12 8 5 1 4 6 2 • ai a2i+1 vôùi ∀i ∈ [left, right] – Khi ñoù (ai , a2i), (ai ,a2i+1) ñöôïc goïi laø caùc caëp phaàn töû lieân ñôùi. – Heap ñöôïc ñònh nghóa nhö treân ñöôïc duøng trong tröôøng hôïp saép xeáp taêng daàn, khi saép xeáp giaûm daàn phaûi ñoåi chieàu caùc quan heä. 85 86 Saép xeáp caây – Heap sort Saép xeáp caây - Heap sort • Moät soá tính chaát cuûa Heap: a1 Caùc phaàn töû – Tính chaát 1: Neáu aleft, aleft+1, , aright laø moät cuûa daõy ñöôïc heap thì khi caét boû moät soá phaàn töû ôû hai bieåu dieãn theo ñaàu cuûa heap, daõy con coøn laïi vaãn laø moät a a caùc moái quan 2 3 heä lieân ñôùi heap. – Tính chaát 2: Neáu a1, a2, , an laø moät heap a a a a thì phaàn töû a1 (ñaàu heap) luoân laø phaàn töû 4 5 6 7 lôùn nhaát trong heap. – Tính chaát 3: Moïi daõy con aleft, aleft+1, , a 8 aright thoûa: 2left > right ñeàu laø heap. 87 88
23. Ví duï caùc tính chaát cuûa heap: Saép xeáp caây - Heap sort • Saép xeáp daõy taêng daàn qua 2 giai ñoaïn: 1 2345678 – Giai ñoaïn 1: Döïa vaøo tính chaát 3 cuûa heap 15 12 8 5 1 6 4 2 ñeå hieäu chænh daõy ban ñaàu thaønh heap – Giai ñoaïn 2: Döïa vaøo caùc tính chaát 1 vaø 2 cuûa heap ñeå saép xeáp heap coù ñöôïc sau giai 12 8 5 1 6 4 ñoaïn 1 thaønh daõy taêng daàn 1 6 4 2 89 90 Heap sort – Giai ñoaïn 1 Heap sort – Giai ñoaïn 1 • Vaán ñeà: Ñoåi choå moät soá phaàn töû treân //input: daõy (a, N) daõy a1, , aN ñeå daõy trôû thaønh heap. //output: daõy (a, N) laø moät heap • YÙ töôûng: theo tính chaát 3, daõy con an/2+1 , • Böôùc 1: left = N/2; //Theâm caùc phaàn töû a a ñöông nhieân laø heap. Laàn löôït n/2+2 n aleft, , a1 vaøo heap theâm vaøo phía tröôùc daõy caùc phaàn töû • Böôùc 2: Trong khi left > 0 an/2, an/2-1, , a1; moãi böôùc theâm vaøo caàn //Löu yù: ñoaïn a , , a ñaõ laø heap hieäu chænh vò trí caùc phaàn töû theo moái left+1 N • Böôùc 21: Hieäu chænh ñoaïn aleft, , aN thaønh heap quan heä lieân ñôùi ta seõ nhaän ñöôïc heap • Böôùc 22: left = left - 1; mong muoán. //Heát laëp 91 92
24. Heap sort – Giai ñoaïn 1 Heap sort – Giai ñoaïn 1 curr joint joint 1 2345678 1 2345678 12 2 8 5 1 6 4 15 12 2 8 5 1 6 4 155 left 93 94 Heap sort – Giai ñoaïn 1 Heap sort – Giai ñoaïn 1 curr joint joint joint curr joint joint 1 2345678 1 2345678 12 2 8 15 1 6 4 5 12 15 8 5 1 6 4 2 left left 95 96
25. Heap sort – Giai ñoaïn 1 Heap sort – Giai ñoaïn 2 • Vaán ñeà: Saép xeáp heap a1, , aN thaønh daõy taêng daàn  1 2345678 //Ñaët: right = N daõy a1, , aright laø heap. • YÙ töôûng: 15 12 8 5 1 6 4 2 – Theo tính chaát 2: a1 seõ laø phaàn töû lôùn nhaát, vì vaäy vò trí ñuùng cuûa a1 phaûi laø right - cuoái daõy.   Ñoåi choå (a1, aright) ñöôïc theâm moät phaàn töû ôû ñuùng vò trí  Theo tính chaát 3: daõy con a2, , aright-1 vaãn laø heap  Giaûm right, theâm a1 vaøo daõy vaø hieäu chænh laïi  daõy a1, , aright laø heap. 97 98 Heap sort – Giai ñoaïn 2 Heap sort – Giai ñoaïn 2 //input: daõy (a, N) laø heap //output: daõy (a, N) saép taêng daàn • Böôùc 1: right = N; //Baét ñaàu thöïc hieän töø cuoái 1 2345678 daõy 15 12 8 5 1 6 4 2 • Böôùc 2: Trong khi right > 1 //Ñöa phaàn töû lôùn nhaát (a )veà vò trí right 1 right • Böôùc 2.1: Hoaùnvò (a1 , aright); //Loaïi boû phaàn töû lôùn nhaát ra khoûi heap Swap(a1, aright) • Böôùc 2.2: right := right -1; • Böôùc 2.3: Hieäu chænh ñoaïn a1, a2, , aright thaønh heap //Heát laëp 99 100
26. Heap sort – Giai ñoaïn 2 Heap sort – Giai ñoaïn 2 curr joint joint 1 2345678 1 2345678 2 12 8 5 1 6 4 15 12 5 8 2 1 6 4 15 right right Shift(a, 1, right) Swap(a1, aright) 101 102 Heap sort – Giai ñoaïn 2 Heap sort – Giai ñoaïn 2 curr joint joint joint 1 2345678 1 2345678 4 5 8 2 1 6 12 15 8 5 6 2 1 4 12 15 right right Shift(a, 1, right) Swap(a1, aright) 103 104
27. Heap sort – Giai ñoaïn 2 Heap sort – Hieäu chænh heap • Vaán ñeà: daõy con aleft+1, aleft+2, , aright laø heap, caàn hieäu chænh laïi ñeå aleft, , aright laø heap 1 2345678 • YÙ töôûng: do aleft+1, aleft+2, , aright laø heap neân taát 4 5 6 2 1 8 12 15 caû caùc phaàn töû naøy ñeàu ñaõ thoûa ñieàu kieän lieân ñôùi  vaán ñeà trôû thaønh: kieåm tra quan heä lieân ñôùi cuûa aleft vaø ñoåi choå aleft vôùi lieân ñôùi thích hôïp 1 2 4 5 6 8 12 15 cuûa noù neáu quan heä lieân ñôùi bò vi phaïm; sau khi hieäu chænh söï vi phaïm ñieàu kieän lieân ñôùi coù theå lan truyeàn ñeán caùc vò trí môùi hieäu chænh. 105 106 Heap sort – Hieäu chænh heap Heap sort – Hieäu chænh heap • Nhaän xeùt: Quaù trình hieäu chænh coù nhieàu curr joint joint joint böôùc ñoåi choã trung gian khoâng caàn thieát. 1 2345678 • Trong ví duï: ñoåi choã (2, 15), sau ñoù ñoåi choå 2 8 15 1 6 4 25 tieáp (2, 5): vò trí cuoái cuøng cuûa 2 laø 8, 2 ôû vò trí 4 chæ laø taïm thôøi, khoâng caàn thieát. left right Coù theå thöïc hieän vieäc dôøi choã haøng loaït, sau ñoù ñöa giaù trò caàn hieäu chænh vaøo ñuùng choã 107 108
28. Heap sort – Hieäu chænh heap Heap sort – Hieäu chænh heap //input: daõy con aleft+1, aleft+2, , aright laø heap //output: daõy con aleft, aleft+1, , aright laø heap • Böôùc 1: curr joint ??? joint 1 2345678 • curr = left; x = acurr; //Baét ñaàu kieåm tra töø vò trí left • joint = 2*curr; //Lieân ñôùi thöù nhaát cuûa curr 2 8 15 1 6 4 25 • Böôùc 2: Trong khi (joint ≤ right) //Coøn lieân ñôùi ñeå xeùt left right • Böôùc 21: Neáu (joint ajoint) joint = joint + 1; //joint: vò trí lieân ñôùi lôùn nhaát • Böôùc 22: Neáu ajoint ≤ x //Thoûa ñieàu kieän lieân ñôùi Chuyeån ñeán Böôùc 3 • Böôùc 23: acurr = ajoint; curr = joint; joint = 2*curr; //Heát laëp • Böôùc 3: acurr = x; 109 110 Heap sort – Caøi ñaët Heap sort – Caøi ñaët void Shift (int a[], int left, int right) • Ñeå caøi ñaët giaûi thuaät Heapsort caàn xaây { döïng caùc thuû tuïc: int x, curr, joint; curr = left; joint =2*curr+1;// ajoint: phaàn töû lieân ñôùi x = a[curr]; – Thuû tuïc hieäu chænh daõy aleft, aleft+1, , aright while (joint <= right) thaønh heap: { if (joint < right) // neáu coù ñuû 2 phaàn töû lieân ñôùi void Shift (int a[], int left, int right) if (a[joint] < a[joint+1]) – Thuû tuïc chuyển ñổi daõy a , a , , a thaønh joint = joint+1; 0 2 N-1 if (a[joint]<x) break; //thoaû quan heä lieân ñôùi heap: a[curr] = a[joint]; curr = joint; // xeùt tieáp khaû naêng hieäu chænh lan truyeàn void CreateHeap(int a[], int N ) joint = 2*curr+1; – Thuû tuïc saép xeáp daõy a , a , , a taêng daàn: } 0 2 N-1 a[curr] = x; void HeapSort(int a[], int N) } 111 112
29. Heap sort – Caøi ñaët Heap Sort – Caøi ñaët void CreateHeap(int a[], int N) void HeapSort (int a[], int N) { { int right; int left; CreateHeap(a, N); //saép xeáp daõy a thanh heap //left: vị trí phần tử cần ghép thêm right = N-1; // right laø vò trí ñuùng cho phaàn töû lôùn nhaát while (right > 0) for (left = (N-1)/2; left >= 0; left { ) Swap(a[0],a[right]); Shift(a, left, N-1); right ; Shift(a,0,right); } } } 113 114 Heap Sort – Ñaùnh giaù giaûi thuaät Shell sort – YÙ töôûng • ShellSort laø moät phöông phaùp caûi tieán cuûa phöông phaùp • Vieäc ñaùnh giaù moät caùch chính xaùc giaûi thuaät saép xeáp cheøn tröïc tieáp. YÙ töôûng cuûa phöông phaùp saép Heapsort raát phöùc taïp. Tuy nhieân, coù theå ñaùnh giaù xeáp naøy laø xem xeùt daõy ban ñaàu nhö nhöõng daõy con goàm moät caùch töông ñoái döïa vaøo moät soá nhaän xeùt: caùc phaàn töû ôû caùch nhau len vò trí; tieán haønh saép xeáp  – Khi xem xeùt heap ôû daïng caây quan heä lieân ñôùi  caùc treân töøng daõy con; giaûm daàn böôùc len ñeán khi len = 1 phaàn töû cuûa heap taïo thaønh caây nhò phaân coù ñoä cao saép xeáp xong: ≈ h log2N. • Daõy ban ñaàu : a1, a2, , aN ñöôïc xem nhö söï xen keõ cuûa – ÔÛ moãi böôùc hieäu chænh, soá pheùp ñieàu chænh caùc vi phaïm caùc daõy con sau : lieân ñôùi khoâng vöôït quaù chieàu cao h cuûa caây lieân ñôùi. – Daõy con thöù nhaát : a1 alen+1 a2len+1 – Daõy con thöù hai : a a a – ÔÛ caû giai ñoaïn 1 vaø giai ñoaïn 2 soá pheùp hieäu chænh 2 len+2 2len+2 khoâng vöôït quaù N – – Daõy con thöù len : a a a Trong tröôøng hôïp xaáu nhaát ñoä phöùc taïp thuaät toaùn len 2len 3len O(Nlog2N) 115 116
30. Shell sort – YÙ töôûng Shell sort – Thuaät toaùn • Vieäc saép xeáp caùc phaàn töû trong cuøng daõy con seõ laøm cho //input: daõy (a, N); daõy (h, k): k ñoä daøi caùc böôùc laëp - caùc phaàn töû ñöôïc ñöa veà vò trí ñuùng töông ñoái (chæ ñuùng const trong daõy con, so vôùi toaøn boä caùc phaàn töû trong daõy ban //output: daõy (a, N) laøñöôïc saép taêng daàn ñaàu coù theå chöa ñuùng) moät caùch nhanh choùng. • Khi khoaûng caùch len giaûm taïo thaønh caùc daõy con môùi  • Böôùc 1: step = 1; //h[step]: ñoä daøi böôùc laëp moät phaàn töû ñöôïc so saùnh vôùi nhieàu phaàn töû khaùc tröôùc • Böôùc 2: Trong khi (step ≤ k) //ñoä daøi böôùc ñoù khoâng ôû cuøng daõy con vôùi noù. coøn >1 • Thuaät toaùn döøng sau khi saép xong daõy con vôùi len = 1, thuaät toaùn luùc naøy thöïc hieän nhö thuaät toaùn cheøn tröïc • Böôùc 21: len = h[step]; //laáy ñoä daøi böôùc tieáp. Tuy nhieân, phaàn lôùn caùc phaàn töû trong daõy ñaõ coù • Böôùc 22: Laëp vôùi i=len+1 N //saép xeáp caùc daõy lieân thöù töï boä phaän. //ñôùi böôùc len Cheøn a[i] vaøo daõy lieân ñôùi böôùc len; • Caùc phaàn töû treân cuøng moät daõy con caùch nhau len vò trí ñöôïc goïi laø cuøng daõy lieân ñôùi böôùc len. • Böôùc 23: step ++; //Heát laëp 117 118 Shell sort – Ví duï Shell sort – Ví duï h = (5, 3, 1); k = 3 h = (5, 3, 1); k = 3 len = 5; len = 5; joint curr 1 2345678 1 2345678 12 2 8 5 1 6 4 15 6 2 8 5 1 12 4 15 119 120
31. Shell sort – Ví duï Shell sort – Ví duï h = (5, 3, 1); k = 3 h = (5, 3, 1); k = 3 len = 3 len = 3 joint curr joint joint curr 1 2345678 1 2345678 6 2 15 5 1 12 4 8 5 1 12 6 2 15 4 8 121 122 Shell sort – Ví duï Shell sort – Ví duï h = (5, 3, 1); k = 3 h = (5, 3, 1); k = 3 len = 3 len = 1 joint jointcurr joint 1 2345678 1 2345678 4 1 12 5 2 15 6 8 4 1 12 5 2 15 6 8 123 124
32. Shell sort – Ví duï Shell sort – Ví duï h = (5, 3, 1); k = 3 len = 1 joint joint joint joint jointcurr joint joint 1 2345678 1 2345678 1 4 5 12 2 15 6 8 1 2 4 5 6 8 12 15 125 126 Shell sort – Caøi ñaët Shell sort – Ñaùnh giaù giaûi thuaät int h[MAXK], k; void ShellSort(int a[], int N) { • Yeáu toá quyeát ñònh tính hieäu quaû cuûa thuaät int step, i, pos, x, len; toaùn: for (step = 0 ; step h vaø h = 1 for(pos=i;(pos-len>=0)&&(x<a[pos-len]);pos-=len) i i+1 k a[pos] = a[pos-len]; a[pos] = x; } } 127 128 }
33. Shell sort – Ñaùnh giaù giaûi thuaät Shell sort – Ñaùnh giaù giaûi thuaät • Chöa coù tieâu chuaån roõ raøng trong vieäc löïa choïn daõy giaù trò khoaûng caùch toát nhaát. Moät gôïi yù: daõy ñöôïc • Vieäc ñaùnh giaù giaûi thuaät Shellsort daãn ñeán choïn khoâng neân coù caùc soá laø boäi soá cuûa nhau. nhöõng vaán ñeà toaùn hoïc raát phöùc taïp, thaäm chí moät soá chöa ñöôïc chöùng minh. • Moät soá daõy ñöôïc Knuth ñeà nghò : • Hieäu quaû cuûa thuaät toaùn coøn phuï thuoäc vaøo h = (h -1)/3 vaøh = 1, k = log n-1 i i-1 k 3 daõy caùc ñoä daøi ñöôïc choïn. ví duï: 121, 40, 13, 4, 1 • Trong tröôøng hôïp choïn daõy ñoä daøi theo coâng hay thöùc hi = (hi-1 -1)/2 vaøhk = 1, k = log2n-1 hi = (hi-1 -1)/2 vaøhk = 1, k = log2N-1 ví duï: 15, 7, 3, 1 thì giaûi thuaät coù ñoä phöùc taïp ≈ n1,2 aj > Sắp xếp dựa trên phân hoạch (*) ak chæ caàn thöïc hieän 1 laàn ñoåi choå (ai, ak): thuaät Quick sort toaùn khoâng laøm ñöôïc. – Ñoä phöùc taïp cuûa thuaät toaùn O(N2)  khi N ñuû lôùn thuaät toaùn seõ raát chaäm  YÙ töôûng: phaân chia daõy thaønh caùc ñoaïn con  taän duïng ñöôïc caùc pheùp ñoåi choã daïng (*) vaø laøm giaûm ñoä daøi daõy khi saép xeáp  caûi thieän ñaùng keå ñoä phöùc taïp cuûa thuaät toaùn. 132
34. Quick sort – YÙ töôûng Quick sort – YÙ töôûng • Giaûi thuaät QuickSort saép xeáp daõy a1, a2 , aN döïa treân vieäc phaân hoaïch daõy ban ñaàu thaønh 3 phaàn : – Phaàn 1: Goàm caùc phaàn töû coù giaù trò khoâng lôùn hôn x – Phaàn 2: Goàm caùc phaàn töû coù giaù trò baèng x • Ñoaïn thöù 2 ñaõ coù thöù töï. – Phaàn 3: Goàm caùc phaàn töû coù giaù trò khoâng beù hôn x • Neáu caùc ñoaïn 1 vaø 3 chæ coù 1 phaàn töû thì chuùng cuõng vôùi x laø giaù trò cuûa moät phaàn töû tuøy yù trong daõy ñaõ coù thöù töï, khi ñoù daõy con ban ñaàu ñaõ ñöôïc saép. • Ngöôïc laïi, neáu caùc ñoaïn 1 vaø 3 coù nhieàu hôn 1 phaàn ban ñaàu. töû thì daõy con ban ñaàu chæ coù thöù töï khi caùc ñoaïn 1, 3 • Sau khi thöïc hieän phaân hoaïch, daõy ban ñaàu ñöôïc ñöôïc saép. phaân thaønh 3 ñoaïn: • Ñeå saép xeáp caùc ñoaïn 1 vaø 3, ta laàn löôït tieán haønh vieäc phaân hoaïch töøng daõy con theo cuøng phöông phaùp – 1. ak ≤ x , vôùi k = 1 j phaân hoaïch daõy ban ñaàu vöøa trình baøy – 2. ak = x , vôùi k = j+1 i-1 ≥ – 3. ak x , vôùi k = i N 133 134 Quick sort – Giaûi thuaät Quick sort – Phaân hoaïch daõy //input: daõy con aleft, , aright //input: daõy con (a, left, right) //output: daõy con chia thaønh 3 ñoaïn: ñoaïn 1 ≤ ñoaïn 2 ≤ ñoaïn 3 //output: daõy con (a, left, right) ñöôïc saép taêng daàn • Böôùc 1: Choïn tuøy yù moät phaàn töû a[p] trong daõy con laø giaù trò moác: • Böôùc 1: Neáu left ≥ right //daõy coù ít hôn 2 phaàn töû x = a[p]; Keát thuùc; //daõy ñaõ ñöôïc saép xeáp • Böôùc 2: Duyeät töø 2 ñaàu daõy ñeå phaùt hieän vaø hieäu chænh caëp phaàn töû a[i], a[j] vi phaïm ñieàu kieän • Böôùc 2: Phaân hoaïch daõy aleft aright thaønh caùc – Böôùc 21: i = left; j = right; ñoaïn: aleft aj,aj+1 ai-1,ai Aright – Böôùc 22: Trong khi (a[i] x) j ; //Ñoaïn 1 x - Ñoaïn 2: aj+1 ai-1 = x - Ñoaïn 3: ai aright x – Böôùc 24: Neáu i<= j // a[i] ≥ x ≥ a[j] maø a[j] ñöùng sau a[i] • Böôùc 3: Saép xeáp ñoaïn 1: aleft aj • Hoaùn vò (a[i],a[j]); i++; j ; – Böôùc 25: Neáu i < j: Laëp laïi Böôùc 22.//chöa xeùt heát maûng • Böôùc 4: Saép xeáp ñoaïn 3: ai aright //Heát duyeät 135 136
35. Quick sort – Ví duï Quick sort – Ví duï Phaân hoaïch daõy Phaân hoaïch daõy X 5 X 5 i j i j 1 2345678 1 2345678 12 2 8 5 1 6 4 15 4 2 8 5 1 6 12 15 left right left right STOP STOP STOP STOP Not less thanNot X greater than X Not less thanNot X greater than X 137 138 Quick sort – Ví duï Quick sort – Ví duï Phaân hoaïch daõy X 6 j i i j 1 2345678 1 2345678 4 2 1 5 8 6 12 15 1 2 4 5 8 6 12 15 left right left right Saép xeáp ñoaïn 3 STOP STOP Not less thanNot X greater than X 139 140
36. Quick sort – Ví duï Shell sort – Ví duï j i 1 2345678 1 2345678 1 2 4 5 6 8 12 15 1 2 4 5 6 8 12 15 left right Saép xeáp ñoaïn 3 141 142 Quick sort – Caøi ñaët Quick sort – Ñaùnh giaù giaûi thuaät void QuickSort(int a[], int left, int right) { Nhaän xeùt: int i, j, x; • Veà nguyeân taéc, coù theå choïn giaù trò moác x laø moät phaàn töû if (left ≥ right) return; x = a[(left+right)/2]; // choïn phaàn töû giöõa laøm giaù trò moác tuøy yù trong daõy, nhöng ñeå ñôn giaûn, phaàn töû coù vò trí i = left; j = right; giöõa thöôøng ñöôïc choïn, khi ñoù p = (l +r)/ 2. while(i x) j ; if(i <= j) { – Soá laàn phaân hoaïch seõ ít nhaát neáu ta choïn ñöôïc x laø phaàn töû Swap(a[i], a[j]); trung vò (median), nhieàu nhaát neáu x laø cöïc trò cuûa daõy. i++ ; j ; – Tuy nhieân do chi phí xaùc ñònh phaàn töû median quaù cao neân trong } thöïc teá ngöôøi ta khoâng choïn phaàn töû naøy maø choïn phaàn töû naèm } chính giöõa daõy laøm moác vôùi hy voïng noù coù theå gaàn vôùi giaù trò QuickSort(a, left, j); median. QuickSort(a, i, right); } 143 144
37. Quick sort – Ñaùnh giaù giaûi thuaät Quick sort – Ñaùnh giaù giaûi thuaät • Ñoä phöùc taïp thuaät toaùn: Hieäu quaû phuï thuoäc vaøo vieäc choïn giaù trò moác: – Tröôøng hôïp toát nhaát: moãi laàn phaân hoaïch ñeàu choïn Tröôøng Ñoä phöùc taïp phaàn töû median laøm moác, khi ñoù daõy ñöôïc phaân chia hôïp thaønh 2 phaàn baèng nhau vaø caàn log2(n) laàn phaân hoaïch thì saép xeáp xong. Toát nhaát O(NlogN) – Neáu moãi laàn phaân hoaïch choïn phaàn töû coù giaù trò cöïc ñaïi (hay cöïc tieåu) laø moác  daõy seõ bò phaân chia Trung O(NlogN) thaønh 2 phaàn khoâng ñeàu: moät phaàn chæ coù 1 phaàn bình töû, phaàn coøn laïi goàm (n-1) phaàn töû, do vaäy caàn phaân 2) hoaïch n laàn môùi saép xeáp xong. Xaáu nhaát O(N 145 146 Merge sort – YÙ töôûng • Giaûi thuaät Merge sort saép xeáp daõy a1, a2, , an döïa treân nhaän xeùt sau: Sắp xếp theo phương pháp Trộn trực tiếp – Moãi daõy a1, a2, , an baát kyø laø moät taäp hôïp caùc daõy Merge Sort con lieân tieáp maø moãi daõy con ñeàu ñaõ coù thöù töï. • Ví duï: daõy 12, 2, 8, 5, 1, 6, 4, 15 coù theå coi nhö goàm 5 daõy con khoâng giaûm (12); (2, 8); (5); (1, 6); (4, 15). – Daõy ñaõ coù thöù töï coi nhö coù 1 daõy con. Höôùng tieáp caän: tìm caùch laøm giaûm soá daõy con khoâng giaûm cuûa daõy ban ñaàu. 148
38. Merge sort – YÙ töôûng Merge sort – Giaûi thuaät • Caùc vaán ñeà caàn giaûi quyeát: //input: daõy (a, N) – Phöông aùn phaân hoaïch daõy ban ñaàu thaønh caùc daõy con. – Phöông aùn laøm giaûm soá daõy con. //output: daõy (a, N) ñöôïc saép taêng daàn • Phaân hoaïch daõy ban ñaàu thaønh caùc daõy con taêng • Böôùc 1 : k = 1; // daõy con coù 1 phaàn töû laø daõy khoâng daàn: giaûm – Phöông aùn 1: Phaân hoaïch daõy theo caùc ñöôøng chaïy  • Böôùc 2 : Laëp trong khi (k < N) // daõy coøn hôn 1 daõy saép xeáp troän töï nhieân. con – Phöông aùn 2: Phaân hoaïch thaønh caùc daõy con coù soá phaàn töû baèng nhau (1, 2, 4, )  saép xeáp troän tröïc tieáp. – Böôùc 21: Phaân phoái ñeàu luaân phieân daõy a1, a2, , an thaønh • Laøm giaûm soá daõy con: 2 daõy b, c theo töøng nhoùm k phaàn töû lieân tieáp nhau. //b = a1, , ak, a2k+1, , a3k, – Caùc daõy con taêng daàn seõ ñöôïc taùch ra 2 daõy phuï theo //c = a , , a , a , , a , nguyeân taéc phaân phoái ñeàu luaân phieân. k+1 2k 3k+1 4k – Troän töøng caëp daõy con cuûa hai daõy phuï thaønh moät daõy – Böôùc 22: Troän töøng caëp daõy con goàm k phaàn töû cuûa 2 daõy con cuûa daõy ban ñaàu  daõy môùi coù soá löôïng daõy con b, c vaøo a. giaûm ñi so vôùi daõy ban ñaàu. – Böôùc 23: k = k*2; 149 150 //Heát laëp Merge sort – Ví duï Merge sort – Ví duï k = 1; Phaân phoái ñeàu luaân phieân k = 1; Phaân phoái ñeàu luaân phieân 1 2345678 1 2345678 12 2 8 5 1 6 4 15 12 2 8 5 1 6 4 15 151 152
39. Merge sort – Ví duï Merge sort – Ví duï k = 1; Troän töøng caëp ñöôøng chaïy k = 1; Troän töøng caëp ñöôøng chaïy 1 2345678 1 2345678 12 8 1 4 12 8 1 4 2 5 6 15 2 5 6 15 153 154 Merge sort – Ví duï Merge sort – Ví duï k = 2; Phaân phoái ñeàu luaân phieân k = 2; Troän töøng caëp ñöôøng chaïy 1 2345678 1 2345678 2 12 5 8 1 6 4 15 2 12 1 6 5 8 4 15 155 156
40. Merge sort – Ví duï Merge sort – Ví duï k = 2; Troän töøng caëp ñöôøng chaïy k = 4; Phaân phoái ñeàu luaân phieân 1 2345678 1 2345678 2 5 8 12 1 4 6 15 2 12 1 6 5 8 4 15 157 158 Merge sort – Ví duï Merge sort – Ví duï k = 4; Troän töøng caëp ñöôøng chaïy k = 4; Troän töøng caëp ñöôøng chaïy 1 2345678 1 2345678 2 5 8 12 2 5 8 12 1 4 6 15 1 4 6 15 159 160
41. Merge sort – Ví duï Merge sort – Ví duï k = 8; 1 2345678 1 2345678 1 2 4 5 6 8 12 15 1 2 4 5 6 8 12 15 STOP Only one subarray 161 162 Merge Sort – Caøi ñaët Merge sort – Caøi ñaët //khai baùo 2 maûng phuï • Döõ lieäu hoã trôï: 2 maûng b, c: int b[MAX], c[MAX], nb, nc; int b[MAX], c[MAX], nb, nc; • Caùc haøm caàn caøi ñaët: – MergeSort: Saép xeáp maûng (a, N) taêng daàn void MergeSort(int a[], int N) void MergeSort(int a[], int N); { – Distribute: Phaân phoái ñeàu luaân phieân caùc daõy con ñoä daøi k töø int k; maûng a vaøo hai maûng b vaø c void Distribute(int a[], int N, for (k = 1; k < N; k *= 2) int &nb, int &nc, int k); { – Merge: Troän maûng b vaø maûng c vaøo maûng a Distribute(a, N, nb, nc, k); void Merge(int a[], int nb, int nc, int k); Merge(a, nb, nc, k); – MergeSubarr: Troän 1 caëp daõy con töø b vaø c vaøo a void MergeSubarr(int a[], int nb, int nc, } int &pa, int &pb, int &pc, int k); } 163 164
42. Merge sort – Caøi ñaët Merge sort – Caøi ñaët void Distribute(int a[], int N, int &nb, int &nc, int k) void Merge(int a[], int nb, int nc, int k) { { int i, pa, pb, pc; int pa, pb, pc; pa = pb = pc = 0; while (pa < N) pa = pb = pc = 0; { while ((pb < nb) && (pc < nc)) for (i=0; (pa<N) && (i<k); i++, pa++, pb++) MergeSubarr(a, nb, nc, pa, pb, pc, k); b[pb] = a[pa]; while (pb < nb) for (i=0; (pa<N) && (i<k); i++, pa++, pc++) a[pa ++] = b[pb ++]; c[pc] = a[pa]; } while (pc < nc) nb = pb; nc = pc; a[pa ++] = c[pc ++]; } } 165 166 Merge sort – Caøi ñaët Merge Sort – Ñaùnh giaù giaûi thuaät void MergeSubarr(int a[], int nb, int nc, int &pa, int &pb, int &pc, int k) Giaûi thuaät troän tröïc tieáp laø phöông phaùp troän ñôn giaûn { nhaát: int rb, rc; • Vieäc phaân hoaïch thaønh caùc daõy con chæ laø taùch daõy thaønh rb = min(nb, pb+k); rc = min(nc, pb+k); caùc daõy con khoâng giaûm ñoä daøi k. while ((pb < rb) && (pc < rc)) • Ñoä daøi cuûa daõy con laø 1, 2, 4, 8, ñaûm baûo daõy con luoân laø if (b[pb] < c[pc]) daõy con khoâng giaûm sau moãi böôùc taùch - troän. a[pa ++] = b[pb ++]; else a[pa ++] = c[pc ++]; • Khoâng söû duïng thoâng tin veà thöù töï cuûa daõy ban ñaàu while (pb < rb)  2 heä quaû: a[pa ++] = b[pb ++]; – Ñoä phöùc taïp thuaät toaùn khoâng phuï thuoäc vaøo daõy ban ñaàu. while (pc < rc) – Moät daõy con khoâng giaûm ñang coù saün bò chia nhoû thaønh caùc daõy a[pa ++] = c[pc ++]; khoâng caàn thieát  caûi tieán thaønh thuaät toaùn: Troän töï nhieân } (Natural Merge sort). 167 168
43. Merge Sort – Ñaùnh giaù giaûi thuaät Merge Sort – Ñaùnh giaù giaûi thuaät • Soá laàn thöïc hieän vieäc chia luaân phieân vaø troän: • Moät nhöôïc ñieåm lôùn nöõa cuûa caùc thuaät toaùn Sau moãi laàn taùch – troän, ñoä daøi K cuûa daõy con troän laø khi caøi ñaët thuaät toaùn ñoøi hoûi theâm taêng gaáp ñoâi  Soá laàn taùch – troän trong khoâng gian boä nhôù ñeå löu caùc daõy phuï b, c. • Haïn cheá naøy khoù chaáp nhaän trong thöïc teá vì thuaät toaùn: log2n . • Chi phí thöïc hieän taùch - troän tæ leä thuaän vôùi n. caùc daõy caàn saép xeáp thöôøng coù kích thöôùc lôùn.  Chi phí thöïc hieän cuûa giaûi thuaät MergeSort • Vì vaäy thuaät toaùn troän thöôøng ñöôïc duøng ñeå laø O(nlog n). saép xeáp caùc caáu truùc döõ lieäu khaùc phuø hôïp 2 hôn nhö danh saùch lieân keát hoaëc file. 169 170 Saép xeáp theo phöông phaùp troän tröïc tieáp Thuaät Saép xeáp theo phöông phaùp troän tröïc tieáp Thuaät toaùn troän töï nhieân Natural Merge sort toaùn troän töï nhieân Natural Merge sort • Moät ñöôøng chaïy cuûa daõy soá a laø moät daõy con khoâng • Thuaät toaùn troän töï nhieân khaùc thuaät toaùn giaûm cuûa cöïc ñaïi cuûa a. Nghóa laø, ñöôøng chaïy troän tröïc tieáp ôû choã thay vì luoân cöùng nhaéc r = (a , a , , a ) phaûi thoûa ñieàu kieän: i i+1 j phaân hoaïch theo daõy con coù chieàu daøi k, vieäc phaân hoaïch seõ theo ñôn vò laø ñöôøng chaïy. ta ⎧a ≤ a ∀k ∈[i, j) k k+1 chæ caàn bieát soá ñöôøng chaïy cuûa a sau laàn phaân ⎪ ⎨ai a cuûa thuaät toaùn vì daõy ñaõ coù thöù töï laø daõy chi ⎩ j j+1 • Ví duï daõy 12, 2, 8, 5, 1, 6, 4, 15 coù theå coi nhö goàm 5 coù moät ñöôøng chaïy. ñöôøng chaïy (12); (2, 8); (5); (1, 6); (4, 15). 171 172
44. Saép xeáp theo phöông phaùp troän tröïc tieáp Thuaät toaùn troän töï nhieân Natural Merge sort • Böôùc 1 : // Chuaån bò – r = 0; // r duøng ñeå ñeám soá döôøng chaïy • Böôùc 2 : Taùch daõy a1, a2, , an thaønh 2 daõy b, c theo nguyeân taéc luaân phieân töøng ñöôøng chaïy: Sắp xếp theo phương pháp Cơ số – Böôùc 2.1 : • Phaân phoái cho b moät ñöôøng chaïy; r = r+1; Radix Sort • Neáu a coøn phaàn töû chöa phaân phoái – Phaân phoái cho c moät ñöôøng chaïy; r = r+1; – Böôùc 2.2 : • Neáu a coøn phaàn töû: quay laïi böôùc 2.1; • Böôùc 3 : – Troän töøng caëp ñöôøng chaïy cuûa 2 daõy b, c vaøo a. • Böôùc 4 : – Neáu r <= 2 thì trôû laïi böôùc 2; Ngöôïc laïi: Döøng. 173 Saép xeáp theo phöông phaùp cô soá Radix Sort Saép xeáp theo phöông phaùp cô soá Radix Sort • Radix Sort laø moät thuaät toaùn tieáp caän theo moät • Ñeå chuyeån moät khoái löôïng thö lôùn ñeán tay ngöôøi nhaän höôùng hoaøn toaøn khaùc. ôû nhieàu ñòa phöông khaùc nhau, böu ñieän thöôøng toå chöùc moät heä thoáng phaân loaïi thö phaân caáp. • Neáu nhö trong caùc thuaät toaùn khaùc, cô sôû ñeå saép • Tröôùc tieân, caùc thö ñeán cuøng moät tænh, thaønh phoá seõ xeáp luoân laø vieäc so saùnh giaù trò cuûa 2 phaàn töû thì ñöôïc saép chung vaøo moät loâ ñeå göûi ñeán tænh thaønh töông Radix Sort laïi döïa treân nguyeân taéc phaân loaïi thö öùng. cuûa böu ñieän. Vì lyù do ñoù Radix Sort coøn coù teân laø • Böu ñieän caùc tænh thaønh naøy laïi thöïc hieän coâng vieäc Postman’s sort. töông töï. Caùc thö ñeán cuøng moät quaän, huyeän seõ ñöôïc • Radix Sort khoâng heà quan taâm ñeán vieäc so saùnh giaù xeáp vaøo chung moät loâ vaø göûi ñeán quaän, huyeän töông trò cuûa phaàn töû maø baûn thaân vieäc phaân loaïi vaø trình öùng. töï phaân loaïi seõ taïo ra thöù töï cho caùc phaàn töû. • Cöù nhö vaäy, caùc böùc thö seõ ñöôïc trao ñeán tay ngöôøi nhaän moät caùch coù heä thoáng maø coâng vieäc saép xeáp thö 175 khoâng quaù naëng nhoïc. 176
45. Saép xeáp theo phöông phaùp cô soá Radix Sort Saép xeáp theo phöông phaùp cô soá Radix Sort • Böôùc 1 :// k cho bieát chöõ soá duøng ñeå phaân loaïi hieän • Moâ phoûng laïi qui trình treân, ñeå saép xeáp daõy haønh a1, a2, , an, giaûi thuaät Radix Sort thöïc hieän – k = 0; // k = 0: haøng ñôn vò; k = 1: haøng chuïc; nhö sau: • Böôùc 2 : //Taïo caùc loâ chöùa caùc loaïi phaàn töû khaùc nhau – Tröôùc tieân, ta coù theå giaû söû moãi phaàn töû ai trong – Khôûi taïo 10 loâ B , B , , B roãng; daõy a1, a2, , an laø moät soá nguyeân coù toái ña m chöõ 0 1 9 soá. • Böôùc 3 : – Ta phaân loaïi caùc phaàn töû laàn löôït theo caùc chöõ soá – For i = 1 n do • Ñaët a vaøo loâ B vôùi t: chöõ soá thöù k cuûa a ; haøng ñôn vò, haøng chuïc, haøng traêm, töông töï i t i • Böôùc 3 : vieäc phaân loaïi thö theo tænh thaønh, quaän huyeän, – Noái B , B , , B laïi (theo ñuùng trình töï) thaønh a. phöôøng xaõ, . 0 1 9 • Böôùc 4 : 177 – k = k+1;Neáu k < m thì trôû laïi böôùc 2. Ngöôïc laïi: Döøng178 Saép xeáp theo phöông phaùp cô soá Radix Sort Saép xeáp theo phöông phaùp cô soá Radix Sort 179 180
46. Saép xeáp theo phöông phaùp cô soá Radix Sort Saép xeáp theo phöông phaùp cô soá Radix Sort 181 182 Saép xeáp theo phöông phaùp cô soá Radix Sort Saép xeáp theo phöông phaùp cô soá Radix Sort • Ñaùnh giaù giaûi thuaät: – Vôùi moät daõy n soá, moãi soá coù toái ña m chöõ soá, thuaät toaùn thöïc hieän m laàn caùc thao taùc phaân loâ vaø gheùp loâ. – Trong thao taùc phaân loâ, moãi phaàn töû chæ ñöôïc xeùt ñuùng moät laàn, khi gheùp cuõng vaäy. – Nhö vaäy, chi phí cho vieäc thöïc hieän thuaät toaùn hieån nhieân laø O(2mn) = O(n). 183 184
47. Saép xeáp theo phöông phaùp cô soá Radix Sort Saép xeáp theo phöông phaùp cô soá Radix Sort  Nhaän xeùt: Nhaän xeùt: – Sau laàn phaân phoái thöù k caùc phaàn töû cuûa A vaøo – Thuaät toaùn khoâng coù tröôøng hôïp xaáu nhaát vaø toát caùc loâ B0, B1, , B9, vaø laáy ngöôïc trôû ra, neáu chæ nhaát. Moïi daõy soá ñeàu ñöôïc saép vôùi chi phí nhö xeùt ñeán k+1 chöõ soá cuûa caùc phaàn töû trong A, ta seõ nhau neáu chuùng coù cuøng soá phaàn töû vaø caùc khoùa → coù moät maûng taêng daàn nhôø trình töï laáy ra töø 0 coù cuøng chieàu daøi. 9. Nhaän xeùt naøy baûo ñaûm tính ñuùng ñaén cuûa thuaät – Thuaät toaùn caøi ñaët thuaän tieän vôùi caùc maûng vôùi toaùn. khoùa saép xeáp laø chuoãi (kyù töï hay soá) hôn laø khoùa – Thuaät toaùn coù ñoä phöùc taïp tuyeán tính neân hieäu soá nhö trong ví duï do traùnh ñöôïc chi phí laáy caùc quaû khi saép daõy coá raát nhieàu phaàn töû, nhaát laø khi chöõ soá cuûa töøng soá. khoùa saép xeáp khoâng quaù daøi so vôùi soá löôïng phaàn töû (ñieàu naøy thöôøng gaëp trong thöïc teá). 185 186 Saép xeáp theo phöông phaùp cô soá Radix Sort Saép xeáp theo phöông phaùp cô soá Radix Sort Nhaän xeùt: Nhaän xeùt: – Soá löôïng loâ lôùn (10 khi duøng soá thaäp phaân, 26 khi – Ngöôøi ta cuõng duøng phöông phaùp phaân loâ theo duøng chuoãi kyù töï tieáng Anh, ) nhöng toång kích bieåu dieãn nhò phaân cuûa khoùa saép xeáp. Khi ñoù ta thöôùc cuûa taát caû caùc loâ chæ baèng daõy ban ñaàu neân coù theå duøng hoaøn toaøn caáu truùc döõ lieäu maûng ñeå ta khoâng theå duøng maûng ñeå bieåu dieãn B. Nhö vaäy, bieåu dieãn B vì chæ caàn duøng hai loâ B0 vaø B1. Tuy phaûi duøng caáu truùc döõ lieäu ñoäng ñeå bieåu dieãn B nhieân, khi ñoù chieàu daøi khoùa seõ lôùn. Khi saép caùc ⇒ Radix Sort raát thích hôïp cho saép xeáp treân daõy khoâng nhieàu phaàn töû, thuaät toaùn Radix sort danh saùch lieân keát. seõ maát öu theá so vôùi caùc thuaät toaùn khaùc. 187 188