Tìm kieám &Saép Tìm kieám &Saép xeáp xeáp
Tìm kieám & Saép xeáp Tìm kieám & Saép xeáp
Muïc tieâu: Muïc tieâu: Giôùi thieäu moät soá thuaät toaùn tìm kieám Giôùi thieäu moät soá thuaät toaùn tìm kieám vaø saép xeáp noäi. vaø saép xeáp noäi. Phaân tích, ñaùnh giaù ñoä phöùc taïp cuûa Phaân tích, ñaùnh giaù ñoä phöùc taïp cuûa caùc giaûi thuaät tìm kieám, saép xeáp. caùc giaûi thuaät tìm kieám, saép xeáp.
Noäi dung: Noäi dung: Nhu caàu tìm kieám vaø saép xeáp döõ lieäu Nhu caàu tìm kieám vaø saép xeáp döõ lieäu trong moät heä thoáng thoâng tin. trong moät heä thoáng thoâng tin. Caùc giaûi thuaät tìm kieám noäi. Caùc giaûi thuaät tìm kieám noäi. Caùc giaûi thuaät saép xeáp noäi. Caùc giaûi thuaät saép xeáp noäi.
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
2
Nhu caàu tìm kieám vaø saép Nhu caàu tìm kieám vaø saép xeáp xeáp döõ lieäu trong 1 heä thoáng döõ lieäu trong 1 heä thoáng thoâng tin thoâng tin Trong haàu heát caùc heä löu tröõ, quaûn lyù Trong haàu heát caùc heä löu tröõ, quaûn lyù döõ lieäu, thao taùc tìm kieám thöôøng ñöôïc döõ lieäu, thao taùc tìm kieám thöôøng ñöôïc thöïc hieän nhaát ñeå khai thaùc thoâng tin. thöïc hieän nhaát ñeå khai thaùc thoâng tin. Do caùc heä thoáng thoâng tin thöôøng phaûi löu Do caùc heä thoáng thoâng tin thöôøng phaûi löu tröõ moät khoái löôïng döõ lieäu ñaùng keå, neân tröõ moät khoái löôïng döõ lieäu ñaùng keå, neân vieäc xaây döïng caùc giaûi thuaät cho pheùp vieäc xaây döïng caùc giaûi thuaät cho pheùp tìm kieám nhanh seõ coù yù nghóa raát lôùn. tìm kieám nhanh seõ coù yù nghóa raát lôùn. Neáu döõ lieäu trong heä thoáng ñaõ ñöôïc toå Neáu döõ lieäu trong heä thoáng ñaõ ñöôïc toå chöùc theo moät traät töï naøo ñoù, thì vieäc tìm chöùc theo moät traät töï naøo ñoù, thì vieäc tìm kieám seõ tieán haønh nhanh choùng vaø hieäu kieám seõ tieán haønh nhanh choùng vaø hieäu quaû hôn quaû hôn
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
3
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
4
Nhu caàu tìm kieám vaø saép Nhu caàu tìm kieám vaø saép xeáp xeáp döõ lieäu trong 1 heä thoáng döõ lieäu trong 1 heä thoáng thoâng tin thoâng tin Coù nhieàu giaûi thuaät tìm kieám vaø saép Coù nhieàu giaûi thuaät tìm kieám vaø saép xeáp xeáp Möùc ñoä hieäu quaû cuûa töøng giaûi thuaät Möùc ñoä hieäu quaû cuûa töøng giaûi thuaät phuï thuoäc vaøo tính chaát cuûa caáu truùc phuï thuoäc vaøo tính chaát cuûa caáu truùc döõ lieäu cuï theå maø noù taùc ñoäng ñeán. döõ lieäu cuï theå maø noù taùc ñoäng ñeán. Döõ lieäu ñöôïc löu tröõ chuû yeáu trong boä Döõ lieäu ñöôïc löu tröõ chuû yeáu trong boä nhôù chính vaø treân boä nhôù phuï, do ñaëc nhôù chính vaø treân boä nhôù phuï, do ñaëc ñieåm khaùc nhau cuûa thieát bò löu tröõ, caùc ñieåm khaùc nhau cuûa thieát bò löu tröõ, caùc thuaät toaùn tìm kieám vaø saép xeáp ñöôïc thuaät toaùn tìm kieám vaø saép xeáp ñöôïc xaây döïng cho caùc caáu truùc löu tröõ treân xaây döïng cho caùc caáu truùc löu tröõ treân boä nhôù chính hoaëc phuï cuõng coù nhöõng boä nhôù chính hoaëc phuï cuõng coù nhöõng ñaëc thuø khaùc nhau. ñaëc thuø khaùc nhau. Chöông naøy seõ trình baøy caùc thuaät toaùn Chöông naøy seõ trình baøy caùc thuaät toaùn saép xeáp vaø tìm kieám döõ lieäu ñöôïc löu saép xeáp vaø tìm kieám döõ lieäu ñöôïc löu tröõ treân boä nhôù chính - goïi laø caùc giaûi tröõ treân boä nhôù chính - goïi laø caùc giaûi
thuaät tìm kieám vaø saép xeáp noäi tìm kieám vaø saép xeáp noäi.. thuaät
Caùc giaûi thuaät Caùc giaûi thuaät tìm kieám noäi tìm kieám noäi
Tìm kieám tuaàn töï Tìm kieám tuaàn töï Tìm kieám nhò phaân Tìm kieám nhò phaân
Caùc giaûi thuaät tìm kieám Caùc giaûi thuaät tìm kieám noäi noäi Baøi toaùn: Tìm vò trí xuaát hieän cuûa phaàn töû Baøi toaùn: Tìm vò trí xuaát hieän cuûa phaàn töû coù giaù trò x treân danh saùch ñaëc a coù giaù trò x treân danh saùch ñaëc a Taäp döõ lieäu ñöôïc löu tröõ laø daõy soá aa11, , Taäp döõ lieäu ñöôïc löu tröõ laø daõy soá , ... ,aNN aa22, ... ,a
int a[N]; Khoaù caàn tìm laø x Khoaù caàn tìm laø x
int
x;
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
6
Tìm kieám tuaàn Tìm kieám tuaàn töï töï
Tìm kieám tuaàn töï Tìm kieám tuaàn töï
Böôùc 1: i = Vò trí ñaàu; Böôùc 1: i = Vò trí ñaàu;
Böôùc 2: Neáu a[i] = x : Tìm thaáy. Döøng, vò Böôùc 2: Neáu a[i] = x : Tìm thaáy. Döøng, vò trí xuaát hieän: i trí xuaát hieän: i
Böôùc 3 : i = Vò trí keá(i);// xeùt tieáp phaàn Böôùc 3 : i = Vò trí keá(i);// xeùt tieáp phaàn töû keá trong maûng töû keá trong maûng
Böôùc 4: Neáu i >Vò trí cuoái: //Heát maûng Böôùc 4: Neáu i >Vò trí cuoái: //Heát maûng
Khoâng tìm thaáy. Döøng. Khoâng tìm thaáy. Döøng.
Ngöôïc laïi: Laëp laïi Böôùc 2. Ngöôïc laïi: Laëp laïi Böôùc 2.
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
8
Tìm kieám tuaàn töï Tìm kieám tuaàn töï
Ví duï: Cho daõy soá a Ví duï: Cho daõy soá a 55 1212 Giaù trò caàn tìm: 8 Giaù trò caàn tìm: 8
i = 1 i = 1
22 88 11 66 44 1515
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
9
Tìm kieám tuaàn töï Tìm kieám tuaàn töï
i = 2 i = 2
i = 3 i = 3
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
10
Tìm kieám tuaàn töï Tìm kieám tuaàn töï
int LinearSearch(int a[], int N, int x) {
for (int i=0; (i return i; // a[i] laø phaàn töû coù khoaù x // tìm heát maûng nhöng khoâng coù x return -1; } Tìm kieám tuaàn töï
Tìm kieám tuaàn töï Caûi tieán caøi ñaët: duøng phöông phaùp “lính
Caûi tieán caøi ñaët: duøng phöông phaùp “lính
canh”
canh”
Ñaët theâm moät phaàn töû coù giaù trò x vaøo cuoái
Ñaët theâm moät phaàn töû coù giaù trò x vaøo cuoái
maûng maûng
Baûo ñaûm luoân tìm thaáy x trong maûng
Baûo ñaûm luoân tìm thaáy x trong maûng
Sau ñoù döïa vaøo vò trí tìm thaáy ñeå keát luaän.
Sau ñoù döïa vaøo vò trí tìm thaáy ñeå keát luaän. Tìm kieám tuaàn töï
Tìm kieám tuaàn töï int LinearSearch(int a[], int N, int x)
{ // maûng goàm N phaàn töû töø a[0]..a[N-1] // theâm lính canh vaøo cuoái daõy a[N] = x;
for (int i=0; (a[i]!=x); i++);
if (i return i; // a[i] laø phaàn töû coù khoaù x // tìm heát maûng nhöng khoâng coù x return -1; } Tìm kieám tuaàn töï
Tìm kieám tuaàn töï Vaäy giaûi thuaät tìm tuaàn töï coù ñoä phöùc taïp tính
Vaäy giaûi thuaät tìm tuaàn töï coù ñoä phöùc taïp tính
toaùn caáp n: T(n) = O(n)
toaùn caáp n: T(n) = O(n) Ñaùnh giaù giaûi thuaät:
Ñaùnh giaù giaûi thuaät: Tìm kieám tuaàn töï
Tìm kieám tuaàn töï Tìm kieám nhò phaân
Tìm kieám nhò phaân Ñoái vôùi nhöõng daõy ñaõ coù thöù töï (giaû
Ñoái vôùi nhöõng daõy ñaõ coù thöù töï (giaû
söû thöù töï taêng ), caùc phaàn töû trong daõy
söû thöù töï taêng ), caùc phaàn töû trong daõy
coù quan heä
coù quan heä i -1 Neáu x > Neáu x < £ £ £ £ aai -1 a ai i a ai+1i+1 thì x chæ coù theå xuaát hieän
Neáu x > a aii thì x chæ coù theå xuaát hieän
] cuûa daõy
i+1 ,a,aNN] cuûa daõy
trong ñoaïn [aai+1
trong ñoaïn [
Neáu x < a aii thì x chæ coù theå xuaát hieän
thì x chæ coù theå xuaát hieän
] cuûa daõy .
trong ñoaïn [aa1 1 ,a,ai-1i-1] cuûa daõy .
trong ñoaïn [ Tìm kieám nhò phaân
Tìm kieám nhò phaân YÙ töôûng cuûa giaûi thuaät laø taïi moãi böôùc
YÙ töôûng cuûa giaûi thuaät laø taïi moãi böôùc
tieán haønh so saùnh x vôùi phaàn töû naèm
tieán haønh so saùnh x vôùi phaàn töû naèm
ôû vò trí giöõa cuûa daõy tìm kieám hieän
ôû vò trí giöõa cuûa daõy tìm kieám hieän
haønh, döïa vaøo keát quaû so saùnh naøy ñeå
haønh, döïa vaøo keát quaû so saùnh naøy ñeå
quyeát ñònh giôùi haïn daõy tìm kieám ôû
quyeát ñònh giôùi haïn daõy tìm kieám ôû
böôùc keá tieáp laø nöûa treân hay nöûa döôùi
böôùc keá tieáp laø nöûa treân hay nöûa döôùi
cuûa daõy tìm kieám hieän haønh
cuûa daõy tìm kieám hieän haønh Tìm kieám nhò phaân
Tìm kieám nhò phaân
Böôùc 1: left = VTÑ; right = VTC;
Böôùc 1: left = VTÑ; right = VTC;
Böôùc 2: Trong khi left £
Böôùc 2: Trong khi left right laëp: //ñoaïn tìm kieám
right laëp: //ñoaïn tìm kieám chöa roãng
chöa roãng
Böôùc 21: mid = (left+right)/2; // laáy moác so saùnh
Böôùc 21: mid = (left+right)/2; // laáy moác so saùnh
Böôùc 22: Neáu a[mid] = x:
Böôùc 22: Neáu a[mid] = x: //Tìm thaáy.
//Tìm thaáy. Döøng, vò trí xuaát hieän: mid
Döøng, vò trí xuaát hieän: mid //tìm x trong daõy con
//tìm x trong daõy con Böôùc 23: Neáu a[mid] > x:
Böôùc 23: Neáu a[mid] > x:
left .. a .. amid -1mid -1
aaleft right = mid - 1;
right = mid - 1; Ngöôïc laïi
Ngöôïc laïi //tìm x trong daõy con amid +1
//tìm x trong daõy con a right
mid +1 .. a .. aright left = mid + 1;
left = mid + 1; //Heát laëp
//Heát laëp £ Böôùc 3: Döøng, khoâng tìm thaáy.
Böôùc 3: Döøng, khoâng tìm thaáy. Tìm kieám nhò phaân
Tìm kieám nhò phaân Ví duï: Cho daõy soá a goàm 8 phaàn töû:
Ví duï: Cho daõy soá a goàm 8 phaàn töû:
15 15
66
11 2 2 4 4 5 5
Giaù trò caàn tìm laø 8
Giaù trò caàn tìm laø 8 1212 88 Tìm kieám nhò phaân
Tìm kieám nhò phaân left = 1, right = 8, mid = 4
left = 1, right = 8, mid = 4 Tìm kieám nhò phaân
Tìm kieám nhò phaân left = 5, right = 8, mid = 6
left = 5, right = 8, mid = 6 Tìm kieám nhò phaân
Tìm kieám nhò phaân Tìm kieám nhò phaân
Tìm kieám nhò phaân Giaûi thuaät tìm nhò phaân coù ñoä phöùc taïp tính toaùn caáp
Giaûi thuaät tìm nhò phaân coù ñoä phöùc taïp tính toaùn caáp
logn:
logn: Ñaùnh giaù giaûi thuaät:
Ñaùnh giaù giaûi thuaät: T(n) = O(log 2 2 n) n)
T(n) = O(log Tìm kieám nhò phaân
Tìm kieám nhò phaân Nhaän xeùt: (n) = O(n).
tuaàn töï (n) = O(n). Nhaän xeùt:
Giaûi thuaät tìm nhò phaân döïa vaøo quan heä giaù trò
Giaûi thuaät tìm nhò phaân döïa vaøo quan heä giaù trò
cuûa caùc phaàn töû maûng ñeå ñònh höôùng trong quaù
cuûa caùc phaàn töû maûng ñeå ñònh höôùng trong quaù
trình tìm kieám, do vaäy chæ aùp duïng ñöôïc cho
trình tìm kieám, do vaäy chæ aùp duïng ñöôïc cho
nhöõng daõy ñaõ coù thöù töï.
nhöõng daõy ñaõ coù thöù töï.
Giaûi thuaät tìm nhò phaân tieát kieäm thôøi gian hôn
Giaûi thuaät tìm nhò phaân tieát kieäm thôøi gian hôn
raát nhieàu so vôùi giaûi thuaät tìm tuaàn töï do
raát nhieàu so vôùi giaûi thuaät tìm tuaàn töï do
TTnhò phaân
nhò phaân (n) = O(log (n) = O(log 22 n) < T n) < Ttuaàn töï Tìm kieám nhò phaân
Tìm kieám nhò phaân Ñònh nghóa baøi toaùn
Ñònh nghóa baøi toaùn
saép xeáp
saép xeáp
Saép xeáp laø quaù trình xöû lyù moät danh
Saép xeáp laø quaù trình xöû lyù moät danh
saùch caùc phaàn töû (hoaëc caùc maãu tin)
saùch caùc phaàn töû (hoaëc caùc maãu tin)
ñeå ñaët chuùng theo moät thöù töï thoûa
ñeå ñaët chuùng theo moät thöù töï thoûa
maõn moät tieâu chuaån naøo ñoù döïa treân
maõn moät tieâu chuaån naøo ñoù döïa treân
noäi dung thoâng tin löu giöõ taïi moãi phaàn
noäi dung thoâng tin löu giöõ taïi moãi phaàn
töû.
töû. Khaùi nieäm nghòch theá
Khaùi nieäm nghòch theá Khaùi nieäm nghòch theá:
Khaùi nieäm nghòch theá:
Xeùt moät maûng caùc soá a , … ann..
, thì ta goïi ñoù laø
> ajj, thì ta goïi ñoù laø Maûng chöa saép xeáp seõ coù nghòch theá.
Maûng chöa saép xeáp seõ coù nghòch theá.
Maûng ñaõ coù thöù töï seõ khoâng chöùa
Maûng ñaõ coù thöù töï seõ khoâng chöùa
nghòch theá.
nghòch theá. Xeùt moät maûng caùc soá a00, a, a11, … a
Neáu coù i £ £ £ … £
… aa00 £ a a11 £ a ann Phöùc taïp hôn
Phöùc taïp hôn
Hieäu quaû cao
Hieäu quaû cao Caùc phöông phaùp saép
Caùc phöông phaùp saép
xeáp thoâng duïng
xeáp thoâng duïng
Selection sort
Selection sort
Insertion sort
Insertion sort
Interchange sort
Interchange sort
Bubble sort
Bubble sort
Shaker sort
Shaker sort
Binary Insertion sort
Binary Insertion sort Shell sort
Shell sort
Heap sort
Heap sort
Quick sort
Quick sort
Merge sort
Merge sort
Radix sort
Radix sort
…… Lôùp thuaät toaùn
Lôùp thuaät toaùn
khaùc
khaùc Ñôn giaûn,
Ñôn giaûn,
Chi phí cao
Chi phí cao Selection sort – YÙ töôûng
Selection sort – YÙ töôûng Nhaän xeùt: Maûng coù thöù töï thì a , …,
=min(aii, a, ai+1i+1, …, Nhaän xeùt: Maûng coù thöù töï thì aii=min(a
aan-1n-1))
YÙ töôûng: moâ phoûng moät trong nhöõng
YÙ töôûng: moâ phoûng moät trong nhöõng
caùch saép xeáp töï nhieân nhaát trong thöïc
caùch saép xeáp töï nhieân nhaát trong thöïc
teá:
teá:
Choïn phaàn töû nhoû nhaát trong N phaàn
Choïn phaàn töû nhoû nhaát trong N phaàn
töû ban ñaàu, ñöa phaàn töû naøy veà vò trí
töû ban ñaàu, ñöa phaàn töû naøy veà vò trí
ñuùng laø ñaàu daõy hieän haønh
ñuùng laø ñaàu daõy hieän haønh
Xem daõy hieän haønh chæ coøn N-1 phaàn
Xem daõy hieän haønh chæ coøn N-1 phaàn
töû cuûa daõy ban ñaàu, baét ñaàu töø vò trí
töû cuûa daõy ban ñaàu, baét ñaàu töø vò trí
thöù 2; laëp laïi quaù trình treân cho daõy
thöù 2; laëp laïi quaù trình treân cho daõy
hieän haønh... ñeán khi daõy hieän haønh
hieän haønh... ñeán khi daõy hieän haønh
chæ coøn 1 phaàn töû.
chæ coøn 1 phaàn töû. Selection sort – Thuaät toaùn
Selection sort – Thuaät toaùn töø a[i] ñeán a[N]
töø a[i] ñeán a[N] i: Hoaùn vò a[min] vaø a[i]
i: Hoaùn vò a[min] vaø a[i] „ //input: daõy (a, N)
//input: daõy (a, N)
//output: daõy (a, N) ñaõ ñöôïc saép xeáp
//output: daõy (a, N) ñaõ ñöôïc saép xeáp
Böôùc 1 : i = Vò trí ñaàu;
Böôùc 1 : i = Vò trí ñaàu;
Böôùc 2 : Tìm phaàn töû a[min] nhoû nhaát trong daõy hieän
Böôùc 2 : Tìm phaàn töû a[min] nhoû nhaát trong daõy hieän
haønh
haønh
Böôùc 3 : Neáu min „
Böôùc 3 : Neáu min
Böôùc 4 : Neáu i chöa laø Vò trí cuoái
Böôùc 4 : Neáu i chöa laø Vò trí cuoái
i = Vò trí keá(i);
i = Vò trí keá(i);
Laëp laïi Böôùc 2
Laëp laïi Böôùc 2
//N phaàn töû ñaõ naèm
Ngöôïc laïi: Döøng. //N phaàn töû ñaõ naèm Ngöôïc laïi: Döøng.
ñuùng vò trí.
ñuùng vò trí. Selection sort – Ví duï
Selection sort – Ví duï Find MinPos(1, 8) Swap(ai, amin) 2 3 4 5 6 7 8 min
1 2 8 5 1 6 4 15 12 i Selection sort – Ví duï
Selection sort – Ví duï Find MinPos(2, 8) Swap(ai, amin) 3 4 5 6 7 8 min
2 1 8 5 12 6 4 15 2 1 i Selection sort – Ví duï
Selection sort – Ví duï Find MinPos(3, 8) Swap(ai, amin) min
3 4 5 6 7 8 1 2 8 5 12 6 4 15 1 2 i Selection sort – Ví duï
Selection sort – Ví duï Find MinPos(4, 8) Swap(ai, amin) 1 2 min
4 5 6 7 8 3 1 2 5 12 6 8 15 4 i Selection sort – Ví duï
Selection sort – Ví duï Find MinPos(5, 8) Swap(ai, amin) 1 2 3 min
5 6 7 8 4 1 2 4 12 6 8 15 5 i Selection sort – Ví duï
Selection sort – Ví duï Find MinPos(6, 8) Swap(ai, amin) 1 2 3 4 min
6 7 8 5 1 2 4 5 12 8 15 6 i Selection sort – Ví duï
Selection sort – Ví duï Find MinPos(7, 8) Swap(ai, amin) 1 2 3 4 5 min
7 8 6 1 2 4 5 6 8 12
12 15
15 i Selection sort
Selection sort Selection sort – Ñaùnh giaù giaûi thuaät
Selection sort – Ñaùnh giaù giaûi thuaät ÔÛû löôït thöù i, caàn (N-i) laàn so saùnh ñeå xaùc ñònh
ÔÛû löôït thöù i, caàn (N-i) laàn so saùnh ñeå xaùc ñònh
phaàn töû nhoû nhaát hieän haønh.
phaàn töû nhoû nhaát hieän haønh.
Soá löôïng pheùp so saùnh khoâng phuï thuoäc vaøo tình
Soá löôïng pheùp so saùnh khoâng phuï thuoäc vaøo tình
traïng cuûa daõy soá ban ñaàu.
traïng cuûa daõy soá ban ñaàu.
Trong moïi tröôøng hôïp, soá laàn so saùnh laø:
Trong moïi tröôøng hôïp, soá laàn so saùnh laø: 1n 1) = - - (n i) n(n
2 =
1i - (cid:229) Selection sort – Ñaùnh giaù giaûi thuaät
Selection sort – Ñaùnh giaù giaûi thuaät Soá laàn hoaùn vò (moät hoaùn vò baèng 3 pheùp gaùn) phuï
Soá laàn hoaùn vò (moät hoaùn vò baèng 3 pheùp gaùn) phuï
thuoäc vaøo tình traïng ban ñaàu cuûa daõy soá
thuoäc vaøo tình traïng ban ñaàu cuûa daõy soá Insertion Sort – YÙ töôûng
Insertion Sort – YÙ töôûng
Nhaän xeùt: moïi daõy luoân coù i-1 phaàn töû ñaàu
phaàn töû ñaàu ,..., ann luoân coù i-1 ,... ,ai-1i-1 ñaõ coù thöù töï (2 ≤ i).
ñaõ coù thöù töï (2 ≤ i). YÙ töôûng chính: tìm caùch cheøn phaàn töû £ £ Nhaän xeùt: moïi daõy aa1 1 , a, a2 2 ,..., a
tieân aa1 1 , a, a2 2 ,... ,a
tieân
YÙ töôûng chính: tìm caùch cheøn phaàn töû aai i vaøo vò trí thích
vaøo vò trí thích
,... ,aii
hôïp cuûa ñoaïn ñaõ ñöôïc saép ñeå coù daõy môùi aa1 1 , a, a2 2 ,... ,a
hôïp cuûa ñoaïn ñaõ ñöôïc saép ñeå coù daõy môùi
trôû neân coù thöù töï.
trôû neân coù thöù töï.
Vò trí naøy chính laø pos thoûa £ pospos£ i).i). a aii < < aapospos (1(1£ Chi tieát hôn:
Chi tieát hôn: Theâm , xem nhö ñaõ coù ñoaïn goàm
,..., ann, xem nhö ñaõ coù ñoaïn goàm Theâm ñöôïc saép
seõ coù ñoaïn aa1 1 aa22 ñöôïc saép ñöôïc saép
ñeå coù ñoaïn aa11 a a22 a a33 ñöôïc saép
vaøo ñoaïn aa11 a a2 ...2 ...aaN-1N-1 Daõy ban ñaàu aa1 1 , a, a2 2 ,..., a
Daõy ban ñaàu
ñaõ ñöôïc saép.
moät phaàn töû aa1 1 ñaõ ñöôïc saép.
moät phaàn töû
vaøo ñoaïn aa1 1 seõ coù ñoaïn
Theâm aa2 2 vaøo ñoaïn
vaøo ñoaïn aa1 1 aa2 2 ñeå coù ñoaïn
Theâm aa3 3 vaøo ñoaïn
Tieáp tuïc cho ñeán khi theâm xong aaN N vaøo ñoaïn
Tieáp tuïc cho ñeán khi theâm xong
ñöôïc saép. .
seõ coù daõy aa1 1 aa2....2.... a aN N ñöôïc saép
seõ coù daõy
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp Insertion Sort – Thuaät toaùn
Insertion Sort – Thuaät toaùn ñaõ ñöôïc
// giaû söû coù ñoaïn a[1]a[1] ñaõ ñöôïc
// giaû söû coù ñoaïn //input: daõy (a, N)
//input: daõy (a, N)
//output: daõy (a, N) ñaõ ñöôïc saép xeáp
//output: daõy (a, N) ñaõ ñöôïc saép xeáp
Böôùc 1
: i = 2;
Böôùc 1: i = 2;
saépsaép
Böôùc 2
: x = a[i]; Tìm vò trí pos thích hôïp trong ñoaïn a[1]
Böôùc 2: x = a[i]; Tìm vò trí pos thích hôïp trong ñoaïn a[1]
ñeán a[i] ñeå cheøn x vaøo
ñeán a[i] ñeå cheøn x vaøo
Böôùc 3
: Dôøi choã caùc phaàn töû töø a[pos] ñeán a[i-1]
Böôùc 3: Dôøi choã caùc phaàn töû töø a[pos] ñeán a[i-1]
sangsang ñaõ ñöôïc saép
a[1]..a[i] ñaõ ñöôïc saép // coù ñoaïn a[1]..a[i] £ n : Laëp laïi Böôùc 2.
n : Laëp laïi Böôùc 2. phaûi 1 vò trí ñeå daønh choå cho x
phaûi 1 vò trí ñeå daønh choå cho x
Böôùc 4
Böôùc 4: a[pos] = x;
: a[pos] = x; // coù ñoaïn
Böôùc 5
Böôùc 5: i = i+1;
: i = i+1;
Neáu i £
Neáu i
Ngöôïc laïi : Döøng.
Ngöôïc laïi : Döøng. Insertion Sort – Ví duï
Insertion Sort – Ví duï 1 2 3 4 5 6 7 8 12 2 8 5 1 6 4 15 Insertion Sort – Ví duï
Insertion Sort – Ví duï Insert a2 into (1, 2) 1 3 4 5 6 7 8 pos
2 8 5 1 6 4 15 2 12
2 x i Insertion Sort – Ví duï
Insertion Sort – Ví duï Insert a3 into (1, 3) 1 2 pos
3 4 5 6 7 8 2 8 5 1 6 4 15 12
8 x i Insertion Sort – Ví duï
Insertion Sort – Ví duï Insert a4 into (1, 4) 1 2 5 6 7 8 pos
4 3 2 1 6 4 15 5 8
5 12 x i Insertion Sort – Ví duï
Insertion Sort – Ví duï Insert a5 into (1, 5) 1 2 3 pos
5 6 7 8 4 5 8 1 6 4 15 12 2
1 x i Insertion Sort – Ví duï
Insertion Sort – Ví duï Insert a6 into (1, 6) 1 2 3 4 pos
6 7 8 5 1 2 5 6 4 15 12 8
6 x i Insertion Sort – Ví duï
Insertion Sort – Ví duï Insert a7 into (1, 7) 1 2 3 4 5 pos
7 8 6 1 2 6 8 4 15 12 5
4 x i Insertion Sort – Ví duï
Insertion Sort – Ví duï Insert a8 into (1, 8) 1 2 3 4 5 6 pos
8 7 1 2 4 5 6 8 12 15
15 x i Insertion Sort – Ví duï
Insertion Sort – Ví duï 1 2 3 4 pos
5 6 7 8 1 2 4 5 6 8 12 15 int pos, i;
int x;//löu tröõ a[i] traùnh bò ghi ñeø khi dôøi choã caùc phaàn
töû.
for(int i=1 ; i x = a[i];
for(pos=i;(pos>0)&&(a[pos-1]>x);pos--) a[pos] = a[pos-1]; a[pos] = x;// cheøn x vaøo daõy } } Insertion Sort – Nhaän xeùt
Insertion Sort – Nhaän xeùt Khi tìm vò trí thích hôïp ñeå cheøn a[i] vaøo ñoaïn a[0]
Khi tìm vò trí thích hôïp ñeå cheøn a[i] vaøo ñoaïn a[0]
ñeán a[i-1], do ñoaïn ñaõ ñöôïc saép coù theå söû duïng
coù theå söû duïng
ñeán a[i-1], do ñoaïn ñaõ ñöôïc saép
giaûi thuaät tìm nhò phaân ñeå thöïc hieän vieäc tìm vò trí
giaûi thuaät tìm nhò phaân ñeå thöïc hieän vieäc tìm vò trí
pos pos giaûi thuaät saép xeáp cheøn nhò phaân
Binary
giaûi thuaät saép xeáp cheøn nhò phaân Binary
Insertion Sort
Insertion Sort
Löu yù: Ngoaøi ra, coù theå caûi tieán giaûi thuaät cheøn tröïc tieáp
Ngoaøi ra, coù theå caûi tieán giaûi thuaät cheøn tröïc tieáp
vôùi phaàn töû caàm canh ñeå giaûm ñieàu kieän kieåm tra
vôùi phaàn töû caàm canh ñeå giaûm ñieàu kieän kieåm tra
khi xaùc ñònh vò trí pos.
khi xaùc ñònh vò trí pos. Löu yù: Cheøn nhò phaân chæ laøm giaûm soá laàn so
Cheøn nhò phaân chæ laøm giaûm soá laàn so
saùnh, khoâng laøm giaûm soá laàn dôøi choã.
saùnh, khoâng laøm giaûm soá laàn dôøi choã. Binary Insertion Sort – Caøi ñaët
Binary Insertion Sort – Caøi ñaët // tìm vò trí cheøn x
// tìm vò trí thích hôïp m // dôøi choã caùc phaàn töû seõ ñöùng sau x // cheøn x vaøo daõy Insertion Sort – Ñaùnh giaù giaûi thuaät
Insertion Sort – Ñaùnh giaù giaûi thuaät Caùc pheùp so saùnh xaûy ra trong moãi voøng laëp tìm vò trí
Caùc pheùp so saùnh xaûy ra trong moãi voøng laëp tìm vò trí
thích hôïp pos. Moãi laàn xaùc ñònh vò trí pos ñang xeùt
thích hôïp pos. Moãi laàn xaùc ñònh vò trí pos ñang xeùt
khoâng thích hôïp dôøi choã phaàn töû a[pos-1] ñeán vò trí
dôøi choã phaàn töû a[pos-1] ñeán vò trí
khoâng thích hôïp
pos. pos.
Giaûi thuaät thöïc hieän taát caû N-1 voøng laëp tìm pos, do
Giaûi thuaät thöïc hieän taát caû N-1 voøng laëp tìm pos, do
soá löôïng pheùp so saùnh vaø dôøi choã naøy phuï thuoäc
soá löôïng pheùp so saùnh vaø dôøi choã naøy phuï thuoäc
vaøo tình traïng cuûa daõy soá ban ñaàu, neân chæ coù theå
vaøo tình traïng cuûa daõy soá ban ñaàu, neân chæ coù theå
öôùc löôïc trong töøng tröôøng hôïp nhö sau:
öôùc löôïc trong töøng tröôøng hôïp nhö sau: – YÙ töôûng
Interchange Sort – YÙ töôûng
Interchange Sort Nhaän xeùt: Ñeå saép xeáp moät daõy soá, ta coù theå xeùt
Nhaän xeùt: Ñeå saép xeáp moät daõy soá, ta coù theå xeùt
caùc nghòch theá coù trong daõy vaø laøm trieät tieâu daàn
caùc nghòch theá coù trong daõy vaø laøm trieät tieâu daàn
chuùng ñi.
chuùng ñi.
YÙ töôûng chính:
YÙ töôûng chính:
Xuaát phaùt töø ñaàu daõy, tìm taát caû nghòch theá
Xuaát phaùt töø ñaàu daõy, tìm taát caû nghòch theá
chöùa phaàn töû naøy, trieät tieâu chuùng baèng caùch
chöùa phaàn töû naøy, trieät tieâu chuùng baèng caùch
ñoåi choã phaàn töû naøy vôùi phaàn töû töông öùng
ñoåi choã phaàn töû naøy vôùi phaàn töû töông öùng
trong caëp nghòch theá.
trong caëp nghòch theá.
Laëp laïi xöû lyù treân vôùi caùc phaàn töû tieáp theo
Laëp laïi xöû lyù treân vôùi caùc phaàn töû tieáp theo
trong daõy
trong daõy // baét ñaàu töø ñaàu daõy
// baét ñaàu töø ñaàu daõy – Thuaät toaùn
Interchange Sort – Thuaät toaùn
Interchange Sort
//input: daõy (a, N)
//input: daõy (a, N)
//output: daõy (a, N) ñaõ ñöôïc saép xeáp
//output: daõy (a, N) ñaõ ñöôïc saép xeáp
Böôùc 1 : i = 1;
Böôùc 1 : i = 1;
//tìm caùc caëp phaàn töû a[j] < a[i], j>i
Böôùc 2 : j = i+1;
Böôùc 2 : j = i+1; //tìm caùc caëp phaàn töû a[j] < a[i], j>i
Böôùc 3 : Trong khi j £
Böôùc 3 : Trong khi j £ N thöïc hieän
N thöïc hieän
« a[j];a[j]; Neáu a[j] Interchange Sort – Ví duï
Interchange Sort – Ví duï j
2 1 3 4 5 6 7 8 2 8 5 1 6 4 15 12
1 i Interchange Sort – Ví duï
Interchange Sort – Ví duï 2 j
3 4 5 6 7 8 1 8 5 2 6 4 15 1 12
2 i Interchange Sort – Ví duï
Interchange Sort – Ví duï 3 j
4 5 6 7 8 1 2 8 5 6 4 15 1 2 12
4 i Interchange Sort – Ví duï
Interchange Sort – Ví duï 1 2 4 j
5 6 7 8 3 1 2 8 6 5 15 4 12
5 i Interchange Sort – Ví duï
Interchange Sort – Ví duï 1 2 3 4 5 6 7 8 1 2 4 5 6 8 12 15 - Caøi ñaët
Interchange Sort - Caøi ñaët
Interchange Sort Interchange Sort
Interchange Sort
Ñaùnh giaù giaûi thuaät
Ñaùnh giaù giaûi thuaät
Soá löôïng caùc pheùp so saùnh xaûy ra khoâng phuï thuoäc
Soá löôïng caùc pheùp so saùnh xaûy ra khoâng phuï thuoäc
vaøo tình traïng cuûa daõy soá ban ñaàu
vaøo tình traïng cuûa daõy soá ban ñaàu
Soá löôïng pheùp hoaùn vò thöïc hieän tuøy thuoäc vaøo
Soá löôïng pheùp hoaùn vò thöïc hieän tuøy thuoäc vaøo
keát quaû so saùnh
keát quaû so saùnh Bubble sort – YÙ töôûng
Bubble sort – YÙ töôûng YÙ töôûng chính:
YÙ töôûng chính:
Xuaát phaùt töø cuoái (ñaàu) daõy, ñoåi choã caùc caëp
Xuaát phaùt töø cuoái (ñaàu) daõy, ñoåi choã caùc caëp
phaàn töû keá caän ñeå ñöa phaàn töû nhoû (lôùn) hôn
phaàn töû keá caän ñeå ñöa phaàn töû nhoû (lôùn) hôn
trong caëp phaàn töû ñoù veà vò trí ñuùng ñaàu (cuoái)
trong caëp phaàn töû ñoù veà vò trí ñuùng ñaàu (cuoái)
daõy hieän haønh, sau ñoù seõ khoâng xeùt ñeán noù ôû
daõy hieän haønh, sau ñoù seõ khoâng xeùt ñeán noù ôû
böôùc tieáp theo,
böôùc tieáp theo,
ÔÛ laàn xöû lyù thöù i coù vò trí ñaàu daõy laø i
ÔÛ laàn xöû lyù thöù i coù vò trí ñaàu daõy laø i
Laëp laïi xöû lyù treân cho ñeán khi khoâng coøn caëp
Laëp laïi xöû lyù treân cho ñeán khi khoâng coøn caëp
phaàn töû naøo ñeå xeùt.
phaàn töû naøo ñeå xeùt. Bubble sort – Thuaät toaùn
Bubble sort – Thuaät toaùn //xeùt caëp phaàn töû keá
a[j-1];//xeùt caëp phaàn töû keá « a[j-1]; //input: daõy (a, N)
//input: daõy (a, N)
//output: daõy (a, N) ñaõ ñöôïc saép xeáp
//output: daõy (a, N) ñaõ ñöôïc saép xeáp
Böôùc 1 : i = Vò trí ñaàu;
Böôùc 1 : i = Vò trí ñaàu;
//Duyeät töø cuoái daõy ngöôïc veà
Böôùc 2 : j = Vò trí cuoái;
Böôùc 2 : j = Vò trí cuoái;//Duyeät töø cuoái daõy ngöôïc veà
vò trí i
vò trí i
Trong khi (j > i) thöïc hieän:
Trong khi (j > i) thöïc hieän:
Neáu a[j] // laàn xöû lyù keá tieáp
Böôùc 3 : i = Vò trí keá(i); // laàn xöû lyù keá tieáp
Neáu i = Vò trí cuoái: Döøng.
// Heát daõy.
Neáu i = Vò trí cuoái: Döøng. // Heát daõy.
Ngöôïc laïi : Laëp laïi Böôùc 2.
Ngöôïc laïi : Laëp laïi Böôùc 2. Bubble Sort – Ví duï
Bubble Sort – Ví duï 2 3 4 5 6 7 j
8 1 2 8 5 1 6 4 15 1
12 i Bubble Sort – Ví duï
Bubble Sort – Ví duï 2 3 4 5 6 7 j
8 1 2 8 5 4 6 15 1 12
2 i Bubble Sort – Ví duï
Bubble Sort – Ví duï 1 3 4 5 6 7 j
8 2 1 4 8 5 6 15 2 12
4 i Bubble Sort – Ví duï
Bubble Sort – Ví duï 1 2 4 5 6 7 j
8 3 1 2 5
12 8 5 6 15 4 i Bubble Sort – Ví duï
Bubble Sort – Ví duï 1 2 3 5 6 7 j
8 4 1 2 4 8 6 15 5 12
6 i Bubble Sort – Ví duï
Bubble Sort – Ví duï 1 2 3 4 6 7 j
8 5 1 2 4 5 8
12 8 15 6 i Bubble Sort – Ví duï
Bubble Sort – Ví duï 1 2 3 4 5 7 j
8 6 1 2 4 5 6 8 12
12 15
15 i Bubble sort - Caøi ñaët
Bubble sort - Caøi ñaët void BubbleSort(int a[], int N)
{ int i, j;
for (i = 0 ; i for (j =N-1; j>i ; j --)
if(a[j]< a[j-1]) Swap(a[j], a[j-1]); } Bubble sort - Ñaùnh giaù giaûi
Bubble sort - Ñaùnh giaù giaûi
thuaät
thuaät Soá löôïng caùc pheùp so saùnh xaûy ra khoâng phuï thuoäc
Soá löôïng caùc pheùp so saùnh xaûy ra khoâng phuï thuoäc
vaøo tình traïng cuûa daõy soá ban ñaàu
vaøo tình traïng cuûa daõy soá ban ñaàu
Soá löôïng pheùp hoaùn vò thöïc hieän tuøy thuoäc vaøo
Soá löôïng pheùp hoaùn vò thöïc hieän tuøy thuoäc vaøo
keát quaû so saùnh
keát quaû so saùnh Bubble sort - Ñaùnh giaù giaûi
Bubble sort - Ñaùnh giaù giaûi
thuaät
thuaät Khuyeát ñieåm:
Khuyeát ñieåm:
Khoâng nhaän dieän ñöôïc tình traïng daõy ñaõ coù thöù
Khoâng nhaän dieän ñöôïc tình traïng daõy ñaõ coù thöù
töï hay coù thöù töï töøng phaàn.
töï hay coù thöù töï töøng phaàn.
Caùc phaàn töû nhoû ñöôïc ñöa veà vò trí ñuùng raát
Caùc phaàn töû nhoû ñöôïc ñöa veà vò trí ñuùng raát
nhanh, trong khi caùc phaàn töû lôùn laïi ñöôïc ñöa veà vò
nhanh, trong khi caùc phaàn töû lôùn laïi ñöôïc ñöa veà vò
trí ñuùng raát chaäm.
trí ñuùng raát chaäm. Bubble sort – Caûi tieán
Bubble sort – Caûi tieán Giaûi thuaät ShakerSort:
Giaûi thuaät ShakerSort:
Döïa treân nguyeân taéc ñoåi choã tröïc tieáp
Döïa treân nguyeân taéc ñoåi choã tröïc tieáp
Tìm caùch khaéc phuïc caùc nhöôïc ñieåm cuûa
Tìm caùch khaéc phuïc caùc nhöôïc ñieåm cuûa
BubleSort
BubleSort Trong moãi laàn saép xeáp, duyeät maûng theo 2
Trong moãi laàn saép xeáp, duyeät maûng theo 2
löôït töø 2 phía khaùc nhau :
löôït töø 2 phía khaùc nhau : Löôït ñi: ñaåy phaàn töû nhoû veà ñaàu
Löôït ñi: ñaåy phaàn töû nhoû veà ñaàu
maûngmaûng
Löôït veà: ñaåy phaàn töû lôùn veà
Löôït veà: ñaåy phaàn töû lôùn veà
cuoái maûng
cuoái maûng Ghi nhaän laïi nhöõng ñoaïn ñaõ saép
Ghi nhaän laïi nhöõng ñoaïn ñaõ saép
xeáp nhaèm tieát kieäm caùc pheùp so
xeáp nhaèm tieát kieäm caùc pheùp so
saùnh thöøa.
saùnh thöøa. Giaûi thuaät ShakerSort
Giaûi thuaät ShakerSort
//input: daõy (a, N)
//input: daõy (a, N)
//output: daõy (a, N) ñaõ ñöôïc saép xeáp
//output: daõy (a, N) ñaõ ñöôïc saép xeáp
Böôùc 1 :
Böôùc 1 :
l = 1; r = n;
//töø l ñeán r laø ñoaïn caàn ñöôïc saép xeáp
l = 1; r = n; //töø l ñeán r laø ñoaïn caàn ñöôïc saép xeáp
k = n;
// ghi nhaän laïi vò trí k xaûy ra hoaùn vò sau
k = n;
// ghi nhaän laïi vò trí k xaûy ra hoaùn vò sau
cuøng
cuøng
// ñeå laøm cô sôû thu heïp ñoaïn l ñeán r
// ñeå laøm cô sôû thu heïp ñoaïn l ñeán r
Böôùc 2 :
Böôùc 2 :
Böôùc 2a : j = r ;
Böôùc 2a : j = r ;
maûng
maûng // ñaåy phaàn töû nhoû veà ñaàu
// ñaåy phaàn töû nhoû veà ñaàu Trong khi (j > l) :
Trong khi (j > l) : Neáu a[j] « Neáu a[j] //löu laïi nôi xaûy ra hoaùn vò
k = j; //löu laïi nôi xaûy ra hoaùn vò k = j; j = j-1;
j = j-1; ñaàu daõy ñaàu daõy Giaûi thuaät ShakerSort
Giaûi thuaät ShakerSort Böôùc 2 :
Böôùc 2 :
Böôùc 2b : j = l ;
Böôùc 2b : j = l ;
maûng
maûng // ñaåy phaàn töû lôùn veà cuoái
// ñaåy phaàn töû lôùn veà cuoái Trong khi (j < r) :
Trong khi (j < r) : « Neáu a[j]>a[j+1]:
Neáu a[j]>a[j+1]: a[j] a[j] « a[j+1];
a[j+1];
//löu laïi nôi xaûy ra hoaùn vò
k = j;//löu laïi nôi xaûy ra hoaùn vò k = j; r = k; j = j+1;
j = j+1; Böôùc 3 : Neáu l < r: Laëp laïi Böôùc 2.
Böôùc 3 : Neáu l < r: Laëp laïi Böôùc 2. //loaïi bôùt caùc phaàn töû ñaõ coù thöù töï ôû
r = k; //loaïi bôùt caùc phaàn töû ñaõ coù thöù töï ôû
cuoái daõy
cuoái daõy Heap sort
Saép xeáp caây - Heap sort
Saép xeáp caây - Khi tìm phaàn töû nhoû nhaát ôû böôùc i, phöông phaùp
Khi tìm phaàn töû nhoû nhaát ôû böôùc i, phöông phaùp
saép xeáp choïn tröïc tieáp khoâng taän duïng ñöôïc caùc
saép xeáp choïn tröïc tieáp khoâng taän duïng ñöôïc caùc
thoâng tin ñaõ coù ñöôïc do caùc pheùp so saùnh ôû böôùc
thoâng tin ñaõ coù ñöôïc do caùc pheùp so saùnh ôû böôùc
i-1.
i-1.
Giaûi thuaät Heap Sort khaéc phuïc nhöôïc ñieåm naøy
Giaûi thuaät Heap Sort khaéc phuïc nhöôïc ñieåm naøy
baèng caùch choïn ra ñöôïc moät caáu truùc döõ lieäu cho
baèng caùch choïn ra ñöôïc moät caáu truùc döõ lieäu cho
pheùp tích luõy caùc thoâng tin veà söï so saùnh giaù trò
pheùp tích luõy caùc thoâng tin veà söï so saùnh giaù trò
caùc phaàn töû trong quaù trình saép xeáp.
caùc phaàn töû trong quaù trình saép xeáp. Heap sort
Saép xeáp caây - Heap sort
Saép xeáp caây - Xeùt daõy soá : 5 2 6 4 8 1
Xeùt daõy soá : 5 2 6 4 8 1
Giaû söû caùc phaàn töû cuûa daõy ñöôïc boá trí theo quan
Giaû söû caùc phaàn töû cuûa daõy ñöôïc boá trí theo quan
heä so saùnh vaø taïo thaønh sô ñoà daïng caây:
heä so saùnh vaø taïo thaønh sô ñoà daïng caây: Heap sort
Saép xeáp caây - Heap sort
Saép xeáp caây - Phaàn töû ôû möùc i chính laø phaàn töû lôùn trong caëp
Phaàn töû ôû möùc i chính laø phaàn töû lôùn trong caëp
phaàn töû töông öùng ôû möùc i+1
phaàn töû töông öùng ôû möùc i+1
phaàn töû ôû möùc 0 (nuùt goác cuûa caây) luoân laø phaàn
phaàn töû ôû möùc 0 (nuùt goác cuûa caây) luoân laø phaàn
töû lôùn nhaát cuûa daõy.
töû lôùn nhaát cuûa daõy.
Neáu loaïi boû phaàn töû goác ra khoûi caây (nghóa laø ñöa
Neáu loaïi boû phaàn töû goác ra khoûi caây (nghóa laø ñöa
phaàn töû lôùn nhaát veà ñuùng vò trí), thì vieäc caäp nhaät
phaàn töû lôùn nhaát veà ñuùng vò trí), thì vieäc caäp nhaät
caây chæ xaûy ra treân nhöõng nhaùnh lieân quan ñeán
caây chæ xaûy ra treân nhöõng nhaùnh lieân quan ñeán
phaàn töû môùi loaïi boû, coøn caùc nhaùnh khaùc ñöôïc
phaàn töû môùi loaïi boû, coøn caùc nhaùnh khaùc ñöôïc
baûo toaøn, nghóa laø böôùc keá tieáp coù theå söû duïng
baûo toaøn, nghóa laø böôùc keá tieáp coù theå söû duïng
laïi caùc keát quaû so saùnh ôû böôùc hieän taïi.
laïi caùc keát quaû so saùnh ôû böôùc hieän taïi. (cid:222) (cid:222) Heap sort
Saép xeáp caây - Heap sort
Saép xeáp caây - Loaïi boû 8 ra khoûi caây vaø theá vaøo caùc choã troáng
Loaïi boû 8 ra khoûi caây vaø theá vaøo caùc choã troáng
giaù trò -¥
ñeå tieän vieäc caäp nhaät laïi caây :
ñeå tieän vieäc caäp nhaät laïi caây :
giaù trò - ¥ Heap sort
Saép xeáp caây - Heap sort
Saép xeáp caây - Toaøn boä nhaùnh traùi cuûa caây cuõ ñöôïc baûo toaøn
Toaøn boä nhaùnh traùi cuûa caây cuõ ñöôïc baûo toaøn
Böôùc keá tieáp ñeå choïn ñöôïc phaàn töû lôùn nhaát hieän
Böôùc keá tieáp ñeå choïn ñöôïc phaàn töû lôùn nhaát hieän
haønh laø 6, chæ caàn laøm theâm moät pheùp so saùnh 1
haønh laø 6, chæ caàn laøm theâm moät pheùp so saùnh 1
vôùi 6.
vôùi 6. (cid:222) (cid:222) Heap sort
Saép xeáp caây - Heap sort
Saép xeáp caây - Tieán haønh nhieàu laàn vieäc loaïi boû phaàn töû goác
Tieán haønh nhieàu laàn vieäc loaïi boû phaàn töû goác
cuûa caây cho ñeán khi taát caû caùc phaàn töû cuûa caây
cuûa caây cho ñeán khi taát caû caùc phaàn töû cuûa caây
ñeàu laø -¥
, khi ñoù xeáp caùc phaàn töû theo thöù töï loaïi
, khi ñoù xeáp caùc phaàn töû theo thöù töï loaïi
ñeàu laø -
boû treân caây seõ coù daõy ñaõ saép xeáp.
boû treân caây seõ coù daõy ñaõ saép xeáp.
Ñeå caøi ñaët thuaät toaùn hieäu quaû, caàn phaûi toå chöùc
Ñeå caøi ñaët thuaät toaùn hieäu quaû, caàn phaûi toå chöùc
moät caáu truùc löu tröõ döõ lieäu coù khaû naêng theå
moät caáu truùc löu tröõ döõ lieäu coù khaû naêng theå
hieän ñöôïc quan heä cuûa caùc phaàn töû trong caây vôùi n
hieän ñöôïc quan heä cuûa caùc phaàn töû trong caây vôùi n
oâ nhôù thay vì 2n-1 nhö trong ví duï.
oâ nhôù thay vì 2n-1 nhö trong ví duï.
Khaùi nieäm heap vaø phöông phaùp saép xeáp Heapsort do
Khaùi nieäm heap vaø phöông phaùp saép xeáp Heapsort do
J.Williams ñeà xuaát ñaõ giaûi quyeát ñöôïc caùc khoù
J.Williams ñeà xuaát ñaõ giaûi quyeát ñöôïc caùc khoù
khaên treân.
khaên treân. ¥ Heap sort
Saép xeáp caây - Heap sort
Saép xeáp caây - left, a, aleft+1 ,... ,
left+1,... , ‡ ‡ " ˛ a a2i2i
a a2i+12i+1
i i ˛ [left, right]
[left, right] Ñònh nghóa heap:
Ñònh nghóa heap:
Heap laø moät daõy caùc phaàn töû aleft
Heap laø moät daõy caùc phaàn töû a
thoaû caùc quan heä:
aaright
right thoaû caùc quan heä:
aaii ‡
aaii ‡
vôùi "
vôùi
) ñöôïc goïi laø caùc
Khi ñoù (aii , a , a2i2i), (a), (aii ,a ,a2i+12i+1) ñöôïc goïi laø caùc
Khi ñoù (a
caëp phaàn töû lieân ñôùi.
caëp phaàn töû lieân ñôùi.
Heap ñöôïc ñònh nghóa nhö treân ñöôïc
Heap ñöôïc ñònh nghóa nhö treân ñöôïc
duøng trong tröôøng hôïp saép xeáp taêng
duøng trong tröôøng hôïp saép xeáp taêng
daàn, khi saép xeáp giaûm daàn phaûi ñoåi
daàn, khi saép xeáp giaûm daàn phaûi ñoåi
chieàu caùc quan heä.
chieàu caùc quan heä. Ví duï daõy laø heap:
Ví duï daõy laø heap: 1 2 3 4 5 6 7 8 15 12 8 5 1 4 6 2 Saép xeáp caây – Heap sort
Saép xeáp caây – Heap sort a1 a2 a3 Caùc phaàn töû
cuûa daõy ñöôïc
bieåu dieãn
theo caùc moái
quan heä lieân
ñôùi a4 a5 a6 a7 a8 Heap sort
Saép xeáp caây - Heap sort
Saép xeáp caây - left+1, …, a , …, aright left, a, aleft+1 , ...,
left+1, ..., Moät soá tính chaát cuûa Heap:
Moät soá tính chaát cuûa Heap:
Tính chaát 1: Neáu aleft
laø moät
left, a, aleft+1
right laø moät
Tính chaát 1: Neáu a
heap thì khi caét boû moät soá phaàn töû ôû
heap thì khi caét boû moät soá phaàn töû ôû
hai ñaàu cuûa heap, daõy con coøn laïi vaãn
hai ñaàu cuûa heap, daõy con coøn laïi vaãn
laø moät heap.
laø moät heap.
laø moät
, …, ann laø moät
Tính chaát 2: Neáu a11, a, a22, …, a
Tính chaát 2: Neáu a
(ñaàu heap) luoân laø
heap thì phaàn töû a11 (ñaàu heap) luoân laø
heap thì phaàn töû a
phaàn töû lôùn nhaát trong heap.
phaàn töû lôùn nhaát trong heap.
Tính chaát 3: Moïi daõy con aleft
Tính chaát 3: Moïi daõy con a
aaright thoûa: 2left > right ñeàu laø heap.
right thoûa: 2left > right ñeàu laø heap. Ví duï caùc tính chaát cuûa
Ví duï caùc tính chaát cuûa
heap:
heap: 1 2 3 4 5 6 7 8 15 12 8 5 1 6 4 2 12 8 5 1 6 4 1 6 4 2 Heap sort
Saép xeáp caây - Heap sort
Saép xeáp caây - Saép xeáp daõy taêng daàn qua 2 giai ñoaïn:
Saép xeáp daõy taêng daàn qua 2 giai ñoaïn:
Giai ñoaïn 1: Döïa vaøo tính chaát 3 cuûa heap ñeå hieäu
Giai ñoaïn 1: Döïa vaøo tính chaát 3 cuûa heap ñeå hieäu
chænh daõy ban ñaàu thaønh heap
chænh daõy ban ñaàu thaønh heap
Giai ñoaïn 2: Döïa vaøo caùc tính chaát 1 vaø 2 cuûa
Giai ñoaïn 2: Döïa vaøo caùc tính chaát 1 vaø 2 cuûa
heap ñeå saép xeáp heap coù ñöôïc sau giai ñoaïn 1
heap ñeå saép xeáp heap coù ñöôïc sau giai ñoaïn 1
thaønh daõy taêng daàn
thaønh daõy taêng daàn Heap sort – Giai ñoaïn 1
Heap sort – Giai ñoaïn 1 Vaán ñeà: Ñoåi choå moät soá phaàn töû treân daõy a YÙ töôûng: theo tính chaát 3, daõy con a n/2-1, …, a , …,
Vaán ñeà: Ñoåi choå moät soá phaàn töû treân daõy a11, …,
ñeå daõy trôû thaønh heap.
aaNN ñeå daõy trôû thaønh heap.
YÙ töôûng: theo tính chaát 3, daõy con an/2+1
n/2+1 , ,
ñöông nhieân laø heap. Laàn löôït
... an n ñöông nhieân laø heap. Laàn löôït
aan/2+2
n/2+2 ... a
theâm vaøo phía tröôùc daõy caùc phaàn töû
theâm vaøo phía tröôùc daõy caùc phaàn töû
aan/2n/2, a, an/2-1
; moãi böôùc theâm vaøo caàn
, …, a11; moãi böôùc theâm vaøo caàn
hieäu chænh vò trí caùc phaàn töû theo moái
hieäu chænh vò trí caùc phaàn töû theo moái
quan heä lieân ñôùi ta seõ nhaän ñöôïc heap
quan heä lieân ñôùi ta seõ nhaän ñöôïc heap
mong muoán.
mong muoán. Heap sort – Giai ñoaïn 1
Heap sort – Giai ñoaïn 1 left, .., a left+1, …, a //input: daõy (a, N)
//input: daõy (a, N)
//output: daõy (a, N) laø moät heap
//output: daõy (a, N) laø moät heap
Böôùc 1: left = N/2; //Theâm caùc phaàn töû a vaøo
, .., a11 vaøo ñaõ laø heap
, …, aN N ñaõ laø heap left, …, a Böôùc 1: left = N/2; //Theâm caùc phaàn töû aleft
heapheap
Böôùc 2: Trong khi left > 0
Böôùc 2: Trong khi left > 0
//Löu yù: ñoaïn aleft+1
//Löu yù: ñoaïn a
Böôùc 21: Hieäu chænh ñoaïn a , …, aNN Böôùc 21: Hieäu chænh ñoaïn aleft
thaønh heap
thaønh heap
Böôùc 22: left = left - 1;
Böôùc 22: left = left - 1; //Heát laëp
//Heát laëp Heap sort – Giai ñoaïn 1
Heap sort – Giai ñoaïn 1 1 2 3 4 5 6 7 8 12 2 8 5 1 6 4 15 Heap sort – Giai ñoaïn 1
Heap sort – Giai ñoaïn 1 1 2 3 joint
6 5 joint
8 7 curr
4 12 2 8 6 1 4 5 15
5 left Heap sort – Giai ñoaïn 1
Heap sort – Giai ñoaïn 1 1 curr
2 joint
4 joint
5 6 7 joint
8 3 12 2 15 1 6 4 5 8
8 left Heap sort – Giai ñoaïn 1
Heap sort – Giai ñoaïn 1 curr
1 joint
3 joint
2 4 5 6 7 8 12 8 15 5 1 6 4 2 left Heap sort – Giai ñoaïn 1
Heap sort – Giai ñoaïn 1 1 2 3 4 5 6 7 8 15 12 8 5 1 6 4 2 Heap sort – Giai ñoaïn 2
Heap sort – Giai ñoaïn 2
Vaán ñeà: Saép xeáp heap a11, …, a
Vaán ñeà: Saép xeáp heap a
daàndaàn
//Ñaët: right = N daõy a
//Ñaët: right = N thaønh daõy taêng
, …, aNN thaønh daõy taêng YÙ töôûng:
YÙ töôûng:
Theo tính chaát 2: a laø heap.
right laø heap. daõy a11, …, a , …, aright Ñoåi choå (a right) ) ñöôïc theâm moät
ñöôïc theâm moät Theo tính chaát 2: a11 seõ laø phaàn töû lôùn nhaát,
seõ laø phaàn töû lôùn nhaát,
phaûi laø right -
vì vaäy vò trí ñuùng cuûa a11 phaûi laø right -
vì vaäy vò trí ñuùng cuûa a
cuoái daõy.
cuoái daõy. Theo tính chaát 3: daõy con a Ñoåi choå (a11, a, aright
phaàn töû ôû ñuùng vò trí
phaàn töû ôû ñuùng vò trí vaãn
right-1 vaãn , …, aright-1 Theo tính chaát 3: daõy con a22, …, a
laø heap
laø heap
Giaûm right, theâm a Giaûm right, theâm a11 vaøo daõy vaø hieäu
vaøo daõy vaø hieäu
chænh laïi
chænh laïi daõy a right laø heap. laø heap. daõy a11, …, a , …, aright Heap sort – Giai ñoaïn 2
Heap sort – Giai ñoaïn 2
//input: daõy (a, N) laø heap
//input: daõy (a, N) laø heap
//output: daõy (a, N) saép taêng daàn
//output: daõy (a, N) saép taêng daàn
Böôùc 1: right = N; //Baét ñaàu thöïc hieän töø cuoái daõy
Böôùc 1: right = N; //Baét ñaàu thöïc hieän töø cuoái daõy
Böôùc 2: Trong khi right > 1
Böôùc 2: Trong khi right > 1 Böôùc 21: Hoaùnvò (a right);); right
, …, aright Hieäu chænh ñoaïn aa11, a, a22, …, a //Ñöa phaàn töû lôùn nhaát (a11)veà vò trí right
)veà vò trí right
//Ñöa phaàn töû lôùn nhaát (a
Böôùc 21: Hoaùnvò (a11 , a , aright
//Loaïi boû phaàn töû lôùn nhaát ra khoûi heap
//Loaïi boû phaàn töû lôùn nhaát ra khoûi heap
Böôùc 22: right := right -1;
Böôùc 22: right := right -1;
Böôùc 23: Hieäu chænh ñoaïn
Böôùc 23:
thaønh heap
thaønh heap //Heát laëp
//Heát laëp Heap sort – Giai ñoaïn 2
Heap sort – Giai ñoaïn 2 1 2 3 4 5 6 7 8 15 12 8 5 1 6 4 2 right Swap(a1, aright) Heap sort – Giai ñoaïn 2
Heap sort – Giai ñoaïn 2 curr
1 joint
2 joint
3 4 5 6 7 8 2 12 8 5 1 6 4 15 right Shift(a, 1, right) Heap sort – Giai ñoaïn 2
Heap sort – Giai ñoaïn 2 1 2 3 4 5 6 7 8 12 5 8 2 1 6 4 15 right Swap(a1, aright) Heap sort – Giai ñoaïn 2
Heap sort – Giai ñoaïn 2 curr
1 joint
2 joint
3 4 5 joint
6 7 8 4 5 8 2 1 6 12 15 right Shift(a, 1, right) Heap sort – Giai ñoaïn 2
Heap sort – Giai ñoaïn 2 1 2 3 4 5 6 7 8 8 5 6 2 1 4 12 15 right Swap(a1, aright) Heap sort – Giai ñoaïn 2
Heap sort – Giai ñoaïn 2 1 2 3 4 5 6 7 8 4 5 6 2 1 8 12 15 1 2 4 5 6 8 12 15 Heap sort – Hieäu chænh heap
Heap sort – Hieäu chænh heap
Vaán ñeà: daõy con a YÙ töôûng: do a left+2, …, a left+1, a, aleft+2 left+2, …, a
left, …, a
, …, aright , …, aright
, …, aright laø heap,
Vaán ñeà: daõy con aleft+1
left+1, a, aleft+2
right laø heap,
laø heap
caàn hieäu chænh laïi ñeå aleft
right laø heap
caàn hieäu chænh laïi ñeå a
laø heap neân
YÙ töôûng: do aleft+1
right laø heap neân
taát caû caùc phaàn töû naøy ñeàu ñaõ thoûa
taát caû caùc phaàn töû naøy ñeàu ñaõ thoûa
ñieàu kieän lieân ñôùi vaán ñeà trôû thaønh:
vaán ñeà trôû thaønh:
ñieàu kieän lieân ñôùi
vaø ñoåi
kieåm tra quan heä lieân ñôùi cuûa aleft
left vaø ñoåi
kieåm tra quan heä lieân ñôùi cuûa a
vôùi lieân ñôùi thích hôïp cuûa noù neáu
choå aleft
choå a
left vôùi lieân ñôùi thích hôïp cuûa noù neáu
quan heä lieân ñôùi bò vi phaïm; sau khi hieäu
quan heä lieân ñôùi bò vi phaïm; sau khi hieäu
chænh söï vi phaïm ñieàu kieän lieân ñôùi coù
chænh söï vi phaïm ñieàu kieän lieân ñôùi coù
theå lan truyeàn ñeán caùc vò trí môùi hieäu
theå lan truyeàn ñeán caùc vò trí môùi hieäu
chænh.
chænh. Heap sort – Hieäu chænh heap
Heap sort – Hieäu chænh heap 1 curr
2 joint
4 joint
5 3 6 7 joint
8 2 15 1 8 6 4 2
5 right left Heap sort – Hieäu chænh heap
Heap sort – Hieäu chænh heap
Nhaän xeùt: Quaù trình hieäu chænh coù nhieàu böôùc ñoåi
Nhaän xeùt: Quaù trình hieäu chænh coù nhieàu böôùc ñoåi
choã trung gian khoâng caàn thieát.
choã trung gian khoâng caàn thieát.
Trong ví duï: ñoåi choã (2, 15), sau ñoù ñoåi choå tieáp (2, 5):
Trong ví duï: ñoåi choã (2, 15), sau ñoù ñoåi choå tieáp (2, 5):
vò trí cuoái cuøng cuûa 2 laø 8, 2 ôû vò trí 4 chæ laø taïm
vò trí cuoái cuøng cuûa 2 laø 8, 2 ôû vò trí 4 chæ laø taïm
thôøi, khoâng caàn thieát.
thôøi, khoâng caàn thieát.
Coù theå thöïc hieän vieäc dôøi choã haøng loaït, sau ñoù ñöa
Coù theå thöïc hieän vieäc dôøi choã haøng loaït, sau ñoù ñöa
giaù trò caàn hieäu chænh vaøo ñuùng choã
giaù trò caàn hieäu chænh vaøo ñuùng choã left+2, …, a
left+1, …, a left+1, a, aleft+2
left, a, aleft+1 Heap sort – Hieäu chænh heap
Heap sort – Hieäu chænh heap
//input: daõy con a
//input:
//output: daõy con a
//output: daõy
Böôùc 1:
Böôùc 1: laø heap
right laø heap
laø heap
right laø heap daõy con aleft+1
con aleft , …, aright
, …, aright curr = left; x = acurr
curr = left; x = a
joint = 2*curr;
joint = 2*curr; Böôùc 2: Trong khi (joint ≤ right) Böôùc 21: Neáu (joint < right) && (a //Baét ñaàu kieåm tra töø vò trí left
curr; ; //Baét ñaàu kieåm tra töø vò trí left
//Lieân ñôùi thöù nhaát cuûa curr
//Lieân ñôùi thöù nhaát cuûa curr
//Coøn lieân ñôùi ñeå xeùt
Böôùc 2: Trong khi (joint ≤ right) //Coøn lieân ñôùi ñeå xeùt joint))
joint+1 > a > ajoint Böôùc 21: Neáu (joint < right) && (ajoint+1 //joint: vò trí lieân ñôùi lôùn
joint = joint + 1; //joint: vò trí lieân ñôùi lôùn
joint = joint + 1;
nhaát
nhaát Böôùc 22: Neáu a joint ≤ x //Thoûa ñieàu kieän lieân
≤ x //Thoûa ñieàu kieän lieân Böôùc 23: a Böôùc 22: Neáu ajoint
ñôùi
ñôùi ; curr = joint; joint =
joint; curr = joint; joint = Chuyeån ñeán Böôùc 3
Chuyeån ñeán Böôùc 3
= ajoint Böôùc 23: acurrcurr = a
2*curr;
2*curr; //Heát laëp //Heát laëp Böôùc 3: a = x; Böôùc 3: acurrcurr = x; Heap sort – Hieäu chænh heap
Heap sort – Hieäu chænh heap 1 curr
2 joint
4 ???
5 3 6 7 joint
8 2 15 1 8 6 4 2
5 right left Heap sort – Caøi ñaët
Heap sort – Caøi ñaët Ñeå caøi ñaët giaûi thuaät Heapsort caàn xaây döïng caùc
Ñeå caøi ñaët giaûi thuaät Heapsort caàn xaây döïng caùc
thuû tuïc:
thuû tuïc:
Thuû tuïc hieäu chænh daõy a left+1, …, a right
, …, aright left, a, aleft+1 Thuû tuïc chuyển đổi daõy a Thuû tuïc hieäu chænh daõy aleft
thaønh heap:
thaønh heap: (int a[], int N ) Thuû tuïc saép xeáp daõy a , …, aN-1N-1 void Shift
Shift (int a[], int left, int right)
(int a[], int left, int right)
void
Thuû tuïc chuyển đổi daõy a00, a, a22, …, a
thaønh heap:
thaønh heap:
CreateHeap(int a[], int N )
void CreateHeap
void
Thuû tuïc saép xeáp daõy a00, a, a22, …, a
daàn:
daàn:
void HeapSort
void HeapSort(int a[], int N) (int a[], int N) taêng
, …, aN-1N-1 taêng Heap sort – Caøi ñaët
Heap sort – Caøi ñaët ñôùi truyeàn Heap sort – Caøi ñaët
Heap sort – Caøi ñaët ử ầ Heap Sort – Caøi ñaët
Heap Sort – Caøi ñaët Heap Sort – Ñaùnh giaù giaûi thuaät
Heap Sort – Ñaùnh giaù giaûi thuaät Vieäc ñaùnh giaù moät caùch chính xaùc giaûi thuaät Heapsort
Vieäc ñaùnh giaù moät caùch chính xaùc giaûi thuaät Heapsort
raát phöùc taïp. Tuy nhieân, coù theå ñaùnh giaù moät caùch
raát phöùc taïp. Tuy nhieân, coù theå ñaùnh giaù moät caùch
töông ñoái döïa vaøo moät soá nhaän xeùt:
töông ñoái döïa vaøo moät soá nhaän xeùt:
Khi xem xeùt heap ôû daïng caây quan heä lieân ñôùi » loglog22N.N. Khi xem xeùt heap ôû daïng caây quan heä lieân ñôùi
caùc phaàn töû cuûa heap taïo thaønh caây nhò phaân coù
caùc phaàn töû cuûa heap taïo thaønh caây nhò phaân coù
ñoä cao h»
ñoä cao h
ÔÛ moãi böôùc hieäu chænh, soá pheùp ñieàu
ÔÛ moãi böôùc hieäu chænh, soá pheùp ñieàu
chænh caùc vi phaïm lieân ñôùi khoâng vöôït
chænh caùc vi phaïm lieân ñôùi khoâng vöôït
quaù chieàu cao h cuûa caây lieân ñôùi.
quaù chieàu cao h cuûa caây lieân ñôùi.
ÔÛ caû giai ñoaïn 1 vaø giai ñoaïn 2 soá pheùp
ÔÛ caû giai ñoaïn 1 vaø giai ñoaïn 2 soá pheùp
hieäu chænh khoâng vöôït quaù N
hieäu chænh khoâng vöôït quaù N Trong tröôøng hôïp xaáu nhaát ñoä phöùc taïp
Trong tröôøng hôïp xaáu nhaát ñoä phöùc taïp
thuaät toaùn O(Nlog22N)N)
thuaät toaùn O(Nlog Shell sort – YÙ töôûng
Shell sort – YÙ töôûng ñöôïc xem nhö söï xen
, ..., aNN ñöôïc xem nhö söï xen ...
2len+1 ... Daõy con thöù hai :
........
Daõy con thöù len : ...
Daõy con thöù len : a alenlen a a2len2len a a3len3len ... Shell sort – YÙ töôûng
Shell sort – YÙ töôûng
Vieäc saép xeáp caùc phaàn töû trong cuøng daõy con seõ laøm
Vieäc saép xeáp caùc phaàn töû trong cuøng daõy con seõ laøm
cho caùc phaàn töû ñöôïc ñöa veà vò trí ñuùng töông ñoái
cho caùc phaàn töû ñöôïc ñöa veà vò trí ñuùng töông ñoái
(chæ ñuùng trong daõy con, so vôùi toaøn boä caùc phaàn töû
(chæ ñuùng trong daõy con, so vôùi toaøn boä caùc phaàn töû
trong daõy ban ñaàu coù theå chöa ñuùng) moät caùch nhanh
trong daõy ban ñaàu coù theå chöa ñuùng) moät caùch nhanh
choùng.
choùng.
Khi khoaûng caùch len giaûm taïo thaønh caùc daõy con môùi
Khi khoaûng caùch len giaûm taïo thaønh caùc daõy con môùi
moät phaàn töû ñöôïc so saùnh vôùi nhieàu phaàn töû khaùc
moät phaàn töû ñöôïc so saùnh vôùi nhieàu phaàn töû khaùc
tröôùc ñoù khoâng ôû cuøng daõy con vôùi noù.
tröôùc ñoù khoâng ôû cuøng daõy con vôùi noù.
Thuaät toaùn döøng sau khi saép xong daõy con vôùi len = 1,
Thuaät toaùn döøng sau khi saép xong daõy con vôùi len = 1,
thuaät toaùn luùc naøy thöïc hieän nhö thuaät toaùn cheøn tröïc
thuaät toaùn luùc naøy thöïc hieän nhö thuaät toaùn cheøn tröïc
tieáp. Tuy nhieân, phaàn lôùn caùc phaàn töû trong daõy ñaõ
tieáp. Tuy nhieân, phaàn lôùn caùc phaàn töû trong daõy ñaõ
coù thöù töï boä phaän.
coù thöù töï boä phaän.
Caùc phaàn töû treân cuøng moät daõy con caùch nhau len vò
Caùc phaàn töû treân cuøng moät daõy con caùch nhau len vò
trí ñöôïc goïi laø cuøng daõy lieân ñôùi böôùc
trí ñöôïc goïi laø cuøng daõy lieân ñôùi böôùc lenlen.. Shell sort – Thuaät toaùn
Shell sort – Thuaät toaùn
//input: daõy (a, N); daõy (h, k): k ñoä daøi caùc böôùc laëp -
//input: daõy (a, N); daõy (h, k): k ñoä daøi caùc böôùc laëp - const
const //ñoä daøi böôùc coøn >1
//ñoä daøi böôùc coøn >1
//laáy ñoä daøi böôùc
//laáy ñoä daøi böôùc //output: daõy (a, N) laø ñöôïc saép taêng daàn
//output: daõy (a, N) laø ñöôïc saép taêng daàn
//h[step]: ñoä daøi böôùc laëp
Böôùc 1: step = 1;
Böôùc 1: step = 1; //h[step]: ñoä daøi böôùc laëp
Böôùc 2: Trong khi (step ≤ k)
Böôùc 2: Trong khi (step ≤ k)
Böôùc 21: len = h[step];
Böôùc 21: len = h[step];
//saép xeáp caùc
Böôùc 22: Laëp vôùi i=len+1 .. N //saép xeáp caùc
Böôùc 22: Laëp vôùi i=len+1 .. N
//ñôùi böôùc len
daõy lieân
//ñôùi böôùc len
daõy lieân daõy lieân ñôùi böôùc len;;
Cheøn a[i] vaøo daõy lieân ñôùi böôùc len
Cheøn a[i] vaøo Böôùc 23: step ++;
Böôùc 23: step ++; //Heát laëp
//Heát laëp Shell sort – Ví duï
Shell sort – Ví duï joint
1 2 3 4 5 curr
6 7 8 12 2 8 5 1 6 4 15 Shell sort – Ví duï
Shell sort – Ví duï 1 2 3 4 5 6 7 8 6 2 8 5 1 12 4 15 Shell sort – Ví duï
Shell sort – Ví duï joint
1 2 3 curr
4 5 6 7 8 6 2 15 5 1 12 4 8 Shell sort – Ví duï
Shell sort – Ví duï joint
1 2 3 joint
4 5 6 curr
7 8 5 1 12 6 2 15 4 8 Shell sort – Ví duï
Shell sort – Ví duï 1 2 3 4 5 6 7 8 4 1 12 5 2 15 6 8 Shell sort – Ví duï
Shell sort – Ví duï joint
1 jointcurr
2 joint
3 4 5 6 7 8 4 1 12 5 2 15 6 8 Shell sort – Ví duï
Shell sort – Ví duï joint
1 joint
2 joint
3 joint
joint
4 jointcurr
5 joint
6 joint
7 8 1 4 5 12 2 15 6 8 Shell sort – Ví duï
Shell sort – Ví duï 1 2 3 4 5 6 7 8 1 2 4 5 6 8 12 15 con Shell sort – Ñaùnh giaù giaûi thuaät
Shell sort – Ñaùnh giaù giaûi thuaät Yeáu toá quyeát ñònh tính hieäu quaû cuûa thuaät toaùn:
Yeáu toá quyeát ñònh tính hieäu quaû cuûa thuaät toaùn:
Caùch choïn khoaûng caùch h trong töøng böôùc saép
Caùch choïn khoaûng caùch h trong töøng böôùc saép
xeápxeáp
Soá böôùc saép xeáp.
Soá böôùc saép xeáp.
Giaû söû quyeát ñònh saép xeáp k böôùc, caùc khoaûng
Giaû söû quyeát ñònh saép xeáp k böôùc, caùc khoaûng
caùch choïn phaûi thoûa ñieàu kieän :
caùch choïn phaûi thoûa ñieàu kieän : i+1 vaø h hhi i > h > hi+1 vaø hk k = 1= 1 Shell sort – Ñaùnh giaù giaûi thuaät
Shell sort – Ñaùnh giaù giaûi thuaät Chöa coù tieâu chuaån roõ raøng trong vieäc löïa choïn
Chöa coù tieâu chuaån roõ raøng trong vieäc löïa choïn
daõy giaù trò khoaûng caùch toát nhaát. Moät gôïi yù: daõy
daõy giaù trò khoaûng caùch toát nhaát. Moät gôïi yù: daõy
ñöôïc choïn khoâng neân coù caùc soá laø boäi soá cuûa
ñöôïc choïn khoâng neân coù caùc soá laø boäi soá cuûa
nhau.
nhau.
Moät soá daõy ñöôïc Knuth ñeà nghò :
Moät soá daõy ñöôïc Knuth ñeà nghò : i-1 - 1)/3 vaø h = (hi-1 - 1)/3 vaø hk k = 1, k = log = 1, k = log33n-1n-1 hhi i = (h
ví duï: 121, 40, 13, 4, 1
ví duï: 121, 40, 13, 4, 1 hay hay = (hi-1i-1 - 1)/2 vaø h - 1)/2 vaø hkk = 1, k = log = 1, k = log22n-1n-1 hhii = (h
ví duï: 15, 7, 3, 1
ví duï: 15, 7, 3, 1 Shell sort – Ñaùnh giaù giaûi thuaät
Shell sort – Ñaùnh giaù giaûi thuaät Vieäc ñaùnh giaù giaûi thuaät Shellsort daãn ñeán nhöõng
Vieäc ñaùnh giaù giaûi thuaät Shellsort daãn ñeán nhöõng
vaán ñeà toaùn hoïc raát phöùc taïp, thaäm chí moät soá
vaán ñeà toaùn hoïc raát phöùc taïp, thaäm chí moät soá
chöa ñöôïc chöùng minh.
chöa ñöôïc chöùng minh.
Hieäu quaû cuûa thuaät toaùn coøn phuï thuoäc vaøo daõy
Hieäu quaû cuûa thuaät toaùn coøn phuï thuoäc vaøo daõy
caùc ñoä daøi ñöôïc choïn.
caùc ñoä daøi ñöôïc choïn.
Trong tröôøng hôïp choïn daõy ñoä daøi theo coâng thöùc
Trong tröôøng hôïp choïn daõy ñoä daøi theo coâng thöùc hhi i = (h = (hi-1 = 1, k = log22N-1 N-1 » - 1)/2 vaø hk k = 1, k = log
i-1 - 1)/2 vaø h
thì giaûi thuaät coù ñoä phöùc taïp »
thì giaûi thuaät coù ñoä phöùc taïp n n1,21,2 << n << n22 Quick sort – YÙ töôûng
Quick sort – YÙ töôûng
Moät vaøi haïn cheá cuûa thuaät toaùn Ñoä phöùc taïp cuûa thuaät toaùn O(N Moät vaøi haïn cheá cuûa thuaät toaùn Ñoåi choã tröïc tieáp
Ñoåi choã tröïc tieáp::
Moãi laàn ñoåi choå chæ thay ñoåi 1 caëp phaàn töû trong
Moãi laàn ñoåi choå chæ thay ñoåi 1 caëp phaàn töû trong
> ajj
i < j < k vaø aii > a
nghòch theá; caùc tröôøng hôïp nhö: i < j < k vaø a
nghòch theá; caùc tröôøng hôïp nhö:
> a> akk (*)(*) chæ caàn thöïc hieän 1 laàn ñoåi choå
chæ caàn thöïc hieän 1 laàn ñoåi choå
): thuaät toaùn khoâng laøm ñöôïc.
(a(aii, a, akk): thuaät toaùn khoâng laøm ñöôïc.
Ñoä phöùc taïp cuûa thuaät toaùn O(N22) ) khi
khi
N ñuû lôùn thuaät toaùn seõ raát chaäm
N ñuû lôùn thuaät toaùn seõ raát chaäm
YÙ töôûng: phaân chia daõy thaønh caùc ñoaïn
YÙ töôûng: phaân chia daõy thaønh caùc ñoaïn
con taän duïng ñöôïc caùc pheùp ñoåi choã
taän duïng ñöôïc caùc pheùp ñoåi choã
con
daïng (*) vaø laøm giaûm ñoä daøi daõy khi saép
daïng (*) vaø laøm giaûm ñoä daøi daõy khi saép
xeáp caûi thieän ñaùng keå ñoä phöùc taïp
caûi thieän ñaùng keå ñoä phöùc taïp
xeáp
cuûa thuaät toaùn.
cuûa thuaät toaùn. Quick sort – YÙ töôûng
Quick sort – YÙ töôûng
Giaûi thuaät QuickSort saép xeáp daõy ..., aNN döïa treân
döïa treân Giaûi thuaät QuickSort saép xeáp daõy a a11, a, a22 ..., a
vieäc phaân hoaïch daõy ban ñaàu thaønh 3 phaàn :
vieäc phaân hoaïch daõy ban ñaàu thaønh 3 phaàn :
Phaàn 1: ‡ x , vôùi k = i..N
x , vôùi k = i..N Goàm caùc phaàn töû coù giaù trò khoâng lôùn hôn
Phaàn 1: Goàm caùc phaàn töû coù giaù trò khoâng lôùn hôn
xx
Phaàn 2:
Goàm caùc phaàn töû coù giaù trò baèng xx
Phaàn 2: Goàm caùc phaàn töû coù giaù trò baèng
Phaàn 3:
Goàm caùc phaàn töû coù giaù trò khoâng beù hôn xx
Phaàn 3: Goàm caùc phaàn töû coù giaù trò khoâng beù hôn
vôùi x laø giaù trò cuûa moät phaàn töû tuøy yù trong daõy ban
vôùi x laø giaù trò cuûa moät phaàn töû tuøy yù trong daõy ban
ñaàu.
ñaàu.
Sau khi thöïc hieän phaân hoaïch, daõy ban ñaàu ñöôïc phaân
Sau khi thöïc hieän phaân hoaïch, daõy ban ñaàu ñöôïc phaân
thaønh 3 ñoaïn:
thaønh 3 ñoaïn:
≤ x , vôùi k = 1 .. j
1. a1. akk ≤ x , vôùi k = 1 .. j
2. a2. akk = x , vôùi k = j+1 .. i-1
= x , vôùi k = j+1 .. i-1
3. a3. akk ‡ Quick sort – YÙ töôûng
Quick sort – YÙ töôûng Ñoaïn thöù 2 ñaõ coù thöù töï.
Ñoaïn thöù 2 ñaõ coù thöù töï.
Neáu caùc ñoaïn 1 vaø 3 chæ coù 1 phaàn töû thì chuùng
Neáu caùc ñoaïn 1 vaø 3 chæ coù 1 phaàn töû thì chuùng
cuõng ñaõ coù thöù töï, khi ñoù daõy con ban ñaàu ñaõ
cuõng ñaõ coù thöù töï, khi ñoù daõy con ban ñaàu ñaõ
ñöôïc saép.
ñöôïc saép.
Ngöôïc laïi, neáu caùc ñoaïn 1 vaø 3 coù nhieàu hôn 1
Ngöôïc laïi, neáu caùc ñoaïn 1 vaø 3 coù nhieàu hôn 1
phaàn töû thì daõy con ban ñaàu chæ coù thöù töï khi caùc
phaàn töû thì daõy con ban ñaàu chæ coù thöù töï khi caùc
ñoaïn 1, 3 ñöôïc saép.
ñoaïn 1, 3 ñöôïc saép.
Ñeå saép xeáp caùc ñoaïn 1 vaø 3, ta laàn löôït tieán haønh
Ñeå saép xeáp caùc ñoaïn 1 vaø 3, ta laàn löôït tieán haønh
vieäc phaân hoaïch töøng daõy con theo cuøng phöông
vieäc phaân hoaïch töøng daõy con theo cuøng phöông
phaùp phaân hoaïch daõy ban ñaàu vöøa trình baøy …
phaùp phaân hoaïch daõy ban ñaàu vöøa trình baøy … Böôùc 2: Phaân hoaïch daõy a left … a ‡ Quick sort – Giaûi thuaät
Quick sort – Giaûi thuaät
//input: daõy con (a, left, right)
//input: daõy con (a, left, right)
//output: daõy con (a, left, right) ñöôïc saép taêng daàn
//output: daõy con (a, left, right) ñöôïc saép taêng daàn
//daõy coù ít hôn 2 phaàn töû
Böôùc 1: Neáu
right //daõy coù ít hôn 2 phaàn töû
right
//daõy ñaõ ñöôïc saép xeáp
//daõy ñaõ ñöôïc saép xeáp
… aright right left.. a.. ajj,, aaj+1j+1.. a.. ai-1i-1,, aaii.. A.. Aright thaønh caùc
right thaønh caùc right ‡
= x - Ñoaïn 3: aii.. a.. aright Böôùc 3: ‡ left ‡
Böôùc 1: Neáu left
Keát thuùc;
Keát thuùc;
Böôùc 2: Phaân hoaïch daõy aleft
ñoaïn: aleft
ñoaïn: a
//Ñoaïn 1 ££
//Ñoaïn 1 x x Böôùc 4: Böôùc 3: Saép xeáp ñoaïn 1 x - Ñoaïn 2: aj+1j+1.. a.. ai-1i-1 = x - Ñoaïn 3: a
x - Ñoaïn 2: a
left.. a.. ajj Saép xeáp ñoaïn 1: a: aleft right Böôùc 4: Saép xeáp ñoaïn 3 Saép xeáp ñoaïn 3: a: aii.. a.. aright left, …, a right Quick sort – Phaân hoaïch daõy
Quick sort – Phaân hoaïch daõy
//input: daõy con aleft
//input: daõy con a
//output: daõy con chia thaønh 3 ñoaïn: ñoaïn 1 ≤ ñoaïn 2 ≤ ñoaïn 3
//output: daõy con chia thaønh 3 ñoaïn: ñoaïn 1 ≤ ñoaïn 2 ≤ ñoaïn 3
Böôùc 1: Choïn tuøy yù moät phaàn töû a[p] trong daõy
Böôùc 1: Choïn tuøy yù moät phaàn töû a[p] trong daõy
con laø giaù trò moác:
con laø giaù trò moác:
x = a[p];
x = a[p]; , …, aright a[j] maø a[j]
a[j] maø a[j] x x ‡ Böôùc 2: Duyeät töø 2 ñaàu daõy ñeå phaùt hieän vaø
Böôùc 2: Duyeät töø 2 ñaàu daõy ñeå phaùt hieän vaø
a[i], a[j] vi phaïm ñieàu
hieäu chænh caëp phaàn töû a[i], a[j] vi phaïm ñieàu
hieäu chænh caëp phaàn töû
kieän
kieän
Böôùc 21: i = left; j = right;
Böôùc 21: i = left; j = right;
Böôùc 22: Trong khi (a[i] ‡ ‡ i++; j--;
i++; j--;
Laëp laïi Böôùc 22.//chöa
Laëp laïi Böôùc 22.//chöa //Heát duyeät //Heát duyeät Quick sort – Ví duï
Quick sort – Ví duï
X 5 2 3 4 5 6 7 i
1 j
8 2 8 5 1 6 4 12 15 right left Not less than X Not greater than X Quick sort – Ví duï
Quick sort – Ví duï
X 5 i
2 3 4 5 j
6 7 1 8 2 8 5 1 6 12 4 15 right left Not less than X Not greater than X Quick sort – Ví duï
Quick sort – Ví duï 1 2 j
3 4 i
5 6 7 8 4 2 1 5 8 6 12 15 right left Quick sort – Ví duï
Quick sort – Ví duï X 1 2 3 4 6 7 i
5 j
8 1 2 4 5 6 12 8 15 right left Not less than X Not greater than X Quick sort – Ví duï
Quick sort – Ví duï j
5 i
6 7 8 1 2 3 4 6 8 12 15 1 2 4 5 right left Shell sort – Ví duï
Shell sort – Ví duï 1 2 3 4 5 6 7 8 1 2 4 5 6 8 12 15 Quick sort – Caøi ñaët
Quick sort – Caøi ñaët moác median. median. Quick sort – Ñaùnh giaù giaûi
Quick sort – Ñaùnh giaù giaûi
thuaät
thuaät
Hieäu quaû phuï thuoäc vaøo vieäc choïn giaù trò moác:
Hieäu quaû phuï thuoäc vaøo vieäc choïn giaù trò moác: Tröôøng hôïp toát nhaát: moãi laàn phaân hoaïch ñeàu
Tröôøng hôïp toát nhaát: moãi laàn phaân hoaïch ñeàu
choïn phaàn töû median laøm moác, khi ñoù daõy ñöôïc
choïn phaàn töû median laøm moác, khi ñoù daõy ñöôïc
(n)
phaân chia thaønh 2 phaàn baèng nhau vaø caàn log22(n)
phaân chia thaønh 2 phaàn baèng nhau vaø caàn log
laàn phaân hoaïch thì saép xeáp xong.
laàn phaân hoaïch thì saép xeáp xong.
Neáu moãi laàn phaân hoaïch choïn phaàn töû
Neáu moãi laàn phaân hoaïch choïn phaàn töû
coù giaù trò cöïc ñaïi (hay cöïc tieåu) laø moác
coù giaù trò cöïc ñaïi (hay cöïc tieåu) laø moác
daõy seõ bò phaân chia thaønh 2 phaàn
daõy seõ bò phaân chia thaønh 2 phaàn
khoâng ñeàu: moät phaàn chæ coù 1 phaàn
khoâng ñeàu: moät phaàn chæ coù 1 phaàn
töû, phaàn coøn laïi goàm (n-1) phaàn töû, do
töû, phaàn coøn laïi goàm (n-1) phaàn töû, do
vaäy caàn phaân hoaïch n laàn môùi saép
vaäy caàn phaân hoaïch n laàn môùi saép
xeáp xong.
xeáp xong. Quick sort – Ñaùnh giaù giaûi
Quick sort – Ñaùnh giaù giaûi
thuaät
thuaät Ñoä phöùc taïp
Ñoä phöùc taïp Tröôøng
Tröôøng
hôïphôïp Toát nhaát
Toát nhaát O(NlogN)
O(NlogN) Trung bình
Trung bình O(NlogN)
O(NlogN) Xaáu nhaát
Xaáu nhaát O(NO(N2)2) Saép xeáp theo
Saép xeáp theo
phöông phaùp troän tröïc
phöông phaùp troän tröïc
tieáp
tieáp
Merge Sort
Merge Sort Merge sort – YÙ töôûng
Merge sort – YÙ töôûng Giaûi thuaät Merge sort saép xeáp , ..., ann döïa
döïa Giaûi thuaät Merge sort saép xeáp daõydaõy a a11, a, a22, ..., a
treân nhaän xeùt sau:
treân nhaän xeùt sau:
Moãi daõy Moãi daõy aa11, a, a22, ..., a
, ..., ann baát kyø laø moät taäp hôïp caùc
baát kyø laø moät taäp hôïp caùc
daõy con lieân tieáp maø moãi daõy con ñeàu ñaõ coù
daõy con lieân tieáp maø moãi daõy con ñeàu ñaõ coù
thöù töï.
thöù töï. Ví duï: daõy 12, 2, 8, 5, 1, 6, 4, 15 coù theå coi nhö
Ví duï: daõy 12, 2, 8, 5, 1, 6, 4, 15 coù theå coi nhö
goàm 5 daõy con khoâng giaûm (12); (2, 8); (5); (1,
goàm 5 daõy con khoâng giaûm (12); (2, 8); (5); (1,
6); (4, 15).
6); (4, 15). Daõy ñaõ coù thöù töï coi nhö coù 1 daõy con.
Daõy ñaõ coù thöù töï coi nhö coù 1 daõy con.
Höôùng tieáp caän: tìm caùch laøm
Höôùng tieáp caän: tìm caùch laøm
giaûm soá daõy con khoâng giaûm cuûa
giaûm soá daõy con khoâng giaûm cuûa
daõy ban ñaàu.
daõy ban ñaàu. Merge sort – YÙ töôûng
Merge sort – YÙ töôûng
Caùc vaán ñeà caàn giaûi quyeát:
Caùc vaán ñeà caàn giaûi quyeát:
Phöông aùn phaân hoaïch daõy ban ñaàu thaønh caùc daõy
Phöông aùn phaân hoaïch daõy ban ñaàu thaønh caùc daõy
con.con.
Phöông aùn laøm giaûm soá daõy con.
Phöông aùn laøm giaûm soá daõy con.
Phaân hoaïch daõy ban ñaàu thaønh caùc daõy con taêng daàn:
Phaân hoaïch daõy ban ñaàu thaønh caùc daõy con taêng daàn:
Phöông aùn 1: Phaân hoaïch daõy theo caùc ñöôøng chaïy Phöông aùn 1: Phaân hoaïch daõy theo caùc ñöôøng chaïy
saép xeáp troän töï nhieân.
saép xeáp troän töï nhieân.
Phöông aùn 2: Phaân hoaïch thaønh caùc daõy con coù soá
Phöông aùn 2: Phaân hoaïch thaønh caùc daõy con coù soá
phaàn töû baèng nhau (1, 2, 4, …) saép xeáp troän tröïc
saép xeáp troän tröïc
phaàn töû baèng nhau (1, 2, 4, …)
tieáp.
tieáp. Merge sort – Giaûi thuaät
Merge sort – Giaûi thuaät
//input: daõy (a, N)
//input: daõy (a, N)
//output: daõy (a, N) ñöôïc saép taêng daàn
//output: daõy (a, N) ñöôïc saép taêng daàn
Böôùc 1 : k = 1; Böôùc 2 : Laëp trong khi (k < N) // daõy con coù 1 phaàn töû laø daõy
Böôùc 1 : k = 1; // daõy con coù 1 phaàn töû laø daõy
khoâng giaûm
khoâng giaûm
// daõy coøn hôn 1
Böôùc 2 : Laëp trong khi (k < N) // daõy coøn hôn 1
daõy con
daõy con
Böôùc 21: daõy
Phaân phoái ñeàu luaân phieân daõy
thaønh 2 daõy b, c theo töøng
, …, ann thaønh 2 daõy b, c theo töøng 2k+1, …, a , …, akk, a, a2k+1 , …, a3k3k, …, …
3k+1, …, a , …, a4k4k, …, … , …, a2k2k, a, a3k+1
töøng caëp daõy con goàm k
Troän töøng caëp daõy con goàm k Böôùc 21: Phaân phoái ñeàu luaân phieân
aa11, a, a22, …, a
nhoùm k phaàn töû lieân tieáp nhau.
nhoùm k phaàn töû lieân tieáp nhau. Merge sort – Ví duï
Merge sort – Ví duï Phaân phoái ñeàu luaân phieân 1 2 3 4 5 6 7 8 12 2 8 5 1 6 4 15 Merge sort – Ví duï
Merge sort – Ví duï Phaân phoái ñeàu luaân phieân 1 2 3 4 5 6 7 8 12 2 8 5 1 6 4 15 Merge sort – Ví duï
Merge sort – Ví duï Troän töøng caëp ñöôøng chaïy 1 2 3 4 5 6 7 8 4 8 12 1 5 2 6 15 Merge sort – Ví duï
Merge sort – Ví duï Troän töøng caëp ñöôøng chaïy 1 2 3 4 5 6 7 8 4 8 12 1 5 2 6 15 Merge sort – Ví duï
Merge sort – Ví duï Phaân phoái ñeàu luaân phieân 1 2 3 4 5 6 7 8 2 12 5 8 1 6 4 15 Merge sort – Ví duï
Merge sort – Ví duï Troän töøng caëp ñöôøng chaïy 1 2 3 4 5 6 7 8 6 12 2 1 8 5 4 15 Merge sort – Ví duï
Merge sort – Ví duï Troän töøng caëp ñöôøng chaïy 1 2 3 4 5 6 7 8 6 12 2 1 8 5 4 15 Merge sort – Ví duï
Merge sort – Ví duï Phaân phoái ñeàu luaân phieân 1 2 3 4 5 6 7 8 2 5 8 12 1 4 6 15 Merge sort – Ví duï
Merge sort – Ví duï Troän töøng caëp ñöôøng chaïy 2 3 4 5 6 7 8 1 12 5 2 8 4 1 6 15 Merge sort – Ví duï
Merge sort – Ví duï Troän töøng caëp ñöôøng chaïy 2 3 4 5 6 7 8 1 12 5 2 8 4 1 6 15 Merge sort – Ví duï
Merge sort – Ví duï 1 2 3 4 5 6 7 8 1 2 4 5 6 8 12 15 Only one subarray Merge sort – Ví duï
Merge sort – Ví duï 1 2 3 4 5 6 7 8 1 2 4 5 6 8 12 15 Distribute: Phaân phoái ñeàu luaân phieân caùc daõy
Phaân phoái ñeàu luaân phieân caùc daõy con ñoä daøi k töø maûng a vaøo hai maûng b vaø c
con ñoä daøi k töø maûng a vaøo hai maûng b vaø c Merge sort – Caøi ñaët
Merge sort – Caøi ñaët //khai baùo 2 maûng phuï
//khai baùo 2 maûng phuï
int b[MAX], c[MAX], nb, nc; Merge sort – Caøi ñaët
Merge sort – Caøi ñaët Merge sort – Caøi ñaët
Merge sort – Caøi ñaët if (b[pb] < c[pc]) Merge Sort – Ñaùnh giaù giaûi
Merge Sort – Ñaùnh giaù giaûi
thuaät
thuaät
Giaûi thuaät troän tröïc tieáp laø phöông phaùp troän ñôn giaûn
Giaûi thuaät troän tröïc tieáp laø phöông phaùp troän ñôn giaûn nhaát:
nhaát:
Vieäc phaân hoaïch thaønh caùc daõy con chæ laø taùch daõy
Vieäc phaân hoaïch thaønh caùc daõy con chæ laø taùch daõy
thaønh caùc daõy con khoâng giaûm ñoä daøi k.
thaønh caùc daõy con khoâng giaûm ñoä daøi k.
Ñoä daøi cuûa daõy con laø 1, 2, 4, 8, … ñaûm baûo daõy con
Ñoä daøi cuûa daõy con laø 1, 2, 4, 8, … ñaûm baûo daõy con
luoân laø daõy con khoâng giaûm sau moãi böôùc taùch - troän.
luoân laø daõy con khoâng giaûm sau moãi böôùc taùch - troän.
Khoâng söû duïng thoâng tin veà thöù töï cuûa daõy ban ñaàu
Khoâng söû duïng thoâng tin veà thöù töï cuûa daõy ban ñaàu
2 heä quaû:
2 heä quaû:
Ñoä phöùc taïp thuaät toaùn khoâng phuï thuoäc vaøo daõy
Ñoä phöùc taïp thuaät toaùn khoâng phuï thuoäc vaøo daõy
ban ñaàu.
ban ñaàu.
Moät daõy con khoâng giaûm ñang coù saün bò chia nhoû
Moät daõy con khoâng giaûm ñang coù saün bò chia nhoû
thaønh caùc daõy khoâng caàn thieát caûi tieán thaønh
caûi tieán thaønh
thaønh caùc daõy khoâng caàn thieát
(Natural Merge sort)..
thuaät toaùn: Troän töï nhieân (Natural Merge sort)
thuaät toaùn: Troän töï nhieân Merge Sort – Ñaùnh giaù giaûi thuaät
Merge Sort – Ñaùnh giaù giaûi thuaät Soá laàn thöïc hieän vieäc chia luaân phieân vaø troän:
Soá laàn thöïc hieän vieäc chia luaân phieân vaø troän:
Sau moãi laàn taùch – troän, ñoä daøi K cuûa daõy con
Sau moãi laàn taùch – troän, ñoä daøi K cuûa daõy con
taêng gaáp ñoâi Soá laàn taùch – troän trong thuaät
Soá laàn taùch – troän trong thuaät
taêng gaáp ñoâi
toaùn: log22n . n .
toaùn: log
Chi phí thöïc hieän taùch - troän tæ leä thuaän
Chi phí thöïc hieän taùch - troän tæ leä thuaän
vôùi n.
vôùi n.
Chi phí thöïc hieän cuûa giaûi thuaät MergeSort
Chi phí thöïc hieän cuûa giaûi thuaät MergeSort
laø O(nlog22n). n).
laø O(nlog Merge Sort – Ñaùnh giaù giaûi thuaät
Merge Sort – Ñaùnh giaù giaûi thuaät Moät nhöôïc ñieåm lôùn nöõa cuûa caùc thuaät toaùn troän
Moät nhöôïc ñieåm lôùn nöõa cuûa caùc thuaät toaùn troän
laø khi caøi ñaët thuaät toaùn ñoøi hoûi theâm khoâng gian
laø khi caøi ñaët thuaät toaùn ñoøi hoûi theâm khoâng gian
boä nhôù ñeå löu caùc daõy phuï b, c.
boä nhôù ñeå löu caùc daõy phuï b, c.
Haïn cheá naøy khoù chaáp nhaän trong thöïc teá vì caùc
Haïn cheá naøy khoù chaáp nhaän trong thöïc teá vì caùc
daõy caàn saép xeáp thöôøng coù kích thöôùc lôùn.
daõy caàn saép xeáp thöôøng coù kích thöôùc lôùn.
Vì vaäy thuaät toaùn troän thöôøng ñöôïc duøng ñeå saép
Vì vaäy thuaät toaùn troän thöôøng ñöôïc duøng ñeå saép
xeáp caùc caáu truùc döõ lieäu khaùc phuø hôïp hôn nhö
xeáp caùc caáu truùc döõ lieäu khaùc phuø hôïp hôn nhö
danh saùch lieân keát hoaëc file.
danh saùch lieân keát hoaëc file. Saép xeáp theo phöông phaùp troän
Saép xeáp theo phöông phaùp troän
tröïc tieáp Thuaät toaùn troän töï nhieân
tröïc tieáp
Thuaät toaùn troän töï nhieân
Natural Merge sort
Natural Merge sort +
1 k k (cid:236) ˛ " £ < (cid:239) 1 (cid:237) - > Moät ñöôøng chaïy cuûa daõy soá a laø moät daõy con
Moät ñöôøng chaïy cuûa daõy soá a laø moät daõy con
khoâng giaûm cuûa cöïc ñaïi cuûa a. Nghóa laø, ñöôøng
khoâng giaûm cuûa cöïc ñaïi cuûa a. Nghóa laø, ñöôøng
chaïy r = (aii, a, ai+1i+1, …, a
, …, ajj) phaûi thoûa
) phaûi thoûa
chaïy r = (a
ñieàu kieän:
ñieàu kieän:
a
k
i
j
),[
a
i
a a
a
i
a j +
1 j (cid:239) Ví duï daõy (cid:238) Ví duï daõy 12, 2, 8, 5, 1, 6, 4, 15 coù theå coi
12, 2, 8, 5, 1, 6, 4, 15 coù theå coi
nhö goàm 5 ñöôøng chaïy (12); (2, 8); (5); (1,
nhö goàm 5 ñöôøng chaïy (12); (2, 8); (5); (1,
6); (4, 15).
6); (4, 15). Saép xeáp theo phöông phaùp troän
Saép xeáp theo phöông phaùp troän
tröïc tieáp Thuaät toaùn troän töï nhieân
tröïc tieáp
Thuaät toaùn troän töï nhieân
Natural Merge sort
Natural Merge sort Thuaät toaùn troän töï nhieân khaùc thuaät toaùn troän tröïc
Thuaät toaùn troän töï nhieân khaùc thuaät toaùn troän tröïc
tieáp ôû choã thay vì luoân cöùng nhaéc phaân hoaïch theo
tieáp ôû choã thay vì luoân cöùng nhaéc phaân hoaïch theo
daõy con coù chieàu daøi k, vieäc phaân hoaïch seõ theo
daõy con coù chieàu daøi k, vieäc phaân hoaïch seõ theo
ñôn vò laø ñöôøng chaïy. ta chæ caàn bieát soá ñöôøng
ñôn vò laø ñöôøng chaïy. ta chæ caàn bieát soá ñöôøng
chaïy cuûa a sau laàn phaân hoaïch cuoái cuøng laø coù theå
chaïy cuûa a sau laàn phaân hoaïch cuoái cuøng laø coù theå
bieát thôøi ñieåm döøng cuûa thuaät toaùn vì daõy ñaõ coù
bieát thôøi ñieåm döøng cuûa thuaät toaùn vì daõy ñaõ coù
thöù töï laø daõy chi coù moät ñöôøng chaïy.
thöù töï laø daõy chi coù moät ñöôøng chaïy. Saép xeáp theo phöông phaùp troän
Saép xeáp theo phöông phaùp troän
tröïc tieáp Thuaät toaùn troän töï nhieân
tröïc tieáp
Thuaät toaùn troän töï nhieân
Natural Merge sort
Natural Merge sort Böôùc 2 : Taùch daõy a thaønh 2 daõy b, c
, …, ann thaønh 2 daõy b, c Böôùc 1 : // Chuaån bò
Böôùc 1 : // Chuaån bò
r = 0; // r duøng ñeå ñeám soá döôøng chaïy
r = 0; // r duøng ñeå ñeám soá döôøng chaïy
Böôùc 2 : Taùch daõy a11, a, a22, …, a
theo nguyeân taéc luaân phieân töøng ñöôøng chaïy:
theo nguyeân taéc luaân phieân töøng ñöôøng chaïy:
Böôùc 2.1 :
Böôùc 2.1 : Phaân phoái cho b moät ñöôøng chaïy; r = r+1;
Phaân phoái cho b moät ñöôøng chaïy; r = r+1;
Neáu a coøn phaàn töû chöa phaân phoái
Neáu a coøn phaàn töû chöa phaân phoái Phaân phoái cho c moät ñöôøng chaïy; r =
Phaân phoái cho c moät ñöôøng chaïy; r =
r+1;
r+1;
Böôùc 2.2 :
Böôùc 2.2 : Neáu a coøn phaàn töû: quay laïi böôùc 2.1;
Neáu a coøn phaàn töû: quay laïi böôùc 2.1; Neáu r <= 2 thì trôû laïi böôùc 2; Ngöôïc laïi: Döøng. Böôùc 3 :
Böôùc 3 :
Troän töøng caëp ñöôøng chaïy cuûa 2 daõy b, c
Troän töøng caëp ñöôøng chaïy cuûa 2 daõy b, c
vaøo a.
vaøo a.
Böôùc 4 :
Böôùc 4 :
Neáu r <= 2 thì trôû laïi böôùc 2; Ngöôïc laïi: Döøng. Saép xeáp theo phöông phaùp
Saép xeáp theo phöông phaùp
Radix Sort
cô soá Radix Sort
cô soá Radix Sort laø moät thuaät toaùn tieáp caän theo moät
Radix Sort laø moät thuaät toaùn tieáp caän theo moät
höôùng hoaøn toaøn khaùc.
höôùng hoaøn toaøn khaùc.
Neáu nhö trong caùc thuaät toaùn khaùc, cô sôû ñeå saép
Neáu nhö trong caùc thuaät toaùn khaùc, cô sôû ñeå saép
xeáp luoân laø vieäc so saùnh giaù trò cuûa 2 phaàn töû thì
xeáp luoân laø vieäc so saùnh giaù trò cuûa 2 phaàn töû thì
Radix Sort laïi döïa treân nguyeân taéc phaân loaïi thö cuûa
Radix Sort laïi döïa treân nguyeân taéc phaân loaïi thö cuûa
böu ñieän. Vì lyù do ñoù Radix Sort coøn coù teân laø
böu ñieän. Vì lyù do ñoù Radix Sort coøn coù teân laø
Postman’s sort.
Postman’s sort.
Radix Sort khoâng heà quan taâm ñeán vieäc so saùnh giaù
Radix Sort khoâng heà quan taâm ñeán vieäc so saùnh giaù
trò cuûa phaàn töû maø baûn thaân vieäc phaân loaïi vaø
trò cuûa phaàn töû maø baûn thaân vieäc phaân loaïi vaø
trình töï phaân loaïi seõ taïo ra thöù töï cho caùc phaàn töû.
trình töï phaân loaïi seõ taïo ra thöù töï cho caùc phaàn töû. Saép xeáp theo phöông phaùp
Saép xeáp theo phöông phaùp
Radix Sort
cô soá Radix Sort
cô soá Ñeå chuyeån moät khoái löôïng thö lôùn ñeán tay ngöôøi
Ñeå chuyeån moät khoái löôïng thö lôùn ñeán tay ngöôøi
nhaän ôû nhieàu ñòa phöông khaùc nhau, böu ñieän
nhaän ôû nhieàu ñòa phöông khaùc nhau, böu ñieän
thöôøng toå chöùc moät heä thoáng phaân loaïi thö phaân
thöôøng toå chöùc moät heä thoáng phaân loaïi thö phaân
caáp.
caáp.
Tröôùc tieân, caùc thö ñeán cuøng moät tænh, thaønh phoá
Tröôùc tieân, caùc thö ñeán cuøng moät tænh, thaønh phoá
seõ ñöôïc saép chung vaøo moät loâ ñeå göûi ñeán tænh
seõ ñöôïc saép chung vaøo moät loâ ñeå göûi ñeán tænh
thaønh töông öùng.
thaønh töông öùng.
Böu ñieän caùc tænh thaønh naøy laïi thöïc hieän coâng
Böu ñieän caùc tænh thaønh naøy laïi thöïc hieän coâng
vieäc töông töï. Caùc thö ñeán cuøng moät quaän, huyeän
vieäc töông töï. Caùc thö ñeán cuøng moät quaän, huyeän
seõ ñöôïc xeáp vaøo chung moät loâ vaø göûi ñeán quaän,
seõ ñöôïc xeáp vaøo chung moät loâ vaø göûi ñeán quaän,
huyeän töông öùng.
huyeän töông öùng.
Cöù nhö vaäy, caùc böùc thö seõ ñöôïc trao ñeán tay ngöôøi
Cöù nhö vaäy, caùc böùc thö seõ ñöôïc trao ñeán tay ngöôøi
nhaän moät caùch coù heä thoáng maø coâng vieäc saép
nhaän moät caùch coù heä thoáng maø coâng vieäc saép
xeáp thö khoâng quaù naëng nhoïc.
xeáp thö khoâng quaù naëng nhoïc. Saép xeáp theo phöông phaùp
Saép xeáp theo phöông phaùp
Radix Sort
cô soá Radix Sort
cô soá Moâ phoûng laïi qui trình treân, ñeå saép xeáp daõy a Moâ phoûng laïi qui trình treân, ñeå saép xeáp daõy a11, ,
, giaûi thuaät Radix Sort thöïc hieän
, ..., ann, giaûi thuaät Radix Sort thöïc hieän
aa22, ..., a
nhö sau:
nhö sau:
Tröôùc tieân, ta coù theå giaû söû moãi
Tröôùc tieân, ta coù theå giaû söû moãi
laø moät
, ..., ann laø moät
trong daõy a11, a, a22, ..., a
phaàn töû aii trong daõy a
phaàn töû a
soá nguyeân coù toái ña m chöõ soá.
soá nguyeân coù toái ña m chöõ soá.
Ta phaân loaïi caùc phaàn töû laàn löôït theo
Ta phaân loaïi caùc phaàn töû laàn löôït theo
caùc chöõ soá haøng ñôn vò, haøng chuïc,
caùc chöõ soá haøng ñôn vò, haøng chuïc,
haøng traêm, … töông töï vieäc phaân loaïi
haøng traêm, … töông töï vieäc phaân loaïi
thö theo tænh thaønh, quaän huyeän,
thö theo tænh thaønh, quaän huyeän,
phöôøng xaõ, ….
phöôøng xaõ, …. Saép xeáp theo phöông phaùp
Saép xeáp theo phöông phaùp
Radix Sort
cô soá Radix Sort
cô soá // k = 0: haøng ñôn vò; k = 1: haøng chuïc; …
// k = 0: haøng ñôn vò; k = 1: haøng chuïc; … Böôùc 1 :// k cho bieát chöõ soá duøng ñeå phaân loaïi
Böôùc 1 :// k cho bieát chöõ soá duøng ñeå phaân loaïi
hieän haønh
hieän haønh
k = 0;
k = 0;
Böôùc 2 : //Taïo caùc loâ chöùa caùc loaïi phaàn töû khaùc
Böôùc 2 : //Taïo caùc loâ chöùa caùc loaïi phaàn töû khaùc
nhaunhau
Khôûi taïo 10 loâ B
Böôùc 3 :
Böôùc 3 :
For i = 1 .. n do
For i = 1 .. n do Khôûi taïo 10 loâ B00, B, B11, …, B roãng;
, …, B99 roãng; vôùi t: chöõ soá thöù k
vaøo loâ Btt vôùi t: chöõ soá thöù k Böôùc 3 :
Böôùc 3 :
Noái B Ñaët aii vaøo loâ B
Ñaët a
cuûa aii;;
cuûa a laïi (theo ñuùng trình töï)
, …, B99 laïi (theo ñuùng trình töï) Noái B00, B, B11, …, B
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
thaønh a.
thaønh a. Böôùc 4 : Böôùc 4 : k = k+1;Neáu k < m thì trôû laïi böôùc 2. k = k+1;Neáu k < m thì trôû laïi böôùc 2. Ngöôïc laïi: Döøng Ngöôïc laïi: Döøng Saép xeáp theo phöông phaùp
Saép xeáp theo phöông phaùp
Radix Sort
cô soá Radix Sort
cô soá Saép xeáp theo phöông phaùp
Saép xeáp theo phöông phaùp
Radix Sort
cô soá Radix Sort
cô soá Saép xeáp theo phöông phaùp
Saép xeáp theo phöông phaùp
Radix Sort
cô soá Radix Sort
cô soá Saép xeáp theo phöông phaùp
Saép xeáp theo phöông phaùp
Radix Sort
cô soá Radix Sort
cô soá Saép xeáp theo phöông phaùp
Saép xeáp theo phöông phaùp
Radix Sort
cô soá Radix Sort
cô soá Saép xeáp theo phöông phaùp
Saép xeáp theo phöông phaùp
Radix Sort
cô soá Radix Sort
cô soá Ñaùnh giaù giaûi thuaät:
Ñaùnh giaù giaûi thuaät:
Vôùi moät daõy n soá, moãi soá coù toái ña m chöõ soá,
Vôùi moät daõy n soá, moãi soá coù toái ña m chöõ soá,
thuaät toaùn thöïc hieän m laàn caùc thao taùc phaân loâ
thuaät toaùn thöïc hieän m laàn caùc thao taùc phaân loâ
vaø gheùp loâ.
vaø gheùp loâ.
Trong thao taùc phaân loâ, moãi phaàn töû chæ ñöôïc
Trong thao taùc phaân loâ, moãi phaàn töû chæ ñöôïc
xeùt ñuùng moät laàn, khi gheùp cuõng vaäy.
xeùt ñuùng moät laàn, khi gheùp cuõng vaäy.
Nhö vaäy, chi phí cho vieäc thöïc hieän thuaät toaùn
Nhö vaäy, chi phí cho vieäc thöïc hieän thuaät toaùn
hieån nhieân laø O(2mn) = O(n).
hieån nhieân laø O(2mn) = O(n). fi thöïc teá). thöïc teá). (cid:222) Th o lu n
Th o lu n ả
ả ậ
ậCaáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
11
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
12
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
13
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
14
Nhaän xeùt:
Nhaän xeùt:
Giaûi thuaät tìm tuyeán tính khoâng phuï thuoäc vaøo
Giaûi thuaät tìm tuyeán tính khoâng phuï thuoäc vaøo
thöù töï cuûa caùc phaàn töû trong danh saùch, do vaäy
thöù töï cuûa caùc phaàn töû trong danh saùch, do vaäy
ñaây laø phöông phaùp toång quaùt nhaát ñeå tìm kieám
ñaây laø phöông phaùp toång quaùt nhaát ñeå tìm kieám
treân moät danh saùch baát kyø.
treân moät danh saùch baát kyø.
Moät thuaät toaùn coù theå ñöôïc caøi ñaët theo nhieàu
Moät thuaät toaùn coù theå ñöôïc caøi ñaët theo nhieàu
caùch khaùc nhau, kyõ thuaät caøi ñaët aûnh höôûng
caùch khaùc nhau, kyõ thuaät caøi ñaët aûnh höôûng
ñeán toác ñoä thöïc hieän cuûa thuaät toaùn.
ñeán toác ñoä thöïc hieän cuûa thuaät toaùn.
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
15
Tìm kieám nhò
Tìm kieám nhò
phaân
phaân
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
17
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
18
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
19
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
20
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
21
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
22
int BinarySearch(int a[],int N,int x )
{
int left =0, right = N-1, midle;
while (left <= right)
{
mid = (left + right)/2;
if (x == a[midle])
return midle;//Tìm thaáy x taïi mid
if (x
}
return -1; // trong daõy khoâng coù x
}
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
23
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
24
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
25
Nhaän xeùt:
Nhaän xeùt:
Khi muoán aùp duïng giaûi thuaät tìm nhò phaân caàn
Khi muoán aùp duïng giaûi thuaät tìm nhò phaân caàn
phaûi xeùt ñeán thôøi gian saép xeáp daõy soá ñeå thoûa
phaûi xeùt ñeán thôøi gian saép xeáp daõy soá ñeå thoûa
ñieàu kieän daõy soá coù thöù töï. Thôøi gian naøy
ñieàu kieän daõy soá coù thöù töï. Thôøi gian naøy
khoâng nhoû, vaø khi daõy soá bieán ñoäng caàn phaûi
khoâng nhoû, vaø khi daõy soá bieán ñoäng caàn phaûi
tieán haønh saép xeáp laïi => khuyeát ñieåm chính cho
tieán haønh saép xeáp laïi => khuyeát ñieåm chính cho
giaûi thuaät tìm nhò phaân.
giaûi thuaät tìm nhò phaân.
Caàn caân nhaéc nhu caàu thöïc teá ñeå choïn moät
Caàn caân nhaéc nhu caàu thöïc teá ñeå choïn moät
trong hai giaûi thuaät tìm kieám treân sao cho coù lôïi
trong hai giaûi thuaät tìm kieám treân sao cho coù lôïi
nhaát.
nhaát.
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
26
Caùc giaûi thuaät
Caùc giaûi thuaät
Saép xeáp noäi
Saép xeáp noäi
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
28
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
29
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
30
Phöông phaùp
Phöông phaùp
choïn tröïc tieáp
choïn tröïc tieáp
Selection sort
Selection sort
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
32
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
33
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
34
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
35
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
36
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
37
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
38
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
39
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
40
void SelectionSort(int a[],int N )
{
int min; // chæ soá phaàn töû nhoû nhaát trong daõy hieän haønh
for (int i=0; i
min = i;
for(int j = i+1; j < N ; j++)
if (a[j] < a[min])
min = j; // ghi nhaän vò trí phaàn töû nhoû nhaát
if (min != i)
Swap(a[min], a[i]);
}
}
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
41
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
42
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
43
Phöông phaùp
Phöông phaùp
Cheøn tröïc tieáp
Cheøn tröïc tieáp
Insertion Sort
Insertion Sort
pos-1 £
Vò trí naøy chính laø pos thoûa aapos-1
45
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
46
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
47
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
48
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
49
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
50
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
51
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
52
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
53
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
54
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
55
Insertion Sort – Caøi ñaët
Insertion Sort – Caøi ñaët
void InsertionSort(int a[], int N )
{
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
56
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
57
BInsertionSort(int a[], int N )
void
{ int l,r,m,i;
int x;//löu tröõ giaù trò a[i] traùnh bò ghi ñeø khi dôøi choã caùc phaàn
töû.
for(int i=1 ; i
x = a[i]; l = 1; r = i-1;
while(i<=r)
{ m = (l+r)/2;
if(x < a[m]) r = m-1;
else l = m+1;
}
for(int j = i ; j >l ; j--)
a[j] = a[j-1];
a[l] = x;
}
}
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
58
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
59
Phöông phaùp
Phöông phaùp
ñoåi choã tröïc
ñoåi choã tröïc
tieáp
tieáp
Interchange Sort
Interchange Sort
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
61
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
62
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
63
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
64
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
65
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
66
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
67
void InterchangeSort(int a[], int N)
{
int i, j;
for (i = 0 ; i
for (j =i+1; j < N ; j++)
if(a[j]< a[i]) //neáu coù nghòch theá thì ñoåi choã
Swap(a[i],a[j]);
}
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
68
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
69
Phöông phaùp
Phöông phaùp
noåi boït
noåi boït
Bubble sort
Bubble sort
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
71
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
72
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
73
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
74
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
75
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
76
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
77
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
78
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
79
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
80
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
81
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
82
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
83
84
//loaïi bôùt caùc phaàn töû ñaõ coù thöù töï ôû
l = k; //loaïi bôùt caùc phaàn töû ñaõ coù thöù töï ôû
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
l = k;
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
85
Saép xeáp caây
Saép xeáp caây
Heap Sort
Heap Sort
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
87
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
88
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
89
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
90
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
91
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
92
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
93
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
94
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
95
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
96
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
97
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
98
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
99
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
100
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
101
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
102
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
103
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
104
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
105
106
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
107
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
108
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
109
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
110
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
111
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
112
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
113
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
114
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
115
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
116
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
117
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
118
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
119
void Shift (int a[], int left, int right)
{
int x, curr, joint;
curr = left; joint =2*curr+1;// ajoint: phaàn töû lieân ñôùi
x = a[curr];
while (joint <= right)
{
if (joint < right) // neáu coù ñuû 2 phaàn töû lieân
if (a[joint] < a[joint+1])
joint = joint+1;
if (a[joint]
a[curr] = a[joint];
curr = joint; // xeùt tieáp khaû naêng hieäu chænh lan
joint = 2*curr+1;
}
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
120
a[curr] = x;
}
void CreateHeap(int a[], int N)
{
int left;
ị
ầ
//left: v trí ph n t c n ghép thêm
for (left = (N-1)/2; left >= 0; left --)
Shift(a, left, N-1);
}
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
121
void HeapSort (int a[], int N)
{
int right;
CreateHeap(a, N); //saép xeáp daõy a thanh heap
right = N-1; // right laø vò trí ñuùng cho phaàn töû lôùn nhaát
while (right > 0) do
{
Swap(a[0],a[right]);
right --;
Shift(a,0,right);
}
}
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
122
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
123
Saép xeáp cheøn
Saép xeáp cheøn
vôùi ñoä daøi
vôùi ñoä daøi
böôùc giaûm daàn
böôùc giaûm daàn
Shell Sort
Shell Sort
len+1 a a2len+1
...
2len+2 ...
ShellSort laø moät phöông phaùp caûi tieán cuûa phöông
ShellSort laø moät phöông phaùp caûi tieán cuûa phöông
phaùp saép xeáp cheøn tröïc tieáp. YÙ töôûng cuûa phöông
phaùp saép xeáp cheøn tröïc tieáp. YÙ töôûng cuûa phöông
phaùp saép xeáp naøy laø xem xeùt daõy ban ñaàu nhö nhöõng
phaùp saép xeáp naøy laø xem xeùt daõy ban ñaàu nhö nhöõng
daõy con goàm caùc phaàn töû ôû caùch nhau len vò trí; tieán
daõy con goàm caùc phaàn töû ôû caùch nhau len vò trí; tieán
haønh saép xeáp treân töøng daõy con; giaûm daàn böôùc len
haønh saép xeáp treân töøng daõy con; giaûm daàn böôùc len
ñeán khi len = 1 saép xeáp xong:
saép xeáp xong:
ñeán khi len = 1
Daõy ban ñaàu : a11, a, a22, ..., a
Daõy ban ñaàu : a
keõ cuûa caùc daõy con sau :
keõ cuûa caùc daõy con sau :
Daõy con thöù nhaát : a a11 a alen+1
Daõy con thöù nhaát :
len+2 a a2len+2
Daõy con thöù hai : a a22 a alen+2
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
125
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
126
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
127
h = (5, 3, 1); k = 3
len = 5;
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
128
h = (5, 3, 1); k = 3
len = 5;
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
129
h = (5, 3, 1); k = 3
len = 3
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
130
h = (5, 3, 1); k = 3
len = 3
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
131
h = (5, 3, 1); k = 3
len = 3
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
132
h = (5, 3, 1); k = 3
len = 1
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
133
h = (5, 3, 1); k = 3
len = 1
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
134
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
135
Shell sort – Caøi ñaët
Shell sort – Caøi ñaët
int h[MAXK], k;
void ShellSort(int a[], int N)
{
int step, i, pos, x, len;
for (step = 0 ; step
len = h[step]; //khoaûng caùch 2 phaàn töû lieân tieáp cuûa daõy
for (i = len; i
a[pos] = a[pos-len];
a[pos] = x;
}
}
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
136
}
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
137
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
138
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
139
Saép xeáp döïa
Saép xeáp döïa
treân phaân
treân phaân
hoaïch
hoaïch
Quick sort
Quick sort
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
141
142
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
143
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
144
145
Hoaùn vò (a[i],a[j]);
Hoaùn vò (a[i],a[j]);
Böôùc 25: Neáu i < j:
Böôùc 25: Neáu i < j:
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
xeùt heát maûng
xeùt heát maûng
Phaân hoaïch
daõy
STOP
STOP
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
146
Phaân hoaïch
daõy
STOP
STOP
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
147
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
148
Phaân hoaïch
daõy
6
STOP
STOP
Saép xeáp ñoaïn
3
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
149
Saép xeáp ñoaïn
3
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
150
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
151
void QuickSort(int a[], int left, int right)
{
int i, j, x;
if (left ‡ right)
return;
x = a[(left+right)/2]; // choïn phaàn töû giöõa laøm giaù trò
i = left; j = right;
while(i < j) {
while(a[i] < x) i++;
while(a[j] > x) j--;
if(i <= j) {
Swap(a[i], a[j]);
i++ ; j--;
}
}
QuickSort(a, left, j);
QuickSort(a, i, right);
}
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
152
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
153
Quick sort – Ñaùnh giaù giaûi
Quick sort – Ñaùnh giaù giaûi
thuaät
thuaät
Nhaän xeùt:
Nhaän xeùt:
Veà nguyeân taéc, coù theå choïn giaù trò moác x laø moät
Veà nguyeân taéc, coù theå choïn giaù trò moác x laø moät
phaàn töû tuøy yù trong daõy, nhöng ñeå ñôn giaûn, phaàn töû
phaàn töû tuøy yù trong daõy, nhöng ñeå ñôn giaûn, phaàn töû
coù vò trí giöõa thöôøng ñöôïc choïn, khi ñoù p = (l +r)/ 2.
coù vò trí giöõa thöôøng ñöôïc choïn, khi ñoù p = (l +r)/ 2.
Giaù trò moác x ñöôïc choïn seõ coù taùc ñoäng ñeán hieäu
Giaù trò moác x ñöôïc choïn seõ coù taùc ñoäng ñeán hieäu
quaû thöïc hieän thuaät toaùn vì noù quyeát ñònh soá laàn
quaû thöïc hieän thuaät toaùn vì noù quyeát ñònh soá laàn
phaân hoaïch.
phaân hoaïch.
Soá laàn phaân hoaïch seõ ít nhaát neáu ta choïn ñöôïc x laø
Soá laàn phaân hoaïch seõ ít nhaát neáu ta choïn ñöôïc x laø
phaàn töû trung vò (median), nhieàu nhaát neáu x laø cöïc
phaàn töû trung vò (median), nhieàu nhaát neáu x laø cöïc
trò cuûa daõy.
trò cuûa daõy.
Tuy nhieân do chi phí xaùc ñònh phaàn töû median quaù
Tuy nhieân do chi phí xaùc ñònh phaàn töû median quaù
cao neân trong thöïc teá ngöôøi ta khoâng choïn phaàn töû
cao neân trong thöïc teá ngöôøi ta khoâng choïn phaàn töû
naøy maø choïn phaàn töû naèm chính giöõa daõy laøm
naøy maø choïn phaàn töû naèm chính giöõa daõy laøm
moác vôùi hy voïng noù coù theå gaàn vôùi giaù trò
moác vôùi hy voïng noù coù theå gaàn vôùi giaù trò
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
154
Ñoä phöùc taïp thuaät toaùn:
Ñoä phöùc taïp thuaät toaùn:
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
155
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
157
Laøm giaûm soá daõy con:
Laøm giaûm soá daõy con:
Caùc daõy con taêng daàn seõ ñöôïc taùch ra 2 daõy phuï theo
Caùc daõy con taêng daàn seõ ñöôïc taùch ra 2 daõy phuï theo
phaân phoái ñeàu luaân phieân. .
nguyeân taéc phaân phoái ñeàu luaân phieân
nguyeân taéc
Troän töøng caëp daõy con cuûa hai daõy phuï thaønh moät
Troän töøng caëp daõy con cuûa hai daõy phuï thaønh moät
daõy con cuûa daõy ban ñaàu daõy môùi coù soá löôïng
daõy môùi coù soá löôïng
daõy con cuûa daõy ban ñaàu
daõy con giaûm ñi so vôùi daõy ban ñaàu.
daõy con giaûm ñi so vôùi daõy ban ñaàu.
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
158
159
//b = a11, …, a
//b = a
//c = ak+1k+1, …, a
//c = a
Böôùc 22:
Böôùc 22: Troän
phaàn töû cuûa 2 daõy b, c vaøo a.
phaàn töû cuûa 2 daõy b, c vaøo a.
Böôùc 23: k = k*2;
Böôùc 23: k = k*2;
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
//Heát laëp
//Heát laëp
k = 1;
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
160
k = 1;
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
161
k = 1;
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
162
k = 1;
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
163
k = 2;
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
164
k = 2;
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
165
k = 2;
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
166
k = 4;
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
167
k = 4;
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
168
k = 4;
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
169
k = 8;
STOP
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
170
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
171
Merge Sort – Caøi ñaët
Merge Sort – Caøi ñaët
Döõ lieäu hoã trôï: 2 maûng b, c:
Döõ lieäu hoã trôï: 2 maûng b, c:
int b[MAX], c[MAX], nb, nc;
Caùc haøm caàn caøi ñaët:
Caùc haøm caàn caøi ñaët:
MergeSort: Saép xeáp maûng (a, N) taêng daàn
: Saép xeáp maûng (a, N) taêng daàn
void MergeSort(int a[], int N);
void Distribute(int a[], int N,
int &nb, int &nc, int k);
Merge: Troän maûng b vaø maûng c vaøo maûng a
: Troän maûng b vaø maûng c vaøo maûng a
void Merge(int a[], int nb, int nc, int k);
MergeSubarr: Troän 1 caëp daõy con töø b vaø c vaøo a
: Troän 1 caëp daõy con töø b vaø c vaøo a
void MergeSubarr(int a[], int nb, int nc,
int &pa, int &pb, int &pc, int k);
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
172
void MergeSort(int a[], int N)
{
int k;
for (k = 1; k < N; k *= 2)
{
Distribute(a, N, nb, nc, k);
Merge(a, nb, nc, k);
}
}
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
173
Merge sort – Caøi ñaët
Merge sort – Caøi ñaët
a[], int
void Distribute(int
N,
int &nb, int &nc, int k)
{
int i, pa, pb, pc;
pa = pb = pc = 0;
while (pa < N)
{
for (i=0; (pa
b[pb] = a[pa];
for (i=0; (pa
c[pc] = a[pa];
}
nb = pb; nc = pc;
}
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
174
void Merge(int a[], int nb, int nc, int k)
{
int pa, pb, pc;
pa = pb = pc = 0;
while ((pb < nb) && (pc < nc))
MergeSubarr(a, nb, nc, pa, pb, pc, k);
while (pb < nb)
a[pa ++] = b[pb ++];
while (pc < nc)
a[pa ++] = c[pc ++];
}
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
175
void MergeSubarr(int a[], int nb, int nc,
int &pa, int &pb, int &pc, int k)
{
int rb, rc;
rb = min(nb, pb+k); rc = min(nc, pb+k);
while ((pb < rb) && (pc < rc))
a[pa ++] = b[pb ++];
else a[pa ++] = c[pc ++];
while (pb < rb)
a[pa ++] = b[pb ++];
while (pc < rc)
a[pa ++] = c[pc ++];
}
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
176
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
177
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
178
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
179
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
180
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
181
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
182
Saép xeáp theo
Saép xeáp theo
phöông phaùp cô
phöông phaùp cô
Radix Sort
soá Radix Sort
soá
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
184
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
185
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
186
187
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
188
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
189
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
190
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
191
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
192
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
193
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
194
Saép xeáp theo phöông phaùp
Saép xeáp theo phöông phaùp
Radix Sort
cô soá Radix Sort
cô soá
Nhaän xeùt:
Nhaän xeùt:
Sau laàn phaân phoái thöù k caùc phaàn töû cuûa A vaøo
Sau laàn phaân phoái thöù k caùc phaàn töû cuûa A vaøo
, vaø laáy ngöôïc trôû ra,
, …, B99, vaø laáy ngöôïc trôû ra,
caùc loâ B00, B, B11, …, B
caùc loâ B
neáu chæ xeùt ñeán k+1 chöõ soá cuûa
neáu chæ xeùt ñeán k+1 chöõ soá cuûa
caùc phaàn töû trong A, ta seõ coù moät
caùc phaàn töû trong A, ta seõ coù moät
maûng taêng daàn nhôø trình töï laáy ra töø
maûng taêng daàn nhôø trình töï laáy ra töø
0 0 fi
9. Nhaän xeùt naøy baûo ñaûm tính
9. Nhaän xeùt naøy baûo ñaûm tính
ñuùng ñaén cuûa thuaät toaùn.
ñuùng ñaén cuûa thuaät toaùn.
Thuaät toaùn coù ñoä phöùc taïp tuyeán tính
Thuaät toaùn coù ñoä phöùc taïp tuyeán tính
neân hieäu quaû khi saép daõy coá raát
neân hieäu quaû khi saép daõy coá raát
nhieàu phaàn töû, nhaát laø khi khoùa saép
nhieàu phaàn töû, nhaát laø khi khoùa saép
xeáp khoâng quaù daøi so vôùi soá löôïng
xeáp khoâng quaù daøi so vôùi soá löôïng
phaàn töû (ñieàu naøy thöôøng gaëp trong
phaàn töû (ñieàu naøy thöôøng gaëp trong
Saép xeáp theo phöông phaùp
Saép xeáp theo phöông phaùp
Radix Sort
cô soá Radix Sort
cô soá
Nhaän xeùt:
Nhaän xeùt:
Thuaät toaùn khoâng coù tröôøng hôïp xaáu nhaát vaø
Thuaät toaùn khoâng coù tröôøng hôïp xaáu nhaát vaø
toát nhaát. Moïi daõy soá ñeàu ñöôïc saép vôùi chi phí
toát nhaát. Moïi daõy soá ñeàu ñöôïc saép vôùi chi phí
nhö nhau neáu chuùng coù cuøng soá phaàn töû vaø
nhö nhau neáu chuùng coù cuøng soá phaàn töû vaø
caùc khoùa coù cuøng chieàu daøi.
caùc khoùa coù cuøng chieàu daøi.
Thuaät toaùn caøi ñaët thuaän tieän vôùi caùc maûng
Thuaät toaùn caøi ñaët thuaän tieän vôùi caùc maûng
vôùi khoùa saép xeáp laø chuoãi (kyù töï hay soá) hôn
vôùi khoùa saép xeáp laø chuoãi (kyù töï hay soá) hôn
laø khoùa soá nhö trong ví duï do traùnh ñöôïc chi phí
laø khoùa soá nhö trong ví duï do traùnh ñöôïc chi phí
laáy caùc chöõ soá cuûa töøng soá.
laáy caùc chöõ soá cuûa töøng soá.
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
195
Saép xeáp theo phöông phaùp
Saép xeáp theo phöông phaùp
Radix Sort
cô soá Radix Sort
cô soá
Nhaän xeùt:
Nhaän xeùt:
Soá löôïng loâ lôùn (10 khi duøng soá thaäp phaân, 26
Soá löôïng loâ lôùn (10 khi duøng soá thaäp phaân, 26
khi duøng chuoãi kyù töï tieáng Anh, …) nhöng toång
khi duøng chuoãi kyù töï tieáng Anh, …) nhöng toång
kích thöôùc cuûa taát caû caùc loâ chæ baèng daõy ban
kích thöôùc cuûa taát caû caùc loâ chæ baèng daõy ban
ñaàu neân ta khoâng theå duøng maûng ñeå bieåu dieãn
ñaàu neân ta khoâng theå duøng maûng ñeå bieåu dieãn
B. Nhö vaäy, phaûi duøng caáu truùc döõ lieäu ñoäng
B. Nhö vaäy, phaûi duøng caáu truùc döõ lieäu ñoäng
ñeå bieåu dieãn B (cid:222)
Radix Sort raát thích hôïp cho saép
Radix Sort raát thích hôïp cho saép
ñeå bieåu dieãn B
xeáp treân danh saùch lieân keát.
xeáp treân danh saùch lieân keát.
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
196
Saép xeáp theo phöông phaùp
Saép xeáp theo phöông phaùp
Radix Sort
cô soá Radix Sort
cô soá
Nhaän xeùt:
Nhaän xeùt:
Ngöôøi ta cuõng duøng phöông phaùp phaân loâ theo
Ngöôøi ta cuõng duøng phöông phaùp phaân loâ theo
bieåu dieãn nhò phaân cuûa khoùa saép xeáp. Khi ñoù ta
bieåu dieãn nhò phaân cuûa khoùa saép xeáp. Khi ñoù ta
coù theå duøng hoaøn toaøn caáu truùc döõ lieäu maûng
coù theå duøng hoaøn toaøn caáu truùc döõ lieäu maûng
vaø
ñeå bieåu dieãn B vì chæ caàn duøng hai loâ B00 vaø
ñeå bieåu dieãn B vì chæ caàn duøng hai loâ B
BB11. Tuy nhieân, khi ñoù chieàu daøi khoùa
. Tuy nhieân, khi ñoù chieàu daøi khoùa
seõ lôùn. Khi saép caùc daõy khoâng nhieàu
seõ lôùn. Khi saép caùc daõy khoâng nhieàu
phaàn töû, thuaät toaùn Radix sort seõ maát
phaàn töû, thuaät toaùn Radix sort seõ maát
öu theá so vôùi caùc thuaät toaùn khaùc.
öu theá so vôùi caùc thuaät toaùn khaùc.
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
197
Caáu truùc Döõ lieäu - Tìm kieám vaø Saép xeáp
198
