Tìm hiểu tầm quan trọng của cấu trúc dữ liệu trong giải thuật phần 2 ppt

Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät

Trang: 24

Daõy con thöù hai (giöõa daõy M) goàm caùc phaàn töû coù giaù trò baèng giaù trò trung bình

cuûa daõy M,

Daõy con thöù ba (cuoái daõy M) goàm caùc phaàn töû coù giaù trò lôùn hôn giaù trò trung bình

cuûa daõy M,

+ Neáu daõy con thöù nhaát vaø daõy con thöù ba coù nhieàu hôn 01 phaàn töû thì chuùng ta laïi

tieáp tuïc phaân hoaïch ñeä quy caùc daõy con naøy.

+ Vieäc tìm giaù trò trung bình cuûa daõy M hoaëc tìm kieám phaàn töû trong M coù giaù trò baèng

giaù trò trung bình cuûa daõy M raát khoù khaên vaø maát thôøi gian. Trong thöïc teá, chuùng

ta choïn moät phaàn töû baát kyø (thöôøng laø phaàn töû ñöùng ôû vò trí giöõa) trong daõy caùc

phaàn töû caàn phaân hoaïch ñeå laøm giaù trò cho caùc phaàn töû cuûa daõy con thöù hai (daõy

giöõa) sau khi phaân hoaïch. Phaàn töû naøy coøn ñöôïc goïi laø phaàn töû bieân (boundary

element). Caùc phaàn töû trong daõy con thöù nhaát seõ coù giaù trò nhoû hôn giaù trò phaàn töû

bieân vaø caùc phaàn töû trong daõy con thöù ba seõ coù giaù trò lôùn hôn giaù trò phaàn töû bieân.

+ Vieäc phaân hoaïch moät daõy ñöôïc thöïc hieän baèng caùch tìm caùc caëp phaàn töû ñöùng ôû

hai daõy con hai beân phaàn töû giöõa (daõy 1 vaø daõy 3) nhöng bò sai thöù töï (phaàn töû

ñöùng ôû daõy 1 coù giaù trò lôùn hôn giaù trò phaàn töû giöõa vaø phaàn töû ñöùng ôû daõy 3 coù

giaù trò nhoû hôn giaù trò phaàn töû giöõa) ñeå ñoåi choã (hoaùn vò) cho nhau.

- Thuaät toaùn:

B1: First = 1

B2: Last = N

B3: IF (First ≥ Last) //Daõy con chæ coøn khoâng quaù 01 phaàn töû

Thöïc hieän Bkt

B4: X = M[(First+Last)/2] //Laáy giaù trò phaàn töû giöõa

B5: I = First //Xuaát phaùt töø ñaàu daõy 1 ñeå tìm phaàn töû coù giaù trò > X

B6: IF (M[I] > X)

Thöïc hieän B8

B7: ELSE

B7.1: I++

B7.2: Laëp laïi B6

B8: J = Last //Xuaát phaùt töø cuoái daõy 3 ñeå tìm phaàn töû coù giaù trò < X

B9: IF (M[J] < X)

Thöïc hieän B11

B10: ELSE

B10.1: J--

B10.2: Laëp laïi B9

B11: IF (I ≤ J)

B11.1: Hoaùn_Vò(M[I], M[J])

B11.2: I++

B11.3: J--

B11.4: Laëp laïi B6

B12: ELSE

B12.1: Phaân hoaïch ñeä quy daõy con töø phaàn töû thöù First ñeán phaàn töû thöù J

B12.2: Phaân hoaïch ñeä quy daõy con töø phaàn töû thöù I ñeán phaàn töû thöù Last

Bkt: Keát thuùc

- Caøi ñaët thuaät toaùn:

Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät

Trang: 25

Haøm QuickSort coù prototype nhö sau:

void QuickSort(T M[], int N);

Haøm thöïc hieän vieäc saép xeáp N phaàn töû coù kieåu döõ lieäu T treân maûng M theo thöù töï

taêng döïa treân thuaät toaùn saép xeáp nhanh. Haøm QuickSort söû duïng haøm phaân hoaïch ñeä

quy PartitionSort ñeå thöïc hieän vieäc saép xeáp theo thöù töï taêng caùc phaàn töû cuûa moät daõy

con giôùi haïn töø phaàn töû thöù First ñeán phaàn töû thöù Last treân maûng M. Haøm

PartitionSort coù prototype nhö sau:

void PartitionSort(T M[], int First, int Last);

Noäi dung cuûa caùc haøm nhö sau:

void PartitionSort(T M[], int First, int Last)

{ if (First >= Last)

return;

T X = M[(First+Last)/2];

int I = First;

int J = Last;

do { while (M[I] < X)

I++;

while (M[J] > X)

J--;

if (I <= J)

{ Swap(M[I], M[J]);

I++;

J--;

}

}

while (I <= J);

PartitionSort(M, First, J);

PartitionSort(M, I, Last);

return;

}

//===========================================

void QuickSort(T M[], int N)

{ PartitionSort(M, 0, N-1);

return;

}

- Ví duï minh hoïa thuaät toaùn:

Giaû söû ta caàn saép xeáp maûng M coù 10 phaàn töû sau (N = 10):

M: 45 55 25 20 15 5 25 30 10 3

Ban ñaàu: First = 1 Last = 10 X = M[(1+10)/2] =M[5] = 15

First X = 15 Last

M: 45 55 25 20 15 5 25 30 10 3

Phaân hoaïch: