text:
Cấu trúc dữ liệu (chương 8)
Chia sẻ: Nguyễn Thị Giỏi | Ngày: | Loại File: PDF | Số trang:34
lượt xem 89
download
Cấu trúc dữ liệu (chương 8)
Để truy xuất thông tin nhanh chóng và chính xác, người ta thường sắp xếp thông tin theo một trật tự hợp lý nào đó. Có một số cấu trúc dữ liệu mà định nghĩa của chúng đã bao hàm..
Bình luận(0) Đăng nhập để gửi bình luận!
Nội dung Text: Cấu trúc dữ liệu (chương 8)
- Chöông 8 – Saép xeáp 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ôï. }; Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 149
- Chöông 8 – Saép xeáp 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ù. Hình 8.1 – Cheøn phaàn töû vaøo danh saùch ñaõ coù thöù töï. 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 Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 150
- Chöông 8 – Saép xeáp 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. Hình 8.2- Ví duï veà saép xeáp kieåu cheøn cho danh saùch lieân tuïc. 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. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 151
- Chöông 8 – Saép xeáp Hình 8.3- Böôùc chính cuûa giaûi thuaät saép xeáp kieåu cheøn. // 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]; // Di chuyeån daàn caùc phaàn töû veà phía sau ñeå tìm choã troáng thích hôïp. do { entry[position] = entry[position - 1]; position--; } while (position > 0 && entry[position - 1] > current); entry[position] = current; } } Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 152
- Chöông 8 – Saép xeáp 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. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 153
- Chöông 8 – Saép xeáp 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; // Loaïi tröôøng hôïp danh saùch roãng vaø if (head != NULL) { // tröôøng hôïp danh saùch chæ coù 1 phaàn töû. last_sorted = head; while (last_sorted->next != NULL) { first_unsorted = last_sorted->next; if (first_unsorted->entry < head->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. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 154
- Chöông 8 – Saép xeáp if (first_unsorted == current) // vò trí ñang coù ñaõ ñuùng. last_sorted = first_unsorted; 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. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 155
- Chöông 8 – Saép xeáp 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ù. Hình 8.6- Moät böôùc trong saép xeáp kieåu choïn. 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. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 156
- Chöông 8 – Saép xeáp // 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
- Chöông 8 – Saép xeáp 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. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 158
- Chöông 8 – Saép xeáp Hình 8.7 – Ví duï veà Shell_Sort. 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. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 159
- Chöông 8 – Saép xeáp 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; } } Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 160
- Chöông 8 – Saép xeáp 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á. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 161
- Chöông 8 – Saép xeáp 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 Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 162
- Chöông 8 – Saép xeáp 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 Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 163
- Chöông 8 – Saép xeáp Hình 8.10- Caây ñeä quy cho Quick_sort vôùi 7 phaàn töû. 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); } Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 164
- Chöông 8 – Saép xeáp 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; // Tìm phaàn töû naèm giöõa danh saùch. while (position != NULL) { position = position->next; if (position != NULL) { midpoint = midpoint->next; position = position->next; } } second_half = midpoint->next; midpoint->next = NULL; return second_half; } Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 165
- Chöông 8 – Saép xeáp 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öï. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 166
- Chöông 8 – Saép xeáp // 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; // Phaàn töû giaû. Node combined; 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ì. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 167
- Chöông 8 – Saép xeáp Ñ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; Danh saùch coù nhieàu hôn moät phaàn töû. if (low < high) { // 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. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 168
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Kỹ thuật lập trình - Chương 4: Khái quát về cấu trúc dữ liệu
32 p | 279 | 134
-
Cấu trúc dữ liệu và giải thuật - Chương 2 - Tìm kiếm và sắp xếp
204 p | 284 | 124
-
Cấu trúc dữ liệu (chương 9)
54 p | 136 | 86
-
Cấu trúc dữ liệu - Chương 1 Các khái niệm cơ bản
4 p | 341 | 82
-
Cấu trúc dữ liệu (chương 10)
46 p | 147 | 68
-
Giáo trình CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - Chương 1
5 p | 202 | 60
-
Cấu trúc dữ liệu và giải thuật - chương 5
27 p | 117 | 27
-
Cấu trúc dữ liệu và giải thuật - chương 1
20 p | 111 | 19
-
Giáo trình cấu trúc dữ liệu part 8
16 p | 38 | 18
-
Cấu trúc dữ liệu và giải thuật - chương 3
22 p | 129 | 18
-
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT (501040) - Chương 1: Tổng quan
20 p | 55 | 14
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - ĐH Bách khoa TP. HCM
28 p | 26 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 8 - ĐH Bách khoa TP. HCM
65 p | 15 | 6
-
Bài giảng cấu trúc dữ liệu - Chương 2 Cấu trúc dữ liệu danh sách Phần 2
41 p | 49 | 5
-
Bài giảng cấu trúc dữ liệu - Chương 1 Nhập môn cấu trúc dữ liệu
33 p | 38 | 4
-
Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 1 - ThS. Phạn Nguyệt Thuần
31 p | 8 | 4
-
Bài giảng cấu trúc dữ liệu - Chương 2 Cấu trúc dữ liệu danh sách Phần 1
25 p | 43 | 3

markdown:
# Cấu trúc dữ liệu (chương 8)
Chia sẻ: Nguyễn Thị Giỏi | Ngày: | Loại File: PDF | Số trang:34
lượt xem 89
download
![](http://image.tlvnimg.com/document/thumbnail/2009/20091105/ntgioi120403/80x100/ctdl_2005_chuong_8_5239.jpg)
##
Cấu trúc dữ liệu (chương 8)
[Vui lòng tải xuống để xem tài liệu đầy đủ](javascript:void(0);)
Download
![](http://static.tlvnimg.com/b2013az/templates/version1/default/images/down16x21.png)
Để truy xuất thông tin nhanh chóng và chính xác, người ta thường sắp xếp thông tin theo một trật tự hợp lý nào đó. Có một số cấu trúc dữ liệu mà định nghĩa của chúng đã bao hàm..
Bình luận(0)
[Đăng nhập để gửi bình luận!](javascript:void(0);)
##
Nội dung Text: Cấu trúc dữ liệu (chương 8)
- Chöông 8 – Saép xeáp 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ôï. }; Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 149
- Chöông 8 – Saép xeáp 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ù. Hình 8.1 – Cheøn phaàn töû vaøo danh saùch ñaõ coù thöù töï. 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 Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 150
- Chöông 8 – Saép xeáp 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. Hình 8.2- Ví duï veà saép xeáp kieåu cheøn cho danh saùch lieân tuïc. 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. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 151
- Chöông 8 – Saép xeáp Hình 8.3- Böôùc chính cuûa giaûi thuaät saép xeáp kieåu cheøn. // 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]; // Di chuyeån daàn caùc phaàn töû veà phía sau ñeå tìm choã troáng thích hôïp. do { entry[position] = entry[position - 1]; position--; } while (position > 0 && entry[position - 1] > current); entry[position] = current; } } Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 152
- Chöông 8 – Saép xeáp 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. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 153
- Chöông 8 – Saép xeáp 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; // Loaïi tröôøng hôïp danh saùch roãng vaø if (head != NULL) { // tröôøng hôïp danh saùch chæ coù 1 phaàn töû. last_sorted = head; while (last_sorted->next != NULL) { first_unsorted = last_sorted->next; if (first_unsorted->entry < head->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. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 154
- Chöông 8 – Saép xeáp if (first_unsorted == current) // vò trí ñang coù ñaõ ñuùng. last_sorted = first_unsorted; 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. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 155
- Chöông 8 – Saép xeáp 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ù. Hình 8.6- Moät böôùc trong saép xeáp kieåu choïn. 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. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 156
- Chöông 8 – Saép xeáp // 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
- Chöông 8 – Saép xeáp 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. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 158
- Chöông 8 – Saép xeáp Hình 8.7 – Ví duï veà Shell_Sort. 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. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 159
- Chöông 8 – Saép xeáp 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; } } Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 160
- Chöông 8 – Saép xeáp 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á. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 161
- Chöông 8 – Saép xeáp 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 Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 162
- Chöông 8 – Saép xeáp 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 Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 163
- Chöông 8 – Saép xeáp Hình 8.10- Caây ñeä quy cho Quick_sort vôùi 7 phaàn töû. 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); } Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 164
- Chöông 8 – Saép xeáp 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; // Tìm phaàn töû naèm giöõa danh saùch. while (position != NULL) { position = position->next; if (position != NULL) { midpoint = midpoint->next; position = position->next; } } second_half = midpoint->next; midpoint->next = NULL; return second_half; } Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 165
- Chöông 8 – Saép xeáp 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öï. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 166
- Chöông 8 – Saép xeáp // 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; // Phaàn töû giaû. Node combined; 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ì. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 167
- Chöông 8 – Saép xeáp Ñ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; Danh saùch coù nhieàu hôn moät phaàn töû. if (low < high) { // 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. Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 168
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Kỹ thuật lập trình - Chương 4: Khái quát về cấu trúc dữ liệu
32 p |
279 |
134
-
Cấu trúc dữ liệu và giải thuật - Chương 2 - Tìm kiếm và sắp xếp
204 p |
284 |
124
-
Cấu trúc dữ liệu (chương 9)
54 p |
136 |
86
-
Cấu trúc dữ liệu - Chương 1 Các khái niệm cơ bản
4 p |
341 |
82
-
Cấu trúc dữ liệu (chương 10)
46 p |
147 |
68
-
Giáo trình CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT - Chương 1
5 p |
202 |
60
-
Cấu trúc dữ liệu và giải thuật - chương 5
27 p |
117 |
27
-
Cấu trúc dữ liệu và giải thuật - chương 1
20 p |
111 |
19
-
Giáo trình cấu trúc dữ liệu part 8
16 p |
38 |
18
-
Cấu trúc dữ liệu và giải thuật - chương 3
22 p |
129 |
18
-
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT (501040) - Chương 1: Tổng quan
20 p |
55 |
14
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 5 - ĐH Bách khoa TP. HCM
28 p |
26 |
6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 8 - ĐH Bách khoa TP. HCM
65 p |
15 |
6
-
Bài giảng cấu trúc dữ liệu - Chương 2 Cấu trúc dữ liệu danh sách Phần 2
41 p |
49 |
5
-
Bài giảng cấu trúc dữ liệu - Chương 1 Nhập môn cấu trúc dữ liệu
33 p |
38 |
4
-
Bài giảng Cấu trúc dữ liệu và thuật toán: Chương 1 - ThS. Phạn Nguyệt Thuần
31 p |
8 |
4
-
Bài giảng cấu trúc dữ liệu - Chương 2 Cấu trúc dữ liệu danh sách Phần 1
25 p |
43 |
3

Set-Cookie: TLDEVNamespace=dadvjou52q6d3lnor5n4d8v183; path=/; domain=.tailieu.vn; HttpOnly

Server: Apache/2.2.31 (CentOS)

Cache-Control: no-store, no-cache, must-revalidate, post-check=0, pre-check=0

Pragma: no-cache