Bài giảng Sắp xếp

Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 149 Chöông 8 – SAÉP XEÁP Chöông naøy giôùi thieäu moät soá phöông phaùp saép xeáp cho caû danh saùch lieân tuïc vaø danh saùch lieân keát. 8.1. Giôùi thieäu Ñeå truy xuaát thoâng tin nhanh choùng vaø chính xaùc, ngöôøi ta thöôøng saép xeáp thoâng tin theo moät traät töï hôïp lyù naøo ñoù. Coù moät soá caáu truùc döõ lieäu maø ñònh nghóa cuûa chuùng ñaõ bao haøm traät töï cuûa caùc phaàn töû, khi ñoù moãi phaàn töû khi theâm vaøo ñeàu phaûi ñaûm baûo traät töï naøy. Trong chöông naøy chuùng ta seõ tìm hieåu vieäc saép xeáp caùc danh saùch chöa coù thöù töï trôû neân coù thöù töï. Vì saép xeáp coù vai troø quan troïng neân coù raát nhieàu phöông phaùp ñöôïc ñöa ra ñeå giaûi quyeát baøi toaùn naøy. Caùc phöông phaùp naøy khaùc nhau ôû nhieàu ñieåm, trong ñoù ñieåm quan troïng nhaát laø döõ lieäu caàn saép xeáp naèm toaøn boä trong boä nhôù chính (töông öùng caùc giaûi thuaät saép xeáp noäi) hay coù moät phaàn naèm trong thieát bò löu tröõ ngoaøi (töông öùng caùc giaûi thuaät saép xeáp ngoaïi). Trong chöông naøy chuùng ta chæ xem xeùt moät soá giaûi thuaät saép xeáp noäi. Chuùng ta seõ söû duïng caùc lôùp ñaõ coù ôû chöông 4 vaø chöông 7. Ngoaøi ra, trong tröôøng hôïp khi coù nhieàu phaàn töû khaùc nhau coù cuøng khoùa thì caùc giaûi thuaät saép xeáp khaùc nhau seõ cho ra nhöõng thöù töï khaùc nhau giöõa chuùng, vaø ñoâi khi söï khaùc nhau naøy cuõng coù aûnh höôûng ñeán caùc öùng duïng. Trong caùc giaûi thuaät tìm kieám, khoái löôïng coâng vieäc phaûi thöïc hieän coù lieân quan chaët cheõ vôùi soá laàn so saùnh caùc khoùa. Trong caùc giaûi thuaät saép xeáp thì ñieàu naøy cuõng ñuùng. Ngoaøi ra, caùc giaûi thuaät saép xeáp coøn phaûi di chuyeån caùc phaàn töû. Coâng vieäc naøy cuõng chieám nhieàu thôøi gian, ñaëc bieät khi caùc phaàn töû coù kích thöôùc lôùn ñöôïc löu tröõ trong danh saùch lieân tuïc. Ñeå coù theå ñaït ñöôïc hieäu quaû cao, caùc giaûi thuaät saép xeáp thöôøng phaûi taän duïng caùc ñaëc ñieåm rieâng cuûa töøng loaïi caáu truùc döõ lieäu. Chuùng ta seõ vieát caùc giaûi thuaät saép xeáp döôùi daïng caùc phöông thöùc cuûa lôùp List. template class Sortable_list:public List { public: // Khai baùo cuûa caùc phöông thöùc saép xeáp ñöôïc theâm vaøo ñaây private: // Caùc haøm phuï trôï. }; Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 150 Chuùng ta coù theå söû duïng baát kyø daïng hieän thöïc naøo cuûa lôùp List trong chöông 4. Caùc phaàn töû döõ lieäu trong Sortable_list coù kieåu laø Record. Nhö ñaõ giôùi thieäu trong chöông 7, Record coù caùc tính chaát sau ñaây: • Moãi maãu tin coù moät khoaù ñi keøm. • Caùc khoùa coù theå ñöôïc so saùnh vôùi nhau baèng caùc toaùn töû so saùnh. • Moät maåu tin coù theå ñöôïc chuyeån ñoåi töï ñoäng thaønh moät khoùa. Do ñoù coù theå so saùnh caùc maãu tin vôùi nhau hoaëc so saùnh maãu tin vôùi khoaù thoâng qua vieäc chuyeån ñoåi maãu tin veà khoùa lieân quan ñeán noù. 8.2. Saép xeáp kieåu cheøn (Insertion Sort) Phöông phaùp saép xeáp chen vaøo döïa treân yù töôûng cheøn phaàn töû vaøo danh saùch ñaõ coù thöù töï. 8.2.1. Cheøn phaàn töû vaøo danh saùch ñaõ coù thöù töï Ñònh nghóa danh saùch coù thöù töï ñaõ ñöôïc trình baøy trong chöông 7. Vôùi caùc danh saùch coù thöù töï, moät soá taùc vuï chæ söû duïng khoùa cuûa phaàn töû chöù khoâng söû duïng vò trí cuûa phaàn töû: • retrieve: truy xuaát moät phaàn töû coù khoùa cho tröôùc. • insert: cheøn moät phaàn töû coù khoùa cho tröôùc sao cho danh saùch vaãn coøn thöù töï, vò trí cuûa phaàn töû môùi ñöôïc xaùc ñònh bôûi khoùa cuûa noù. Pheùp theâm vaøo vaø pheùp truy xuaát coù theå khoâng cho keát quaû duy nhaát trong tröôøng hôïp coù nhieàu phaàn töû truøng khoùa. Pheùp truy xuaát phaàn töû döïa treân khoùa chính laø pheùp tìm kieám ñaõ ñöôïc trình baøy trong chöông 7. Ñeå theâm phaàn töû môùi vaøo danh saùch lieân tuïc ñaõ coù thöù töï, caùc phaàn töû seõ ñöùng sau noù phaûi ñöôïc dòch chuyeån ñeå taïo choã troáng. Chuùng ta caàn thöïc hieän pheùp Hình 8.1 – Cheøn phaàn töû vaøo danh saùch ñaõ coù thöù töï. Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 151 tìm kieám ñeå tìm vò trí chen vaøo. Vì danh saùch ñaõ coù thöù töï neân ta coù theå söû duïng pheùp tìm kieám nhò phaân. Tuy nhieân, do thôøi gian caàn cho vieäc di chuyeån caùc phaàn töû lôùn hôn nhieàu so vôùi thôøi gian tìm kieám, neân vieäc tieát kieäm thôøi gian tìm kieám cuõng khoâng caûi thieän thôøi gian chaïy toaøn boä giaûi thuaät ñöôïc bao nhieâu. Neáu vieäc tìm kieám tuaàn töï töø cuoái danh saùch coù thöù töï ñöôïc thöïc hieän ñoàng thôøi vôùi vieäc di chuyeån phaàn töû, thì chi phí cho moät laàn chen moät phaàn töû môùi laø toái thieåu. 8.2.2. Saép xeáp kieåu cheøn cho danh saùch lieân tuïc Taùc vuï theâm moät phaàn töû vaøo danh saùch coù thöù töï laø cô sôû cuûa pheùp saép xeáp kieåu cheøn. Ñeå saép xeáp moät danh saùch chöa coù thöù töï, chuùng ta laàn löôït laáy ra töøng phaàn töû cuûa noù vaø duøng taùc vuï treân ñeå ñöa vaøo moät danh saùch luùc ñaàu laø roãng. Phöông phaùp naøy ñöôïc minh hoïa trong hình 8.2. Hình naøy chæ ra caùc böôùc caàn thieát ñeå saép xeáp moät danh saùch coù 6 töø. Nhìn hình veõ chuùng ta thaáy, phaàn danh saùch ñaõ coù thöù töï goàm caùc phaàn töû töø chæ soá sorted trôû leân treân, caùc phaàn töû töø chæ soá unsorted trôû xuoáng döôùi laø chöa coù thöù töï. Böôùc ñaàu tieân, töø “hen” ñöôïc xem laø ñaõ coù thöù töï do danh saùch coù moät phaàn töû ñöông nhieân laø danh saùch coù thöù töï. Taïi moãi böôùc, phaàn töû ñaàu tieân trong phaàn danh saùch beân döôùi ñöôïc laáy ra vaø cheøn vaøo vò trí thích hôïp trong phaàn danh saùch ñaõ coù thöù töï beân treân. Ñeå coù choã cheøn phaàn töû naøy, moät soá phaàn töû khaùc trong phaàn danh saùch ñaõ coù thöù töï ñöôïc di chuyeån veà phía cuoái danh saùch. Trong phöông thöùc duôùi ñaây, first_unsorted laø chæ soá phaàn töû ñaàu tieân trong phaàn danh saùch chöa coù thöù töï, vaø current laø bieán taïm naém giöõ phaàn töû naøy cho ñeán khi tìm ñöôïc choã troáng ñeå cheøn vaøo. Hình 8.2- Ví duï veà saép xeáp kieåu cheøn cho danh saùch lieân tuïc. Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 152 // Daønh cho danh saùch lieân tuïc trong chöông 4. template void Sortable_list::insertion_sort() /* post: Caùc phaàn töû trong danh saùch ñaõ ñöôïc saép xeáp theo thöù töï khoâng giaûm. uses: Caùc phöông thöùc cuûa lôùp Record. */ { int first_unsorted;//Chæ soá phaàn töû ñaàu tieân trong phaàn danh saùch chöa coù thöù töï. int position; // Chæ soá duøng cho vieäc di chuyeån caùc phaàn töû veà phía sau. Record current;// Naém giöõ phaàn töû ñang ñöôïc tìm choã cheøn vaøo phaàn danh saùch ñaõ coù thöù töï. for (first_unsorted = 1; first_unsorted < count; first_unsorted++) if (entry[first_unsorted] < entry[first_unsorted - 1]) { position = first_unsorted; current = entry[first_unsorted]; do { // Di chuyeån daàn caùc phaàn töû veà phía sau ñeå tìm choã troáng thích hôïp. entry[position] = entry[position - 1]; position--; } while (position > 0 && entry[position - 1] > current); entry[position] = current; } } Hình 8.3- Böôùc chính cuûa giaûi thuaät saép xeáp kieåu cheøn. Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 153 Vì danh saùch coù moät phaàn töû xem nhö ñaõ coù thöù töï neân voøng laëp treân bieán first_unsorted baét ñaàu vôùi phaàn töû thöù hai. Neáu phaàn töû naøy ñaõ ôû ñuùng vò trí thì khoâng caàn phaûi tieán haønh thao taùc naøo. Ngöôïc laïi, phaàn töû ñöôïc ñöa vaøo bieán current, voøng laëp do...while ñaåy caùc phaàn töû luøi veà sau moät vò trí cho ñeán khi tìm ñöôïc vò trí ñuùng cho current. Tröôøng hôïp vò trí ñuùng cuûa current laø ñaàu daõy caàn ñöôïc nhaän bieát rieâng bôûi ñieàu kieän thoaùt khoûi voøng laëp laø position==0. 8.2.3. Saép xeáp kieåu cheøn cho danh saùch lieân keát Vôùi danh saùch lieân keát, chuùng ta khoâng caàn di chuyeån caùc phaàn töû, do ñoù cuõng khoâng caàn baét ñaàu tìm kieám töø phaàn töû cuoái cuûa phaàn danh saùch ñaõ coù thöù töï. Hình 8.4 minh hoïa giaûi thuaät naøy. Con troû last_sorted chæ phaàn töû cuoái cuøng cuûa phaàn danh saùch ñaõ coù thöù töï, last_sorted->next chæ phaàn töû ñaàu tieân cuûa phaàn danh saùch chöa coù thöù töï. Ta duøng bieán first_unsorted ñeå chæ vaøo phaàn töû naøy vaø bieán current ñeå tìm vò trí thích hôïp cho vieäc cheøn phaàn töû *first_unsorted vaøo. Neáu vò trí ñuùng cuûa *first_unsorted laø ñaàu danh saùch thì noù ñöôïc cheøn vaøo vò trí naøy. Ngöôïc laïi, current ñöôïc di chuyeån veà phía cuoái danh saùch cho ñeán khi coù (current->entry >= first_unsorted->entry) vaø *first_unsorted ñöôïc theâm vaøo ngay tröôùc *current. Ñeå coù theå thöïc hieän vieäc theâm vaøo tröôùc current, chuùng ta caàn moät con troû trailing luoân ñöùng tröôùc current moät vò trí. Hình 8.4- Saép xeáp kieåu cheøn cho danh saùch lieân keát. Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 154 Nhö chuùng ta ñaõ bieát, phaàn töû caàm canh (sentinel) laø moät phaàn töû ñöôïc theâm vaøo moät ñaàu cuûa danh saùch ñeå ñaûm baûo raèng voøng laëp luoân keát thuùc maø khoâng caàn phaûi thöïc hieän boå sung moät pheùp kieåm tra naøo. Vì chuùng ta ñaõ coù last_sorted->next == first_unsorted, neân phaàn töû *first_unsorted ñoùng luoân vai troø cuûa phaàn töû caàm canh trong khi current tieán daàn veà phía cuoái phaàn danh saùch ñaõ coù thöù töï. Nhôø ñoù, ñieàu kieän döøng cuûa voøng laëp di chuyeån current luoân ñöôïc ñaûm baûo. Ngoaøi ra, danh saùch roãng hay danh saùch coù moät phaàn töû laø ñöông nhieân coù thöù töï, neân ta coù theå kieåm tra tröôùc deã daøng. Maëc duø cô cheá hieän thöïc cuûa saép xeáp kieåu cheøn cho danh saùch lieân keát vaø cho danh saùch lieân tuïc coù nhieàu ñieåm khaùc nhau nhöng veà yù töôûng thì hai phieân baûn naøy raát gioáng nhau. Ñieåm khaùc bieät lôùn nhaát laø trong danh saùch lieân keát vieäc tìm kieám ñöôïc thöïc hieän töø ñaàu danh saùch trong khi trong danh saùch lieân tuïc vieäc tìm kieám ñöôïc thöïc hieän theo chieàu ngöôïc laïi. // Daønh cho danh saùch lieân keát trong chöông 4. template void Sortable_list::insertion_sort() /* post: Caùc phaàn töû trong danh saùch ñaõ ñöôïc saép xeáp theo thöù töï khoâng giaûm. uses: Caùc phöông thöùc cuûa lôùp Record. */ { Node *first_unsorted, *last_sorted, *current, *trailing; if (head != NULL) { // Loaïi tröôøng hôïp danh saùch roãng vaø last_sorted = head; // tröôøng hôïp danh saùch chæ coù 1 phaàn töû. while (last_sorted->next != NULL) { first_unsorted = last_sorted->next; if (first_unsorted->entry entry) { // *first_unsorted ñöôïc cheøn vaøo ñaàu danh saùch. last_sorted->next = first_unsorted->next; first_unsorted->next = head; head = first_unsorted; } else { // Tìm vò trí thích hôïp. trailing = head; current = trailing->next; while (first_unsorted->entry > current->entry) { trailing = current; current = trailing->next; } // *first_unsorted ñöôïc cheøn vaøo giöõa *trailing vaø *current. Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 155 if (first_unsorted == current) last_sorted = first_unsorted; // vò trí ñang coù ñaõ ñuùng. else { last_sorted->next = first_unsorted->next; first_unsorted->next = current; trailing->next = first_unsorted; } } } } } Thôøi gian caàn thieát ñeå saép xeáp danh saùch duøng giaûi thuaät saép xeáp kieåu cheøn tæ leä vôùi bình phöông soá phaàn töû cuûa danh saùch. 8.3. Saép xeáp kieåu choïn (Selection Sort) Saép xeáp kieåu cheøn coù moät nhöôïc ñieåm lôùn. Sau khi moät soá phaàn töû ñaõ ñöôïc saép xeáp vaøo phaàn ñaàu cuûa danh saùch, vieäc saép xeáp moät phaàn töû phía sau ñoâi khi ñoøi hoûi phaûi di chuyeån phaàn lôùn caùc phaàn töû ñaõ coù thöù töï naøy. Moãi laàn di chuyeån, caùc phaàn töû chæ ñöôïc di chuyeån moät vò trí, do ñoù neáu moät phaàn töû caàn di chuyeån 20 vò trí ñeå ñeán ñöôïc vò trí ñuùng cuoái cuøng cuûa noù thì noù caàn ñöôïc di chuyeån 20 laàn. Neáu kích thöôùc cuûa moãi phaàn töû laø nhoû hoaëc chuùng ta söû duïng danh saùch lieân keát thì vieäc di chuyeån naøy khoâng caàn nhieàu thôøi gian laém. Nhöng neáu kích thöôùc moãi phaàn töû lôùn vaø danh saùch laø lieân tuïc thì thôøi gian di chuyeån caùc phaàn töû seõ raát lôùn. Nhö vaäy, neáu nhö moãi phaàn töû, khi caàn phaûi di chuyeån, ñöôïc di chuyeån ngay ñeán vò trí ñuùng sau cuøng cuûa noù thì giaûi thuaät seõ chaïy hieäu quaû hôn nhieàu. Sau ñaây chuùng ta trình baøy moät giaûi thuaät ñeå ñaït ñöôïc ñieàu ñoù. 8.3.1. Giaûi thuaät Hình 8.5- Ví duï saép xeáp kieåu choïn. Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 156 Hình 8.5 trình baøy moät ví duï saép xeáp 6 töø theo thöù töï cuûa baûng chöõ caùi. Taïi böôùc ñaàu tieân, chuùng ta tìm phaàn töû seõ ñöùng taïi vò trí cuoái cuøng trong danh saùch coù thöù töï vaø traùo ñoåi vò trí vôùi phaàn töû cuoái cuøng hieän taïi. Trong caùc böôùc keá tieáp, chuùng ta tieáp tuïc laëp laïi coâng vieäc treân vôùi phaàn coøn laïi cuûa danh saùch khoâng keå caùc phaàn töû ñaõ ñöôïc choïn trong caùc böôùc tröôùc. Khi phaàn danh saùch chöa ñöôïc saép xeáp chæ coøn laïi moät phaàn töû thì giaûi thuaät keát thuùc. Böôùc toång quaùt trong saép xeáp kieåu choïn ñöôïc minh hoïa trong hình 8.6. Caùc phaàn töû coù khoùa lôùn ñaõ ñöôïc saép theo thöù töï vaø ñaët ôû phaàn cuoái danh saùch. Caùc phaàn töû coù khoùa nhoû hôn chöa ñöôïc saép xeáp. Chuùng ta tìm trong soá nhöõng phaàn töû chöa ñöôïc saép xeáp ñeå laáy ra phaàn töû coù khoùa lôùn nhaát vaø ñoåi choã noù veà cuoái caùc phaàn töû naøy. Baèng caùch naøy, taïi moãi böôùc, moät phaàn töû ñöôïc ñöa veà ñuùng vò trí cuoái cuøng cuûa noù. 8.3.2. Saép xeáp choïn treân danh saùch lieân tuïc Saép xeáp choïn giaûm toái ña vieäc di chuyeån döõ lieäu do moãi böôùc ñeàu coù ít nhaát moät phaàn töû ñöôïc ñaët vaøo ñuùng vò trí cuoái cuøng cuûa noù. Vì vaäy saép xeáp kieåu choïn thích hôïp cho caùc danh saùch lieân tuïc coù caùc phaàn töû coù kích thöôùc lôùn. Neáu caùc phaàn töû coù kích thöôùc nhoû hay danh saùch coù hieän thöïc laø lieân keát thì saép xeáp kieåu cheøn thöôøng nhanh hôn saép xeáp kieåu choïn. Do ñoù chuùng ta chæ xem xeùt saép xeáp kieåu choïn cho danh saùch lieân tuïc. Giaûi thuaät sau ñaây söû duïng haøm phuï trôï max_key cuûa Sortable_list ñeå tìm phaàn töû lôùn nhaát. Hình 8.6- Moät böôùc trong saép xeáp kieåu choïn. Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 157 // Daønh cho danh saùch lieân tuïc trong chöông 4. template void Sortable_list::selection_sort() /* post: Caùc phaàn töû trong danh saùch ñaõ ñöôïc saép xeáp theo thöù töï khoâng giaûm. uses: max_key, swap. */ { for (int position = count - 1; position > 0; position--) { int max = max_key(0, position); swap(max, position); } } Löu yù raèng khi n-1 phaàn töû ñaõ ñöùng vaøo vò trí ñuùng (n laø soá phaàn töû cuûa danh saùch) thì phaàn töû coøn laïi ñöông nhieân coù vò trí ñuùng. Do ñoù voøng laëp keát thuùc taïi position==1. template // Daønh cho danh saùch lieân tuïc trong chöông 4. int Sortable_list::max_key(int low, int high) /* pre: low vaø high laø hai vò trí hôïp leä trong danh saùch vaø low <= high. post: traû veà vò trí phaàn töû lôùn nhaát naèm trong khoaûng chæ soá töø low ñeán high. uses: lôùp Record. */ { int largest, current; largest = low; for (current = low + 1; current <= high; current++) if (entry[largest] < entry[current]) largest = current; return largest; } template void Sortable_list::swap(int low, int high) /* pre: low vaø high laø hai vò trí hôïp leä trong danh saùch Sortable_list. post: Phaàn töû taïi low hoaùn ñoåi vôùi phaàn töû taïi high. uses: Hieän thöïc danh saùch lieân tuïc trong chöông 4. */ { Record temp; temp = entry[low]; entry[low] = entry[high]; entry[high] = temp; } Öu ñieåm chính cuûa saép xeáp kieåu choïn lieân quan ñeán vieäc di chuyeån döõ lieäu. Neáu moät phaàn töû ñaõ ôû ñuùng vò trí cuûa noù thì seõ khoâng bò di chuyeån nöõa. Khi hai Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 158 phaàn töû naøo ñoù ñöôïc ñoåi choã thì ít nhaát moät trong hai phaàn töû seõ ñöôïc ñöa vaøo ñuùng vò trí cuoái cuøng cuûa phaàn töû trong danh saùch. 8.4. Shell_sort Nhö chuùng ta thaáy, nguyeân taéc hoaït ñoäng cuûa saép xeáp kieåu cheøn vaø saép xeáp kieåu choïn laø ngöôïc nhau. Saép xeáp kieåu choïn thöïc hieän vieäc di chuyeån phaàn töû raát hieäu quaû nhöng laïi thöïc hieän nhieàu pheùp so saùnh thöøa. Trong tröôøng hôïp toát nhaát coù theå xaûy ra, saép xeáp kieåu cheøn thöïc hieän raát ít caùc pheùp so saùnh nhöng laïi thöïc hieän raát nhieàu pheùp di chuyeån döõ lieäu thöøa. Sau ñaây chuùng ta xem xeùt moät phöông phaùp trong ñoù nhöôïc ñieåm cuûa moãi phöông phaùp treân seõ ñöôïc traùnh caøng nhieàu caøng toát. Lyù do khieán giaûi thuaät saép xeáp kieåu cheøn chæ di chuyeån caùc phaàn töû moãi laàn ñöôïc moät vò trí laø vì noù chæ so saùnh caùc phaàn töû gaàn nhau. Neáu chuùng ta thay ñoåi giaûi thuaät naøy sao cho noù so saùnh caùc phaàn töû ôû xa nhau tröôùc thì khi coù söï ñoåi choã, moät phaàn töû seõ di chuyeån xa hôn. Daàn daàn, khoaûng caùch naøy ñöôïc giaûm daàn ñeán 1 ñeå ñaûm baûo raèng toaøn boä danh saùch ñöôïc saép xeáp. Ñaây cuõng laø tö töôûng cuûa giaûi thuaät Shell sort, ñöôïc D.L. Shell ñeà xuaát vaø hieän thöïc vaøo naêm 1959. Phöông phaùp naøy ñoâi khi coøn ñöôïc goïi laø phöông phaùp saép xeáp giaûm ñoä taêng (diminishing-increment sort). Ôû ñaây chuùng ta xem moät ví duï khi saép xeáp caùc teân. Luùc ñaàu ta saép xeáp caùc teân ôû caùch nhau 5 vò trí, sau ñoù giaûm xuoáng 3 vaø cuoái cuøng coøn 1. Maëc duø chuùng ta phaûi duyeät danh saùch nhieàu laàn, nhöng trong nhöõng laàn duyeät tröôùc caùc phaàn töû ñaõ ñöôïc di chuyeån ñeán gaàn vò trí cuoái cuøng cuûa chuùng. Nhôø vaäy nhöõng laàn duyeät sau, caùc phaàn töû nhanh choùng ñöôïc di chuyeån veà vò trí ñuùng sau cuøng cuûa chuùng. Caùc khoaûng caùch 5, 3, 1 ñöôïc choïn ngaãu nhieân. Tuy nhieân, khoâng neân choïn caùc böôùc di chuyeån maø chuùng laïi laø boäi soá cuûa nhau. Vì khi ñoù thì caùc phaàn töû ñaõ ñöôïc so saùnh vôùi nhau ôû böôùc tröôùc seõ ñöôïc so saùnh trôû laïi ôû böôùc sau, maø nhö vaäy vò trí cuûa chuùng seõ khoâng ñöôïc caûi thieän. Ñaõ coù moät soá nghieân cöùu veà Shell_sort, nhöng chöa ai coù theå chæ ra caùc khoaûng caùch di chuyeån naøo laø toát nhaát. Tuy nhieân cuõng coù moät soá gôïi yù veà caùch choïn caùc khoaûng caùch di chuyeån. Neáu caùc khoaûng di chuyeån ñöôïc choïn gaàn nhau thì seõ phaûi duyeät danh saùch nhieàu laàn hôn nhöng moãi laàn duyeät laïi nhanh hôn. Ngöôïc laïi, neáu khoaûng caùch di chuyeån giaûm nhanh thì coù ít laàn duyeät hôn vaø moãi laàn duyeät seõ toán nhieàu thôøi gian hôn. Ñieàu quan troïng nhaát laø khoaûng di chuyeån cuoái cuøng phaûi laø 1. Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 159 template void Sortable_list::shell_sort() /* post: Caùc phaàn töû trong Sortable_list ñaõ ñöôïc saép theo thöù töï khoùa khoâng giaûm. uses: Haøm sort_interval */ { int increment = count; // Khoaûng caùch giöõa caùc phaàn töû trong moãi danh saùch con. int start; do { increment = increment / 3 + 1; // Giaûm khoaûng caùch qua moãi laàn laëp. for (start = 0; start < increment; start++) sort_interval(start, increment);// Bieán theå cuûa giaûi thuaät saép xeáp kieåu cheøn. } while (increment > 1); } Haøm sort_interval laø moät bieán theå cuûa giaûi thuaät saép xeáp kieåu cheøn, vôùi thoâng soá increment laø khoaûng caùch cuûa hai phaàn töû keá nhau trong danh saùch caàn ñöôïc saép thöù töï. Tuy nhieân coù moät ñieàu caàn löu yù laø vieäc saép xeáp trong töøng danh saùch con khoâng nhaát thieát phaûi duøng phöông phaùp chen vaøo. Hình 8.7 – Ví duï veà Shell_Sort. Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 160 Taïi böôùc cuoái cuøng, khoaûng di chuyeån laø 1 neân Shell_sort veà baûn chaát vaãn laø saép xeáp kieåu cheøn. Vì vaäy tính ñuùng ñaén cuûa Shell_sort cuõng töông töï nhö saép xeáp kieåu cheøn. Veà maët hieäu quaû, chuùng ta hy voïng raèng caùc böôùc tieàn xöû lyù seõ giuùp cho quaù trình xöû lyù nhanh hôn. Vieäc phaân tích Shell_sort laø ñaëc bieät khoù. Cho ñeán nay, ngöôøi ta chæ môùi coù theå öôùc löôïng ñöôïc soá laàn so saùnh vaø soá pheùp gaùn caàn thieát cho giaûi thuaät trong nhöõng tröôøng hôïp ñaëc bieät. 8.5. Caùc phöông phaùp saép xeáp theo kieåu chia ñeå trò 8.5.1. YÙ töôûng cô baûn Töø nhöõng giaûi thuaät ñaõ ñöôïc trình baøy vaø töø kinh nghieäm thöïc teá ta ruùt ra keát luaän raèng saép xeáp danh saùch daøi thì khoù hôn laø saép xeáp danh saùch ngaén. Neáu chieàu daøi danh saùch taêng gaáp ñoâi thì coâng vieäc saép xeáp thoâng thöôøng taêng hôn gaáp ñoâi (vôùi saép xeáp kieåu cheøn vaø saép xeáp kieåu choïn, khoái löôïng coâng vieäc taêng leân khoaûng boán laàn). Do ñoù, neáu chuùng ta coù theå chia moät danh saùch ra thaønh hai phaàn coù kích thöôùc xaáp xæ nhau vaø thöïc hieän vieäc saép xeáp moãi phaàn moät caùch rieâng reõ thì khoái löôïng coâng vieäc caàn thieát cho vieäc saép xeáp seõ giaûm ñi ñaùng keå. Ví duï vieäc saép xeáp caùc phieáu trong thö vieän seõ nhanh hôn neáu caùc phieáu ñöôïc chia thaønh töøng nhoùm coù chung chöõ caùi ñaàu vaø töøng nhoùm ñöôïc tieán haønh saép xeáp rieâng reõ. Ôû ñaây chuùng ta vaän duïng yù töôûng chia moät baøi toaùn thaønh nhieàu baøi toaùn töông töï nhö baøi toaùn ban ñaàu nhöng nhoû hôn vaø giaûi quyeát caùc baøi toaùn nhoû naøy. Sau ñoù chuùng ta toång hôïp laïi ñeå coù lôøi giaûi cho toaøn boä baøi toaùn ban ñaàu. Phöông phaùp naøy ñöôïc goïi laø “chia ñeå trò” ( divide-and-conquer). Ñeå saép xeáp caùc danh saùch con, chuùng ta laïi aùp duïng chieán löôïc chia ñeå trò ñeå tieáp tuïc chia nhoû töøng danh saùch con. Quaù trình naøy dó nhieân khoâng bò laëp voâ taän. Khi ta coù caùc danh saùch con vôùi kích thöôùc laø 1 phaàn töû thì quaù trình döøng. Chuùng ta coù theå theå hieän yù töôûng treân trong ñoaïn maõ giaû sau ñaây. void Sortable_list::sort() { if (danh saùch coù nhieàu hôn 1 phaàn töû) { Phaân hoaïch danh saùch thaønh hai danh saùch con lowlist, highlist; lowlist.sort(); highlist.sort(); Keát noái hai danh saùch con lowlist vaø highlist; } } Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 161 Vaán ñeà coøn laïi caàn xem xeùt laø caùch phaân hoaïch (partition) danh saùch ban ñaàu vaø caùch keát noái (combine) hai danh saùch ñaõ coù thöù töï cho thaønh moät danh saùch coù thöù töï. Coù hai phöông phaùp döôùi ñaây, moãi phöông phaùp seõ laøm vieäc toát öùng vôùi moät soá tröôøng hôïp rieâng. • Merge_sort: theo phöông phaùp naøy hai danh saùch con chæ caàn coù kích thöôùc gaàn baèng nhau. Sau khi saép xeáp xong thì chuùng ñöôïc troän laïi sao cho danh saùch cuoái cuøng coù thöù töï. • Quick_sort: theo phöông phaùp naøy, hai danh saùch con ñöôïc chia sao cho böôùc keát noái laïi trôû neân ñôn giaûn. Phöông phaùp naøy ñöôïc C. A. R. Hoare ñöa ra. Ñeå phaân hoaïch danh saùch, chuùng ta seõ choïn moät phaàn töû töø trong danh saùch vôùi hi voïng raèng coù khoaûng moät nöûa soá phaàn töû ñöùng tröôùc vaø khoaûng moät nöûa soá phaàn töû ñöùng sau phaàn töû ñöôïc choïn trong danh saùch coù thöù töï sau cuøng. Phaàn töû naøy ñöôïc goïi laø phaàn töû truï (pivot). Sau ñoù chuùng ta chia caùc phaàn töû theo qui taéc: caùc phaàn töû coù khoaù nhoû hôn khoaù cuûa phaàn töû truï ñöôïc chia vaøo danh saùch thöù nhaát, caùc phaàn töû coù khoaù lôùn hôn khoaù cuûa phaàn töû truï ñöôïc chia vaøo danh saùch thöù hai. Khi hai danh saùch naøy ñaõ ñöôïc saép xeáp thì chuùng ta chæ caàn noái chuùng laïi vôùi nhau. 8.5.2. Ví duï Tröôùc khi xem xeùt chi tieát cuûa caùc giaûi thuaät, chuùng ta seõ thöïc hieän vieäc saép xeáp moät danh saùch cuï theå coù 7 soá nhö sau: 26 33 35 29 19 12 22 Hình 8.8- Caây ñeä quy cho Merge_sort vôùi 7 soá. Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 162 8.5.2.1. Ví duï cho Merge_sort Böôùc ñaàu tieân laø chia danh saùch thaønh hai phaàn. Khi soá phaàn töû cuûa danh saùch laø leû thì chuùng ta seõ qui öôùc danh saùch con beân traùi seõ daøi hôn danh saùch con beân phaûi moät phaàn töû. Theo qui öôùc naøy, chuùng ta coù hai danh saùch con 26 33 35 29 vaø 19 12 22 Ta xem xeùt danh saùch con thöù nhaát tröôùc. Danh saùch naøy cuõng ñöôïc chia thaønh hai phaàn 26 33 vaø 35 29 vôùi moãi nöûa naøy, chuùng ta laïi aùp duïng phöông phaùp treân ñeå ñöôïc caùc danh saùch con coù chieàu daøi laø 1. Caùc danh saùch con chieàu daøi 1 phaàn töû naøy khoâng caàn phaûi saép xeáp. Cuoái cuøng chuùng ta caàn phaûi troän caùc danh saùch con naøy ñeå ñöôïc moät danh saùch coù thöù töï. 26 vaø 33 taïo thaønh danh saùch 26 33; 35 vaø 29 ñöôïc troän thaønh 29 35. Keá tieáp, hai danh saùch naøy naøy ñöôïc troän thaønh 26 29 33 35. Töông töï nhö vaäy, vôùi nöûa thöù hai cuûa danh saùch ban ñaàu ta ñöôïc 12 19 22 Cuoái cuøng, troän hai phaàn naøy ta ñöôïc 12 19 22 26 29 33 35 8.5.2.2. Ví duï cho Quick_sort Chuùng ta söû duïng ví duï naøy cho Quick_sort. Ñeå söû duïng Quick_sort, tröôùc tieân chuùng ta phaûi xaùc ñònh phaàn töû truï. Phaàn töû naøy coù theå laø phaàn töû baát kyø naøo cuûa danh saùch, tuy nhieân, ñeå cho thoáng nhaát chuùng ta seõ choïn phaàn töû ñaàu tieân. Trong caùc öùng duïng thöïc teá thöôøng ngöôøi ta coù nhöõng caùch xaùc ñònh phaàn töû truï khaùc toát hôn. Theo ví duï naøy, phaàn töû truï ñaàu tieân laø 26. Do ñoù hai danh saùch con ñöôïc taïo ra laø: 19 12 22 vaø 33 35 29 Hai danh saùch naøy laàn löôït chöùa caùc soá nhoû hôn vaø lôùn hôn phaàn töû truï. Ôû ñaây thöù töï cuûa caùc phaàn töû trong hai danh saùch con khoâng ñoåi so vôùi danh saùch ban ñaàu nhöng ñaây khoâng phaûi laø ñieàu baét buoäc. Chuùng ta tieáp tuïc saép xeáp caùc chuoãi con. Vôùi chuoãi con thöù nhaát, chuùng ta choïn phaàn töû truï laø 19, do ñoù ñöôïc hai danh saùch con laø 12 vaø 22. Hai danh saùch naøy Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 163 chæ coù moät phaàn töû neân ñöông nhieân coù thöù töï. Cuoái cuøng, gom hai danh saùch con vaø phaàn töû truï laïi ta coù danh saùch ñaõ saép xeáp 12 19 22 AÙp duïng phöông phaùp treân cho phaàn thöù hai cuûa danh saùch, ta ñöôïc danh saùch cuoái cuøng laø 29 33 35 Gom hai danh saùch con ñaõ saép xeáp naøy vaø phaàn töû truï ñaàu tieân ta ñöôïc danh saùch coù thöù töï sau cuøng: 12 19 22 26 29 33 35 Caùc böôùc cuûa giaûi thuaät ñöôïc minh hoaï bôûi hình sau. Hình 8.9- Caùc böôùc thöïc thi cuûa Quick_sort Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 164 8.6. Merge_sort cho danh saùch lieân keát Sau ñaây laø caùc haøm ñeå thöïc hieän caùc pheùp saép xeáp noùi treân. Vôùi Merge_sort, chuùng ta vieát moät phieân baûn cho danh saùch lieân keát coøn vôùi Quick_sort thì chuùng ta vieát moät phieân baûn cho danh saùch lieân tuïc. Sinh vieân coù theå töï phaân tích xem lieäu caùch laøm ngöôïc laïi coù khaû thi vaø coù hieäu quaû hay khoâng (Merge_sort cho danh saùch lieân tuïc vaø Quick_sort cho danh saùch lieân keát). Merge_sort coøn laø moät phöông phaùp raát toát cho vieäc saép xeáp ngoaïi, töùc laø saép xeáp caùc döõ lieäu naèm treân boä nhôù ngoaøi coù toác ñoä truy xuaát khaù chaäm vaø khoâng coù khaû naêng truy xuaát ngaãu nhieân. Saép xeáp danh saùch lieân keát coù nghóa laø thay ñoåi caùc moái lieân keát trong danh saùch vaø traùnh vieäc taïo môùi hay xoaù ñi caùc phaàn töû. Cuï theå hôn, chöông trình Merge_sort seõ goïi moät haøm ñeä qui ñeå xöû lyù töøng taäp con caùc phaàn töû cuûa danh saùch lieân keát. // Daønh cho danh saùch lieân keát trong chöông 4. template void Sortable_list::merge_sort() /* post: Caùc phaàn töû trong danh saùch ñaõ ñöôïc saép theo thöù töï khoâng giaûm. uses: recursive_merge_sort. */ { recursive_merge_sort(head); } Hình 8.10- Caây ñeä quy cho Quick_sort vôùi 7 phaàn töû. Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 165 Sau ñaây laø haøm recursive_merge_sort ñöôïc vieát döôùi daïng ñeä qui. template void Sortable_list::recursive_merge_sort(Node *&sub_list) /* post: Caùc phaàn töû trong danh saùch tham chieáu bôûi sub_list ñaõ ñöôïc saép theo thöù töï khoâng giaûm. Tham bieán con troû sub_list ñöôïc caäp nhaät chöùa ñòa chæ phaàn töû ñaàu tieân vaø cuõng laø phaàn töû nhoû nhaát trong danh saùch. uses: Caùc haøm divide_from, merge, vaø recursive_merge_sort. */ { if (sub_list != NULL && sub_list->next != NULL) { Node *second_half = divide_from(sub_list); recursive_merge_sort(sub_list); recursive_merge_sort(second_half); sub_list = merge(sub_list, second_half); } } Haøm ñaàu tieân maø haøm recursive_merge_sort söû duïng laø divide_from. Haøm naøy nhaän vaøo danh saùch ñöôïc tham chieáu bôûi sub_list vaø taùch noù thaønh hai nöûa baèng caùch thay lieân keát ôû giöõa danh saùch baèng NULL vaø traû veà con troû ñeán phaàn töû ñaàu tieân cuûa phaàn coøn laïi cuûa danh saùch ban ñaàu. Baèng caùch cho con troû midpoint tieán moät böôùc vaø con troû position tieán hai böôùc trong moãi laàn laëp, khi position ñeán cuoái danh saùch thì midpoint döøng ngay giöõa danh saùch. // Daønh cho danh saùch lieân keát trong chöông 4. template Node *Sortable_list::divide_from(Node *sub_list) /* post: Soá phaàn töû trong danh saùch troû bôûi sub_list giaûm moät nöûa. Ñòa chæ phaàn töû ñaàu trong danh saùch caùc phaàn töû coøn laïi ñöôïc traû veà. Neáu danh saùch ban ñaàu coù soá phaàn töû leû thì danh saùch thöù nhaát nhieàu hôn danh saùch thöù hai 1 phaàn töû. */ { Node *position, *midpoint, *second_half; if ((midpoint = sub_list) == NULL) return NULL; // Danh saùch ban ñaàu roãng. position = midpoint->next; while (position != NULL) { // Tìm phaàn töû naèm giöõa danh saùch. position = position->next; if (position != NULL) { midpoint = midpoint->next; position = position->next; } } second_half = midpoint->next; midpoint->next = NULL; return second_half; } Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 166 Haøm thöù hai Node *merge(Node *first, Node *second) troän hai danh saùch coù thöù töï khoâng giaûm troû bôûi first vaø second thaønh moät danh saùch coù thöù töï khoâng giaûm vaø traû veà con troû ñeán phaàn töû coù khoaù nhoû nhaát (cuõng laø phaàn töû ñaàu tieân cuûa danh saùch keát quaû). Haøm naøy duyeät ñoàng thôøi hai danh saùch, so saùnh moät caëp khoaù laáy töø hai phaàn töû, moãi phaàn töû thuoäc moät trong hai danh saùch noùi treân, vaø ñöa phaàn töû thích hôïp (nhoû hôn hoaëc baèng) vaøo trong danh saùch keát quaû. Tröôøng hôïp ñaàu vaø cuoái cuûa danh saùch caàn phaûi ñöôïc xöû lyù rieâng bieät. Khi moät trong hai danh saùch heát tröôùc, chuùng ta chæ caàn noái phaàn coøn laïi cuûa danh saùch kia vaøo cuoái danh saùch keát quaû. Caàn nhaéc laïi raèng, ñoái vôùi danh saùch lieân keát, caùch xöû lyù cho phaàn töû ñaàu tieân khoâng gioáng vôùi caùch xöû lyù cho caùc phaàn töû töø vò trí thöù hai trôû ñi, do coù aûnh höôûng ñeán con troû ñaàu danh saùch. Caùch deã daøng nhaát laø chuùng ta taïo moät nuùt taïm thôøi goïi laø combined. Nuùt naøy ñöôïc ñaët ôû ñaàu danh saùch vaø khoâng chöùa döõ lieäu thöïc. Vôùi caáu truùc naøy, caùc phaàn töû coù theå ñöôïc ñöa vaøo danh saùch maø khoâng caàn phaûi phaân bieät ñaâu laø phaàn töû ñaàu tieân thöïc söï. Cuoái cuøng, giaù trò traû veà cuûa haøm laø con troû next cuûa nuùt combined. Nuùt combined coøn ñöôïc goïi laø nuùt giaû vì noù khoâng chöùa döõ lieäu thaät söï maø chæ ñöôïc duøng ñeå ñôn giaûn hoaù vieäc xöû lyù caùc con troû, noù seõ khoâng coøn toàn taïi khi heát phaïm vi cuûa phöông thöùc merge. Hình 8.11- Troân hai danh saùch ñaõ coù thöù töï. Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 167 // Daønh cho danh saùch lieân keát trong chöông 4. template Node *Sortable_list::merge(Node *first, Node *second) /* pre: first vaø second troû ñeán hai danh saùch coù thöù töï. post: Phöông thöùc traû veà con troû troû ñeán danh saùch caùc phaàn töû ñaõ coù thöù töï, ñoù laø caùc phaàn töû cuûa hai danh saùch ban ñaàu ñöôïc troän laïi. Hai danh saùch ban ñaàu khoâng coøn phaàn töû. uses: Caùc phöông thöùc cuûa lôùp Records. */ { Node *last_sorted; Node combined; // Phaàn töû giaû. last_sorted = &combined; // Danh saùch keát quaû nhaän daàn caùc phaàn töû töø first vaø // second, theo thöù töï töø phaàn töû nhoû ñeán phaàn töû lôùn. while (first != NULL && second != NULL) { if (first->entry entry) { last_sorted->next = first; last_sorted = first; first = first->next; } else { last_sorted->next = second; last_sorted = second; second = second->next; } } // Noái phaàn coøn laïi cuûa danh saùch chöa heát. if (first == NULL) last_sorted->next = second; else last_sorted->next = first; return combined.next; } 8.7. Quick_sort cho danh saùch lieân tuïc 8.7.1. Caùc haøm Giaûi thuaät Quick_sort cho danh saùch lieân tuïc caàn ñeán moät giaûi thuaät phaân hoaïch danh saùch thoâng qua vieäc söû duïng phaàn töû truï. Giaûi thuaät naøy ñoåi choã caùc phaàn töû sao cho caùc phaàn töû coù khoaù nhoû hôn khoaù phaàn töû truï seõ ñöôïc ñöùng tröôùc, keá ñeán laø caùc phaàn töû coù khoaù truøng vôùi khoaù cuûa phaàn töû truï, vaø cuoái cuøng laø caùc phaàn töû coù khoaù lôùn hôn khoaù cuûa phaàn töû truï. Chuùng ta duøng bieán pivot_position ñeå löu laïi vò trí cuûa phaàn töû truï trong danh saùch ñaõ ñöôïc phaân hoaïch. Do caùc danh saùch con, keát quaû cuûa pheùp phaân hoaïch, ñöôïc löu trong cuøng moät danh saùch vaø theo ñuùng vò trí töông ñoái giöõa chuùng, neân vieäc gom chuùng laïi thaønh moät danh saùch laø hoaøn toaøn khoâng caàn thieát vaø chöông trình khoâng caàn phaûi laøm theâm baát cöù ñieàu gì. Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 168 Ñeå coù theå goïi ñeä qui haøm saép xeáp cho caùc danh saùch con, caùc giôùi haïn treân vaø döôùi cuûa danh saùch phaûi laø caùc tham soá cho haøm saép xeáp. Tuy nhieân, do qui öôùc cuûa chuùng ta laø caùc phöông thöùc saép xeáp khoâng nhaän tham soá, chuùng ta seõ duøng moät phöông thöùc khoâng coù tham soá ñeå goïi haøm saép xeáp ñeä qui coù tham soá. // Daønh cho danh saùch lieân tuïc trong chöông 4. template void Sortable_list::quick_sort() /* post: Caùc phaàn töû trong danh saùch ñaõ ñöôïc saép theo thöù töï khoâng giaûm. uses: recursive_quick_sort. */ { recursive_quick_sort(0, count - 1); } Haøm ñeä qui thöïc hieän vieäc saép xeáp: // Daønh cho danh saùch lieân tuïc trong chöông 4. template void Sortable_list::recursive_quick_sort(int low, int high) /* pre: low vaø high laø caùc vò trí hôïp leä trong Sortable_list. post: Caùc phaàn töû trong danh saùch töø chæ soá low ñeán chæ soá high ñaõ ñöôïc saép theo thöù töï khoâng giaûm. uses: recursive_quick_sort, partition. */ { int pivot_position; if (low < high) { // Danh saùch coù nhieàu hôn moät phaàn töû. pivot_position = partition(low, high); recursive_quick_sort(low, pivot_position - 1); recursive_quick_sort(pivot_position + 1, high); } } 8.7.2. Phaân hoaïch danh saùch Coù nhieàu giaûi thuaät ñeå phaân hoaïch danh saùch. Phöông phaùp chuùng ta söû duïng ôû ñaây raát ñôn giaûn nhöng hieäu quaû. Noù thöïc hieän soá laàn so saùnh khoaù nhoû nhaát coù theå ñöôïc. 8.7.2.1. Phaùt trieån giaûi thuaät Cho giaù trò cuûa phaàn töû truï, chuùng ta phaûi boá trí laïi caùc phaàn töû vaø tính chæ soá pivot_position sao cho phaàn töû truï naèm taïi pivot_position, caùc phaàn töû nhoû hôn naèm phía beân traùi vaø caùc phaàn töû lôùn hôn naèm phía beân phaûi phaàn töû truï. Ñeå coù theå xöû lyù tröôøng hôïp coù nhieàu hôn moät phaàn töû coù khoaù ñuùng baèng khoaù cuûa phaàn töû truï, chuùng ta qui öôùc raèng caùc phaàn töû beân traùi coù khoaù nhoû hôn khoaù cuûa phaàn töû truï moät caùch nghieâm ngaët trong khi caùc phaàn töû beân phaûi coù khoaù lôùn hôn hoaëc baèng khoaù cuûa phaàn töû truï nhö trong sô ñoà sau ñaây. Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 169 Ñeå coù ñöôïc caùc phaàn töû nhö theá naøy, chuùng ta phaûi so saùnh töøng phaàn töû vôùi phaàn töû truï baèng caùch söû duïng moät voøng for vôùi bieán chæ soá laø i. Ngoaøi ra, chuùng ta coøn söû duïng bieán last_small sao cho caùc phaàn töû töø last_small trôû veà tröôùc coù khoaù nhoû hôn khoaù cuûa phaàn töû truï. Giaû söû ban ñaàu phaàn töû truï naèm taïi ñaàu danh saùch. Taïm thôøi chuùng ta seõ giöõ nguyeân vò trí cuûa noù ôû ñoù. Khi chöông trình ñang ôû trong thaân voøng laëp, danh saùch vaø caùc bieán coù quan heä vôùi nhau nhö sau: Khi chöông trình kieåm tra phaàn töû taïi vò trí i thì coù hai tröôøng hôïp xaûy ra. Neáu phaàn töû ñoù vaãn lôùn hôn hay baèng phaàn töû truï thì bieán i seõ tieáp tuïc taêng leân vaø danh saùch vaãn baûo toaøn tính chaát caàn thieát. Ngöôïc laïi, chuùng ta seõ taêng last_small vaø hoaùn ñoåi hai phaàn töû taïi last_small (môùi) vaø phaàn töû taïi i. Khi ñoù, tính chaát cuûa danh saùch vaãn ñöôïc duy trì. Cuoái cuøng, khi i ñaõ ñi heát chieàu daøi cuûa danh saùch, chuùng ta chæ caàn ñoåi choã phaàn töû truï töø vò trí low sang vò trí last_small laø seõ coù keát quaû caàn thieát. Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 170 8.7.2.2. Choïn phaàn töû truï Phaàn töû truï khoâng nhaát thieát phaûi laø phaàn töû ñaàu tieân cuûa danh saùch. Chuùng ta coù theå choïn baát cöù phaàn töû naøo cuûa danh saùch ñeå laøm phaàn töû truï. Thöïc teá thì phaàn töû ñaàu tieân thöôøng khoâng phaûi laø phaàn töû truï toát. Vì neáu danh saùch ñaõ coù thöù töï thì khoâng coù phaàn töû naøo nhoû hôn phaàn töû truï, do ñoù moät trong hai danh saùch con seõ roãng vaø trong tröôøng hôïp naøy Quick_sort trôû thaønh “Slow_sort”. Vì vaäy, moät löïa choïn toát hôn cho phaàn töû truï laø phaàn töû gaàn giöõa cuûa danh saùch vôùi hi voïng raèng phaàn töû naøy seõ chia hai danh saùch coù kích thöôùc gaàn nhö nhau. 8.7.2.3. Vieát chöông trình Vôùi nhöõng löïa choïn naøy, chuùng ta coù ñöôïc phöông thöùc sau. template int Sortable_list::partition(int low, int high) /* pre: low vaø high laø caùc vò trí hôïp leä trong Sortable_list, low <= high. post: Phaàn töû naèm giöõa hai chæ soá low vaø high ñöôïc choïn laøm pivot. Caùc phaàn töû trong danh saùch töø chæ soá low ñeán chæ soá high ñaõ ñöôïc phaân hoaïch nhö sau: caùc phaàn töû nhoû hôn pivot ñöùng tröôùc pivot, caùc phaàn töû coøn laïi ñöùng saö pivot. Haøm traû veà vò trí cuûa pivot. uses: caùc phöông thöùc cuûa lôùp Record vaø haøm swap(int i, int j) hoaùn vò hai phaàn töû taïi vò trí i vaø j trong danh saùch. */ { Record pivot; int i, last_small; swap(low, (low + high) / 2); pivot = entry[low]; last_small = low; for (i = low + 1; i <= high; i++) // Ñaàu moãi laàn laëp, chuùng ta coù caùc ñieàu kieän sau: // If low < j <= last_small then entry[j].key < pivot. // If last_small = pivot. if (entry[i] < pivot) { last_small = last_small + 1; swap(last_small, i); } swap(low, last_small);// Traû pivot veà ñuùng vò trí thích hôïp return last_small; } 8.8. Heap vaø Heap_sort Quick_sort coù moät nhöôïc ñieåm laø ñoä phöùc taïp trong tröôøng hôïp xaáu nhaát raát lôùn. Thoâng thöôøng thì Quick_sort chaïy raát nhanh nhöng cuõng coù nhöõng tröôøng hôïp döõ lieäu vaøo khieán cho Quick_sort chaïy raát chaäm. Trong phaàn naøy chuùng ta xem xeùt moät phöông phaùp saép xeáp khaùc khaéc phuïc ñöôïc nhöôïc ñieåm naøy. Giaûi thuaät naøy coù teân laø Heap_sort. Heap_sort caàn O(n log n) pheùp so saùnh vaø di chuyeån phaàn töû ñeå saép xeáp moät danh saùch lieân tuïc coù n phaàn töû, ngay caû trong tröôøng hôïp xaáu nhaát. Nhö vaäy trong tröôøng hôïp xaáu nhaát, Heap_sort coù giôùi haïn Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 171 veà thôøi gian chaïy toát hôn so vôùi Quick_sort. Ngoaøi ra noù cuõng toát hôn Merge_sort treân danh saùch lieân tuïc veà maët söû duïng khoâng gian. Giaûi thuaät Heap_sort cuõng nhö moät soá hieän thöïc cuûa haøng öu tieân trong chöông 11 ñeàu döïa treân cuøng moät khaùi nieäm heap nhö nhau. Ñoù laø moät caáu truùc caây töông töï nhö caáu truùc caáp baäc trong moät toå chöùc. Chuùng ta thöôøng bieåu dieãn caáu truùc toå chöùc cuûa moät coâng ty naøo ñoù baèng moät caáu truùc caây. Khi giaùm ñoác coâng ty nghæ vieäc thì moät trong hai phoù giaùm ñoác (ngöôøi toát hôn, theo moät soá tieâu chí naøo ñoù) seõ ñöôïc choïn ñeå theá choã vaø nhö vaäy tieáp tuïc troáng moät vò trí khaùc. Quaù trình naøy ñöôïc laëp laïi töø choã cao nhaát trong caáu truùc cho ñeán choã thaáp nhaát. Chuùng ta laøm quen vôùi ñònh nghóa heap nhò phaân döôùi ñaây. 8.8.1. Ñònh nghóa heap nhò phaân Ñònh nghóa: Moät heap nhò phaân laø moät caáu truùc caây nhò phaân vôùi hai tính chaát sau: 1. Caây ñaày ñuû hoaëc gaàn nhö ñaày ñuû. 2. Khoùa taïi moãi nuùt ñeàu nhoû hôn hoaëc baèng khoùa cuûa caùc nuùt trong hai caây con cuûa noù. Moät caây nhò phaân ñaày ñuû hoaëc gaàn nhö ñaày ñuû chieàu cao h seõ coù töø 2h-1 ñeán 2h- 1 nuùt. Do ñoù chieàu cao cuûa noù seõ laø O(logN). Moät ñieàu quan troïng nhaát ôû ñaây laø do tính chaát caây ñaày ñuû hoaëc gaàn nhö ñaày ñuû neân heap coù theå ñöôïc hieän thöïc baèng maûng lieân tuïc caùc phaàn töû maø khoâng caàn duøng ñeán con troû. Neáu phaàn töû ñaàu tieân cuûa maûng coù chæ soá laø 0 thì, moät phaàn töû taïi vò trí i seõ coù con traùi taïi 2i+1 vaø con phaûi taïi 2i+2, vaø cha cuûa noù taïi ⎣i-1/2⎦ . (a) (b) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 13 21 16 24 31 19 68 65 26 32 (c) Hình 8.12 (a) Caây nhò phaân gaàn nhö ñaày ñuû bieåu dieãn moät heap. 13 21 16 24 31 65 26 32 19 68 13 21 16 20 31 65 26 32 19 68 Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 172 (b) Khoâng thoûa ñieàu kieän cuûa heap taïi neùt ñöùt rôøi. (c) Hieän thöïc heap ôû hình a trong moät maûng lieân tuïc. Löu yù raèng coù khi chuùng ta goïi heap ñöôïc ñònh nghóa nhö treân laø moät min- heap, ñeå phaân bieät vôùi tröôøng hôïp max-heap. Trong min-heap thì phaàn töû taïi goác laø phaàn töû beù nhaát. Max-heap seõ söûa ñieàu kieän thöù hai thaønh “Khoùa taïi moãi nuùt ñeàu lôùn hôn hoaëc baèng khoùa cuûa caùc nuùt trong hai caây con cuûa noù”, do ñoù phaàn töû taïi goác seõ laø phaàn töû lôùn nhaát. Max-heap ñöôïc söû duïng trong giaûi thuaät Heap_sort. Khi ñoïc xong veà haøng öu tieân, sinh vieân coù theå thaáy raèng coù theå söû duïng ngay haøng öu tieân (neáu ñaõ coù saün) ñeå phuïc vuï cho vieäc saép xeáp theo ñuùng yù töôûng cuûa Heap_sort. Tuy nhieân, neáu chæ vôùi muïc ñích hieän thöïc moät giaûi thuaät saép thöù töï thaät hieäu quaû treân moät danh saùch saùch lieân tuïc, thì giaûi thuaät saép ñöôïc trình baøy döôùi ñaây ñôn giaûn vaø tieát kieäm khoâng gian hôn raát nhieàu, do noù ñaõ coá gaéng chæ söûng duïng chính phaàn boä nhôù chöùa caùc phaàn töû caàn saép xeáp, chöù khoâng ñoøi hoûi theâm vuøng nhôù naøo ñaùng keå. Löu yù raèng heap khoâng phaûi laø moät danh saùch coù thöù töï. Tuy phaàn töû ñaàu tieân laø phaàn töû lôùn nhaát cuûa danh saùch nhöng taïi caùc vò trí k > 1 khaùc thì khoâng coù moät thöù töï baét buoäc giöõa caùc phaàn töû k vaø k+1. Ngoaøi ra, töø heap ôû ñaây khoâng coù lieân heä gì vôùi töø heap duøng trong vieäc quaûn lyù boä nhôù ñoäng. 8.8.2. Phaùt trieån giaûi thuaät Heap_sort 8.8.2.1. Phöông phaùp Giaûi thuaät Heap_sort bao goàm hai giai ñoaïn. Ñaàu tieân, caùc phaàn töû trong danh saùch ñöôïc saép xeáp ñeå thoaû yeâu caàu cuûa moät heap. Keá ñeán chuùng ta laäp laïi nhieàu laàn vieäc laáy ra phaàn töû ñaàu tieân cuûa heap vaø choïn moät phaàn töû khaùc leân thay theá noù. Hình 8.13- Max-heap bieåu dieãn döôùi daïng caây vaø döôùi daïng danh saùch lieân tuïc. Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 173 Trong giai ñoaïn thöù hai, chuùng ta nhaän thaáy raèng goác cuûa caây (cuõng laø phaàn töû ñaàu tieân cuûa danh saùch hay laø ñænh cuûa heap) laø phaàn töû coù khoùa lôùn nhaát. Vò trí ñuùng cuoái cuøng cuûa phaàn töû naøy laø ôû cuoái danh saùch. Nhö vaäy chuùng ta di chuyeån phaàn töû naøy veà cuoái danh saùch, phaàn töû taïi vò trí cuoái danh saùch thì ñöôïc cheùp vaøo phaàn töû taïm current ñeå nhöôøng choã. Keá ñeán chuùng ta giaûm bieán last_unsorted laø ranh giôùi giöõa phaàn danh saùch chöa ñöôïc saép xeáp vôùi caùc phaàn töû ñaõ ñöôïc ñöa veà vò trí ñuùng (Quaù trình saép xeáp tieáp theo seõ khoâng quan taâm ñeán caùc phaàn töû naèm sau last_unsorted). Luùc naøy, vò trí ñaàu danh saùch chöa saép xeáp ñöôïc xem nhö troáng, caùc phaàn töû coøn laïi trong danh saùch ñeàu ñang thoûa ñieàu kieän cuûa heap. Vieäc caàn laøm chính laø tìm choã thích hôïp ñeå ñaët phaàn töû ñang chöùa taïm trong current vaøo danh saùch naøy maø vaãn duy trì tính chaát cuûa heap, tröôùc khi choïn ra phaàn töû lôùn nhaát keá tieáp. Haøm phuï trôï insert_heap seõ laøm ñieàu naøy. Nhö vaäy, theo giaûi thuaät naøy, Heap_sort caàn truy xuaát ngaãu nhieân ñeán caùc phaàn töû trong danh saùch. Heap_sort chæ thích hôïïp vôùi danh saùch lieân tuïc. 8.8.2.2. Chöông trình chính Sau ñaây laø haøm thöïc hieän giaûi thuaät Heap_sort. // Daønh cho danh saùch lieân tuïc trong chöông 4. template void Sortable_list::heap_sort() /* post: Caùc phaàn töû trong danh saùch ñaõ ñöôïc saép xeáp theo thöù töï khoâng giaûm. uses: build_heap vaø insert_heap. */ { Record current; int last_unsorted; // Caùc phaàn töû naèm sau last_unsorted ñaõ coù thöù töï build_heap(); // Giai ñoaïn 1: taïo heap töø danh saùch caùc phaàn töû. for (last_unsorted = count - 1; last_unsorted > 0; last_unsorted--) { current = entry[last_unsorted]; entry[last_unsorted] = entry[0];// Moãi laàn laëp choïn ñöôïc moät phaàn töû lôùn nhaát. insert_heap(current, 0, last_unsorted - 1); // Khoâi phuïc heap. } } 8.8.2.3. Ví duï Tröôùc khi vieát caùc haøm ñeå taïo heap (build_heap) vaø ñöa phaàn töû vaøo heap (insert_heap) chuùng ta xem xeùt moät soá böôùc ñaàu tieân cuûa quaù trình saép xeáp heap treân hình. Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 174 Trong böôùc ñaàu tieân, khoaù lôùn nhaát, y, ñöôïc di chuyeån töø ñaàu ñeán cuoái danh saùch. Hình veõ ñaàu tieân cho thaáy keát quaû cuûa vieäc di chuyeån, trong ñoù y ñöôïc taùch ra khoûi caây vaø phaàn töû cuoái cuøng tröôùc ñaây, c, ñöôïc ñöa vaøo phaàn töû taïm current. Ñeå toå chöùc laïi caây, chuùng ta xem xeùt hai phaàn töû taïi goác cuûa hai caây con. Moãi phaàn töû naøy lôùn hôn taát caû caùc phaàn töû khaùc trong caây con töông öùng. Do ñoù chuùng ta choïn phaàn töû lôùn nhaát trong ba phaàn töû, hai phaàn töû goác cuûa hai caây con vaø baûn thaân c, laøm phaàn töû goác môùi cuûa toaøn boä caây. Trong ví duï naøy, chuùng ta seõ ñöa phaàn töû r leân goác vaø laëp laïi quaù trình cho hai caây con cuûa r. Tôùi ñaây, chuùng ta seõ duøng f ñeå theá choã cho r. Taïi f, vì f khoâng coù nuùt con cho neân c seõ theá choã f vaø quaù trình döøng. Chuùng ta thaáy raèng ñieàu kieän döøng khi tìm thaáy choã troáng thích hôïp cho c thoûa tính chaát cuûa heap laø: moät choã troáng maø khoâng coù nuùt con, hoaëc moät choã troáng maø caû hai nuùt con ñeàu <= c. Tieáp theo, chuùng ta laïi coù theå taùch phaàn töû lôùn nhaát trong heap (phaàn töû ñaàu tieân) vaø laëp laïi toaøn boä quaù trình. Hình 8.14 – Böôùc thöù nhaát cuûa Heapsort. Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 175 8.8.2.4. Haøm insert_heap Töø nhöõng ñieàu trình baøy ôû treân ta coù haøm insert_heap nhö sau. // Daønh cho danh saùch lieân tuïc trong chöông 4. template void Sortable_list::insert_heap(const Record ¤t, int low, int high) /* pre: Caùc phaàn töû töø chæ soá low + 1 ñeán high thoûa ñieàu kieän cuûa heap. low xem nhö vò trí coøn troáng (phaàn töû taïi low seõ bò boû ñi). post: Phaàn töû trong current thay theá cho phaàn töû taïi low, vaø taát caû caùc phaàn töû töø low ñeán high ñöôïc taùi saép xeáp ñeå thoûa ñieàu kieän cuûa heap. uses: Lôùp Record */ { int large; large = 2 * low + 1; // large laø vò trí con traùi cuûa low. while (large <= high) { if (large < high && entry[large] < entry[large + 1]) large++;//large laø vò trí cuûa con coù khoùa lôùn nhaát trong 2 con cuûa phaàn töû taïi low. Hình 8. 15 – Theo veát cuûa Heap_sort Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 176 if (current >= entry[large]) break; // low chính laø vò trí coù theå ñaët current vaøo.. else { // Dôøi phaàn töû con leân laáp choã troáng. entry[low] = entry[large]; low = large; large = 2 * low + 1; } } entry[low] = current; } 8.8.2.5. Xaây döïng heap ban ñaàu Vieäc coøn laïi maø chuùng ta phaûi laøm laø xaây döïng heap ban ñaàu töø danh saùch coù thöù töï baát kyø. Tröôùc tieân, ta löu yù raèng caây nhò phaân coù moät soá nuùt töï ñoäng thoaû ñieàu kieän cuûa heap do chuùng khoâng coù nuùt con. Ñoù chính laø caùc nuùt laù trong caây. Do ñoù chuùng ta khoâng caàn saép xeáp caùc nuùt laù cuûa caây, töùc laø nöûa sau cuûa danh saùch. Neáu chuùng ta baét ñaàu töø ñieåm giöõa cuûa danh saùch vaø duyeät veà phía ñaàu danh saùch thì coù theå söû duïng haøm insert_heap ñeå ñöa laàn löôït töøng phaàn töû vaøo trong heap, vôùi löu yù söû duïng caùc thoâng soá low vaø high thích hôïp. // Daønh cho danh saùch lieân tuïc trong chöông 4. template void Sortable_list::build_heap() /* post: Caùc phaàn töû trong danh saùch ñöôïc saép xeáp ñeå thoûa ñieàu kieän cuûa heap. uses: insert_heap. */ { int low; // Caùc phaàn töû töø low+1 ñeán cuoái danh saùch thoûa ñieàu kieän cuûa heap. for (low = count / 2 - 1; low >= 0; low--) { Record current = entry[low]; insert_heap(current, low, count - 1); } } 8.9. Radix Sort Cuoái cuøng chuùng ta xem xeùt moät giaûi thuaät saép thöù töï hôi ñaëc bieät moät chuùt, ñoù laø giaûi thuaät thöôøng ñöôïc duøng cho caùc phaàn töû coù khoùa laø caùc chuoãi kyù töï. Giaûi thuaät radix_sort voán ñöôïc ñöa ra trong nhöõng ngaøy ñaàu cuûa lòch söû maùy tính ñeå söû duïng cho caùc theû ñuïc loã, nhöng ñaõ ñöôïc phaùt trieån thaønh moät phöông phaùp saép thöù töï raát hieäu quaû cho caùc caáu truùc döõ lieäu coù lieân keát . YÙ töôûng ñöôïc trình baøy döôùi ñaây cuõng ñöôïc xem nhö moät öùng duïng khaù thuù vò cuûa hieän thöïc lieân keát cuûa CTDL haøng ñôïi. Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 177 8.9.1. YÙ töôûng YÙ töôûng cuûa giaûi thuaät laø xeùt töøng kyù töï moät vaø chia danh saùch thaønh nhieàu danh saùch con, soá danh saùch con phuï thuoäc vaøo soá kyù töï khaùc nhau coù trong khoùa. Giaû söû caùc khoùa laø caùc töø goàm caùc chöõ caùi, thì chuùng ta chia danh saùch caàn saép thöù töï ra 26 danh saùch con taïi moãi böôùc vaø phaân phoái caùc phaàn töû vaøo caùc danh saùch con naøy töông öùng vôùi moät trong caùc kyù töï coù trong khoùa. Ñeå saép thöù töï caùc töø, tröôùc tieân ngöôøi ta thöôøng chia chuùng thaønh 26 danh saùch con theo kyù töï ñaàu tieân, sau ñoù laïi chia moãi danh saùch con thaønh 26 danh saùch con theo kyù töï thöù hai, vaø cöù theá tieáp tuïc. Nhö vaäy soá danh saùch con seõ trôû neân quaù lôùn, chuùng ta khoù naém giöõ ñöôïc. YÙ töôûng döôùi ñaây nhaèm traùnh soá löôïng danh saùch con buøng noå quaù lôùn. Thay vì laàn löôït xeùt caùc kyù töï töø traùi qua phaûi, chuùng ta seõ xeùt theo thöù töï töø phaûi qua traùi. Tröôùc tieân neân chia caùc phaàn töû vaøo caùc danh saùch con theo vò trí cuûa kyù töï cuoái cuûa töø daøi nhaát. Sau ñoù caùc danh saùch con naøy laïi ñöôïc noái laïi thaønh moät danh saùch, thöù töï caùc töø trong moãi danh saùch con giöõ nguyeân, thöù töï noái caùc danh saùch con tuaân theo thöù töï alphabet cuûa caùc kyù töï taïi vò trí vöøa xeùt. Danh saùch naøy laïi ñöôïc chia theo vò trí keá tröôùc vò trí vöøa roài, roài laïi ñöôïc noái laïi. Cöù theá tieáp tuïc cho ñeán khi danh saùch ñöôïc chia theo vò trí ñaàu tieân cuûa caùc chuoãi kyù töï vaø ñöôïc noái laïi, chuùng ta seõ coù moät danh saùch caùc töø coù thöù töï theo alphabet. Quaù trình naøy ñöôïc minh hoïa qua vieäc saép thöù töï 9 töø coù chieàu daøi toái ña ba kyù töï trong hình 8.16. Coät beân traùi cuûa hình veõ laø thöù töï ban ñaàu cuûa caùc töø. Chuùng ñöôïc chia thaønh 3 danh saùch töông öùng vôùi 3 kyù töï khaùc nhau ôû vò trí cuoái cuøng, keát quaû ôû coät thöù hai cuûa hình veõ, moãi hình khoái bieåu dieãn moät danh saùch con. Thöù töï giöõa caùc töø trong moät danh saùch con khoâng thay ñoåi so vôùi thöù töï giöõa chuùng trong danh saùch lôùn khi chöa ñöôïc chia. Tieáp theo, caùc danh saùch con ñöôïc noái laïi vaø ñöôïc chia thaønh 2 danh saùch con töông öùng 2 kyù töï khaùc nhau ôû vò trí keá cuoái (vò trí thöù hai cuûa töø) nhö coät thöù ba trong hình. Cuoái cuøng chuùng ñöôïc noái laïi vaø chia thaønh 4 danh saùch con töông öùng 4 kyù töï khaùc nhau ôû vò trí ñaàu cuûa caùc töø. Khi caùc danh saùch con ñöôïc noái laïi thì chuùng ta coù moät danh saùch ñaõ coù thöù töï. 8.9.2. Hieän thöïc Chuùng ta seõ hieän thöïc phöông phaùp naøy trong C++ cho danh saùch caùc maãu tin coù khoùa laø caùc chuoãi kyù töï. Sau moãi laàn phaân hoaïch thaønh caùc danh saùch con, chuùng ñöôïc noái laïi thaønh moät danh saùch ñeå sau ñoù laïi ñöôïc phaân hoaïch tieáp töông öùng vôùi vò trí keá tröôùc trong khoùa. Chuùng ta söû duïng caùc haøng ñôïi ñeå chöùa caùc danh saùch con, do trong giaûi thuaät, khi phaân hoaïch, caùc phaàn töû luoân ñöôïc theâm vaøo cuoái caùc danh saùch con vaø khi noái laïi thì caùc phaàn töû laïi ñöôïc laáy ra töø ñaàu caùc danh saùch con (FIFO). Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 178 Neáu chuùng ta duøng caùc CTDL haøng vaø danh saùch toång quaùt coù saün ñeå xöû lyù, seõ coù moät soá thao taùc di chuyeån caùc phaàn töû khoâng caàn thieát. Ngöôïc laïi, neáu söû duïng caáu truùc lieân keát, coù theå noái caùc haøng lieân keát thaønh moät danh saùch kieân keát baèng caùch noái rear cuûa haøng naøy vaøo front cuûa haøng kia, thì chöông trình seõ hieäu quaû hôn raát nhieàu. Quaù trình naøy ñöôïc minh hoïa trong hình 8.17. Chöông trình radix_sort nhö vaäy caàn coù theâm lôùp daãn xuaát töø lôùp Queue coù boå sung phöông thöùc ñeå noái caùc haøng laïi vôùi nhau, phaàn naøy coù theå xem nhö baøi taäp. Phaàn minh hoïa tieáp theo chuùng ta chæ söû duïng lôùp Queue ñôn giaûn coù saün. Chuùng ta seõ duøng moät maûng coù 28 haøng ñôïi ñeå chöùa 28 danh saùch con. Vò trí 0 töông öùng kyù töï troáng (khoaûng traéng khoâng coù kyù töï), caùc vò trí töø 1 ñeán 26 töông öùng caùc kyù töï chöõ caùi (khoâng phaân bieät chöõ hoa chöõ thöôøng), coøn vò trí 27 töông öùng moïi kyù töï coøn laïi (neáu coù) xuaát hieän trong khoùa. Vieäc xöû lyù seõ ñöôïc laëp laïi töø kyù töï cuoái ñeán kyù töï ñaàu trong khoùa, moãi laàn laëp chuùng ta seõ duyeät qua danh saùch lieân keát ñeå theâm töøng phaàn töû vaøo cuoái moãi danh saùch con töông öùng. Sau khi danh saùch ñaõ ñöôïc phaân hoaïch, chuùng ta noái caùc danh saùch con laïi thaønh moät danh saùch. Cuoái voøng laëp danh saùch ñaõ coù thöù töï. Chuùng ta seõ hieän thöïc radix_sort nhö laø moät phöông thöùc cuûa Sortable_list. Hình 8.16 – Tieán trình cuûa radix_sort. Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 179 // Coù theå söû duïng cho baát kyø hieän thöïc naøo cuûa List. template class Sortable_list: public List { public: // Caùc phöông thöùc saép thöù töï. void radix_sort(); private: // Caùc haøm phuï trôï. void rethread(Queue queues[]); }; ÔÛ ñaây, lôùp cô sôû List coù theå laø baát kyø hieän thöïc naøo cuûa List trong chöông 4. Haøm phuï trôï rethread seõ ñöôïc söû duïng ñeå noái caùc haøng ñôïi. Chuùng ta seõ söû duïng caùc phöông thöùc cuûa lôùp Record, char key_letter(int position) traû veà kyù töï taïi position cuûa khoùa, hoaëc traû veà khoaûng traéng neáu chieàu daøi cuûa khoùa nhoû hôn position. Ñònh nghóa Record nhö sau: Hình 8.17 – Radix sort lieân keát Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 180 class Record { public: char key_letter(int position) const; Record(); // constructor maëc ñònh. operator Key() const; // traû veà khoùa cuûa phaàn töû. // Caùc phöông thöùc vaø caùc thuoäc tính khaùc cuûa lôùp. }; 8.9.2.1. Phöông phaùp saép thöù töï radix_sort const int max_chars = 28; template void Sortable_list::radix_sort() /* post: Caùc phaàn töû cuûa danh saùch ñaõ ñöôïc saép theo thöù töï alphabet. uses: Caùc phöông thöùc cuûa caùc lôùp List, Queue, vaø Record; functions position and rethread. */ { Record data; Queue queues[max_chars]; for (int position = key_size - 1; position >= 0; position--) { // Laëp töø vò trí cuoái ñeán vò trí ñaàu caùc chuoãi kyù töï. while (remove(0, data) == success) { int queue_number = alphabetic_order(data.key_letter(position)); queues[queue_number].append(data); // Ñöa vaøo haøng thích hôïp. } rethread(queues);// Noái caùc danh saùch con trong caùc haøng thaønh danh saùch. } } Haøm naøy söû duïng hai haøm phuï trôï: alphabetic_order ñeå xaùc ñònh haøng ñôïi töông öùng vôùi moät kyù töï cho tröôùc, vaø Sortable_list::rethread() ñeå noái caùc haøng. Chuùng ta coù theå duøng baát kyø hieän thöïc naøo cuûa haøng töông thích vôùi ñaëc taû Queue tröøu töôïng trong chöông 3. 8.9.2.2. Choïn moät queue Haøm alphabetic_order laáy thöù töï cuûa moät kyù töï cho tröôùc trong baûng chöõ caùi, vôùi quy öôùc raèng taát caû caùc kyù töï khoâng phaûi laø kyù töï chöõ caùi seõ coù cuøng thöù töï laø 27, khoaûng traéng coù thöù töï 0. Haøm khoâng phaân bieät chöõ hoa vaø chöõ thöôøng. int alphabetic_order(char c) /* post: Traû veà thöù töï cuûa kyù töï trong c theo thöù töï alphabet, hoaëc traû veà 0 neáu c laø khoaûng traéng. */ { if (c == ' ') return 0; if ('a' <= c && c <= 'z') return c - 'a' + 1; if ('A' <= c && c <= 'Z') return c - 'A' + 1; return 27; } Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 181 8.9.2.3. Noái caùc haøng Haøm rethread noái 28 haøng laïi thaønh moät Sortable_list. Haøm cuõng laøm roãng taát caû caùc haøng naøy ñeå chuùng coù theå ñöôïc söû duïng trong laàn laëp sau cuûa giaûi thuaät. Haøm naøy coù theå ñöôïc vieát laïi theo caùch phuï thuoäc vaøo hieän thöïc cuûa caùc haøng ñeå giaûi thuaät radix_sort coù theå chaïy nhanh hôn, chuùng ta xem nhö baøi taäp. template void Sortable_list::rethread(Queue queues[]) /* post: Moïi haøng ñöôïc noái laïi thaønh moät danh saùch, caùc haøng trôû thaønh roãng. uses: Caùc phöông thöùc cuûa caùc lôùp List vaø Queue. */ { Record data; for (int i = 0; i < max_chars; i++) while (!queues[i].empty()) { queues[i].retrieve(data); insert(size(), data); queues[i].serve(); } } 8.9.3. Phaân tích phöông phaùp radix_sort Chuù yù raèng thôøi gian ñeå chaïy radix_sort laø θ(nk), n laø soá phaàn töû caàn saép thöù töï vaø k laø soá kyù töï coù trong khoùa. Thôøi gian caàn cho caùc phöông phaùp saép thöù töï khaùc cuûa chuùng ta phuï thuoäc vaøo n vaø khoâng phuï thuoäc tröïc tieáp vaøo chieàu daøi cuûa khoùa. Thôøi gian toát nhaát laø ñoái vôùi merge_sort: nlgn + O(n). Hieäu quaû töông ñoái cuûa caùc phöông phaùp coù lieân quan ñeán kích thöôùc nk vaø n lgn, coù nghóa laø, k vaø lgn. Neáu caùc khoùa coù chieàu daøi lôùn vaø soá phaàn töû caàn saép thöù töï khoâng lôùn (k lôùn vaø lg n töông ñoái nhoû), thì caùc phöông phaùp khaùc, töïa nhö merge_sort, seõ hieäu quaû hôn radix_sort; ngöôïc laïi neáu k nhoû (caùc khoùa ngaén) vaø soá phaàn töû caàn saép thöù töï nhieàu, thì radix_sort seõ nhanh hôn moïi phöông phaùp saép thöù töï maø chuùng ta ñaõ bieát. Chöông 8 – Saép xeáp Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 182