Tài liệu Cấu trúc dữ liệu 2005 P8 doc

Chöông 8 – Saép xeáp

Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 149

Chöông 8 – SAÉP XEÁP

Chöông naøy giôùi thieäu moät soá phöông phaùp saép xeáp cho caû danh saùch lieân tuïc

vaø danh saùch lieân keát.

8.1. Giôùi thieäu

Ñeå truy xuaát thoâng tin nhanh choùng vaø chính xaùc, ngöôøi ta thöôøng saép xeáp

thoâng tin theo moät traät töï hôïp lyù naøo ñoù. Coù moät soá caáu truùc döõ lieäu maø ñònh

nghóa cuûa chuùng ñaõ bao haøm traät töï cuûa caùc phaàn töû, khi ñoù moãi phaàn töû khi

theâm vaøo ñeàu phaûi ñaûm baûo traät töï naøy. Trong chöông naøy chuùng ta seõ tìm hieåu

vieäc saép xeáp caùc danh saùch chöa coù thöù töï trôû neân coù thöù töï.

Vì saép xeáp coù vai troø quan troïng neân coù raát nhieàu phöông phaùp ñöôïc ñöa ra ñeå

giaûi quyeát baøi toaùn naøy. Caùc phöông phaùp naøy khaùc nhau ôû nhieàu ñieåm, trong ñoù

ñieåm quan troïng nhaát laø döõ lieäu caàn saép xeáp naèm toaøn boä trong boä nhôù chính

(töông öùng caùc giaûi thuaät saép xeáp noäi) hay coù moät phaàn naèm trong thieát bò löu tröõ

ngoaøi (töông öùng caùc giaûi thuaät saép xeáp ngoaïi). Trong chöông naøy chuùng ta chæ

xem xeùt moät soá giaûi thuaät saép xeáp noäi.

Chuùng ta seõ söû duïng caùc lôùp ñaõ coù ôû chöông 4 vaø chöông 7. Ngoaøi ra, trong

tröôøng hôïp khi coù nhieàu phaàn töû khaùc nhau coù cuøng khoùa thì caùc giaûi thuaät saép

xeáp khaùc nhau seõ cho ra nhöõng thöù töï khaùc nhau giöõa chuùng, vaø ñoâi khi söï khaùc

nhau naøy cuõng coù aûnh höôûng ñeán caùc öùng duïng.

Trong caùc giaûi thuaät tìm kieám, khoái löôïng coâng vieäc phaûi thöïc hieän coù lieân

quan chaët cheõ vôùi soá laàn so saùnh caùc khoùa. Trong caùc giaûi thuaät saép xeáp thì ñieàu

naøy cuõng ñuùng. Ngoaøi ra, caùc giaûi thuaät saép xeáp coøn phaûi di chuyeån caùc phaàn töû.

Coâng vieäc naøy cuõng chieám nhieàu thôøi gian, ñaëc bieät khi caùc phaàn töû coù kích thöôùc

lôùn ñöôïc löu tröõ trong danh saùch lieân tuïc.

Ñeå coù theå ñaït ñöôïc hieäu quaû cao, caùc giaûi thuaät saép xeáp thöôøng phaûi taän duïng

caùc ñaëc ñieåm rieâng cuûa töøng loaïi caáu truùc döõ lieäu. Chuùng ta seõ vieát caùc giaûi thuaät

saép xeáp döôùi daïng caùc phöông thöùc cuûa lôùp List.

template <class 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ôï.

};

Chöông 8 – Saép xeáp

Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 150

Chuùng ta coù theå söû duïng baát kyø daïng hieän thöïc naøo cuûa lôùp List trong chöông

4. Caùc phaàn töû döõ lieäu trong Sortable_list coù kieåu laø Record. Nhö ñaõ giôùi

thieäu trong chöông 7, Record coù caùc tính chaát sau ñaây:

• Moãi maãu tin coù moät khoaù ñi keøm.

• Caùc khoùa coù theå ñöôïc so saùnh vôùi nhau baèng caùc toaùn töû so saùnh.

• Moät maåu tin coù theå ñöôïc chuyeån ñoåi töï ñoäng thaønh moät khoùa. Do ñoù coù theå

so saùnh caùc maãu tin vôùi nhau hoaëc so saùnh maãu tin vôùi khoaù thoâng qua vieäc

chuyeån ñoåi maãu tin veà khoùa lieân quan ñeán noù.

8.2. Saép xeáp kieåu cheøn (Insertion Sort)

Phöông phaùp saép xeáp chen vaøo döïa treân yù töôûng cheøn phaàn töû vaøo danh saùch

ñaõ coù thöù töï.

8.2.1.Cheøn phaàn töû vaøo danh saùch ñaõ coù thöù töï

Ñònh nghóa danh saùch coù thöù töï ñaõ ñöôïc trình baøy trong chöông 7.

Vôùi caùc danh saùch coù thöù töï, moät soá taùc vuï chæ söû duïng khoùa cuûa phaàn töû chöù

khoâng söû duïng vò trí cuûa phaàn töû:

• retrieve: truy xuaát moät phaàn töû coù khoùa cho tröôùc.

• insert: cheøn moät phaàn töû coù khoùa cho tröôùc sao cho danh saùch vaãn coøn

thöù töï, vò trí cuûa phaàn töû môùi ñöôïc xaùc ñònh bôûi khoùa cuûa noù.

Pheùp theâm vaøo vaø pheùp truy xuaát coù theå khoâng cho keát quaû duy nhaát trong

tröôøng hôïp coù nhieàu phaàn töû truøng khoùa. Pheùp truy xuaát phaàn töû döïa treân khoùa

chính laø pheùp tìm kieám ñaõ ñöôïc trình baøy trong chöông 7.

Ñeå theâm phaàn töû môùi vaøo danh saùch lieân tuïc ñaõ coù thöù töï, caùc phaàn töû seõ

ñöùng sau noù phaûi ñöôïc dòch chuyeån ñeå taïo choã troáng. Chuùng ta caàn thöïc hieän pheùp

Hình 8.1 – Cheøn phaàn töû vaøo danh saùch ñaõ coù thöù töï.

Chöông 8 – Saép xeáp

Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät 151

tìm kieám ñeå tìm vò trí chen vaøo. Vì danh saùch ñaõ coù thöù töï neân ta coù theå söû duïng

pheùp tìm kieám nhò phaân. Tuy nhieân, do thôøi gian caàn cho vieäc di chuyeån caùc phaàn

töû lôùn hôn nhieàu so vôùi thôøi gian tìm kieám, neân vieäc tieát kieäm thôøi gian tìm kieám

cuõng khoâng caûi thieän thôøi gian chaïy toaøn boä giaûi thuaät ñöôïc bao nhieâu. Neáu vieäc

tìm kieám tuaàn töï töø cuoái danh saùch coù thöù töï ñöôïc thöïc hieän ñoàng thôøi vôùi vieäc di

chuyeån phaàn töû, thì chi phí cho moät laàn chen moät phaàn töû môùi laø toái thieåu.

8.2.2.Saép xeáp kieåu cheøn cho danh saùch lieân tuïc

Taùc vuï theâm moät phaàn töû vaøo danh saùch coù thöù töï laø cô sôû cuûa pheùp saép xeáp

kieåu cheøn. Ñeå saép xeáp moät danh saùch chöa coù thöù töï, chuùng ta laàn löôït laáy ra töøng

phaàn töû cuûa noù vaø duøng taùc vuï treân ñeå ñöa vaøo moät danh saùch luùc ñaàu laø roãng.

Phöông phaùp naøy ñöôïc minh hoïa trong hình 8.2. Hình naøy chæ ra caùc böôùc caàn

thieát ñeå saép xeáp moät danh saùch coù 6 töø. Nhìn hình veõ chuùng ta thaáy, phaàn danh

saùch ñaõ coù thöù töï goàm caùc phaàn töû töø chæ soá sorted trôû leân treân, caùc phaàn töû töø

chæ soá unsorted trôû xuoáng döôùi laø chöa coù thöù töï. Böôùc ñaàu tieân, töø “hen” ñöôïc

xem laø ñaõ coù thöù töï do danh saùch coù moät phaàn töû ñöông nhieân laø danh saùch coù

thöù töï. Taïi moãi böôùc, phaàn töû ñaàu tieân trong phaàn danh saùch beân döôùi ñöôïc laáy ra

vaø cheøn vaøo vò trí thích hôïp trong phaàn danh saùch ñaõ coù thöù töï beân treân. Ñeå coù

choã cheøn phaàn töû naøy, moät soá phaàn töû khaùc trong phaàn danh saùch ñaõ coù thöù töï

ñöôïc di chuyeån veà phía cuoái danh saùch.

Trong phöông thöùc duôùi ñaây, first_unsorted laø chæ soá phaàn töû ñaàu tieân

trong phaàn danh saùch chöa coù thöù töï, vaø current laø bieán taïm naém giöõ phaàn töû

naøy cho ñeán khi tìm ñöôïc choã troáng ñeå cheøn vaøo.

Hình 8.2- Ví duï veà saép xeáp kieåu cheøn cho danh saùch lieân tuïc.