Giáo trình Cấu trúc dữ liệu và giải thuật - Phần 2: Các cấu trúc dữ liệu - Chương 8: Sắp xếp
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 Record>
class Sortable_list:public List<Record> {
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 Listtrong 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, Recordcoù 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 <class Record>
void Sortable_list<Record>::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;
}
}
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
currentmoä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 <class Record>
void Sortable_list<Record>::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 <Record> *first_unsorted,
*last_sorted,
*current,
*trailing;
if (head != NULL) {
last_sorted =
// Loaïi tröôøng hôïp danh saùch roãng vaø
// tröôøng hôïp danh saùch chæ coù 1 phaàn töû.
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)
last_sorted = first_unsorted;
else {
//vò trí ñang coù ñaõ ñuùng.
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_keycuû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 <class Record>
void Sortable_list<Record>::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 <class Record>
// Daønh cho danh saùch lieân tuïc trong chöông 4.
int Sortable_list<Record>::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 <class Record>
void Sortable_list<Record>::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
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
157
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 <class Record>
void Sortable_list<Record>::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_sortveà 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_sortvôù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_sortcho 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_sortcho danh saùch lieân keát).
Merge_sortcoø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 <class Record>
void Sortable_list<Record>::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 <class Record>
void Sortable_list<Record>::recursive_merge_sort(Node<Record> *&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<Record> *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û midpointtieán moät böôcù vaø con troû positiontieán hai böôùc trong moãi laàn laëp,
khi positionñeán cuoái danh saùch thì midpointdöøng ngay giöõa danh saùch.
// Daønh cho danh saùch lieân keát trong chöông 4.
template <class Record>
Node<Record> *Sortable_list<Record>::divide_from(Node<Record> *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<Record> *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) {
position = position->next;
if (position != NULL) {
midpoint = midpoint->next;
position = position->next;
}
// Tìm phaàn töû naèm giöõa danh saùch.
}
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<Record> *merge(Node<Record> *first, Node<Record> *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 <class Record>
Node<Record> *Sortable_list<Record>::merge(Node<Record> *first,
Node<Record> *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<Record> *last_sorted;
Node<Record> combined;
// Phaàn töû giaû.
last_sorted = &combined; // Danh saùch keát quaû nhaän daàn caùc phaàn töû töø firstvaø
// second, theo thöù töï töø phaàn töû nhoû ñeán phaàn töû lôùn.
while (first != NULL && second != NULL) {
if (first->entry <= second->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_sortcho 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 <class Record>
void Sortable_list<Record>::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 <class Record>
void Sortable_list<Record>::recursive_quick_sort(int low, int high)
/*
pre: low vaø highlaø 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_positionsao 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ø cacù 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
Tải về để xem bản đầy đủ
34 trang
25040
Free
Bạn đang xem 20 trang mẫu của tài liệu "Giáo trình Cấu trúc dữ liệu và giải thuật - Phần 2: Các cấu trúc dữ liệu - Chương 8: Sắp xếp", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- giao_trinh_cau_truc_du_lieu_va_giai_thuat_phan_2_cac_cau_tru.pdf
