Chương 8: Sắp xếp - Cấu trúc dữ liệu và giải thuật | Trường Đại học CNTT Thành Phố Hồ Chí Minh

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. 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 .
Khai baùo cuûa caùc phöông thöùc saép xeáp ñöôïc theâm vaøo ñaây Caùc haøm phuï trôï.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
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 trong chöông
4. Caùc phaàn töû döõ lieäu trong coù kieåu laø . Nhö ñaõ giôùi thieäu trong chöông 7,
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ù.
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öï.
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öû: •
: truy xuaát moät phaàn töû coù khoùa cho tröôùc. •
: 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
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.
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á
trôû leân treân, caùc phaàn töû töø chæ soá
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,
laø chæ soá phaàn töû ñaàu tieân
trong phaàn danh saùch chöa coù thöù töï, vaø
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
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.
Caùc phaàn töû trong danh saùch ñaõ ñöôïc saép xeáp theo thöù töï khoâng giaûm.
Caùc phöông thöùc cuûa lôùp
Chæ soá phaàn töû ñaàu tieân trong phaàn danh saùch chöa coù thöù töï.
Chæ soá duøng cho vieäc di chuyeån caùc phaàn töû veà phía sau.
aém giöõ phaàn töû ñang ñöôïc tìm choã cheøn vaøo phaàn danh saùch ñaõ coù thöù töï.
Di chuyeån daàn caùc phaàn töû veà phía sau ñeå tìm choã troáng thích hôïp.
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
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
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 , voøng laëp
ñ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
. Tröôøng hôïp vò trí ñuùng cuûa 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ø .
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û
chæ phaàn töû cuoái cuøng
cuûa phaàn danh saùch ñaõ coù thöù töï,
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 ñeå chæ vaøo phaàn töû naøy vaø bieán
ñeå tìm vò trí thích hôïp cho vieäc cheøn phaàn töû
vaøo. Neáu vò trí ñuùng cuûa laø ñaàu danh saùch
thì noù ñöôïc cheøn vaøo vò trí naøy. Ngöôïc laïi,
ñöôïc di chuyeån veà phía cuoái
danh saùch cho ñeán khi coù ( vaø
ñöôïc theâm vaøo ngay tröôùc
. Ñeå coù theå thöïc hieän vieäc theâm vaøo tröôùc
, chuùng ta caàn moät con troû luoân ñöùng tröôùc 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
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ù , neân phaàn töû
ñoùng luoân vai troø cuûa phaàn töû caàm canh trong khi
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.
Caùc phaàn töû trong danh saùch ñaõ ñöôïc saép xeáp theo thöù töï khoâng giaûm.
Caùc phöông thöùc cuûa lôùp
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öû.
ñöôïc cheøn vaøo ñaàu danh saùch. Tìm vò trí thích hôïp.
ñöôïc cheøn vaøo giöõa vaø
Giaùo trình Caáu truùc döõ lieäu vaø Giaûi thuaät
Chöông 8 – Saép xeáp
vò trí ñang coù ñaõ ñuùng.
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.
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ù. 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
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.
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ôï cuûa
ñ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
Chöông 8 – Saép xeáp
Daønh cho danh saùch lieân tuïc trong chöông 4.
Caùc phaàn töû trong danh saùch ñaõ ñöôïc saép xeáp theo thöù töï khoâng giaûm.
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 .
Daønh cho danh saùch lieân tuïc trong chöông 4. vaø
laø hai vò trí hôïp leä trong danh saùch vaø
traû veà vò trí phaàn töû lôùn nhaát naèm trong khoaûng chæ soá töø ñeán lôùp vaø
laø hai vò trí hôïp leä trong danh saùch Phaàn töû taïi
hoaùn ñoåi vôùi phaàn töû taïi
Hieän thöïc danh saùch lieân tuïc trong chöông
Ö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
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. 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à ,
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