Cơ sở dữ liệu toàn tập

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