Tìm hiểu tầm quan trọng của cấu trúc dữ liệu và giải thụât trong một đề án tin học phần 2

Dãy con thứ hai (giữa dãy M) gồm các phần tử có giá trị bằng giá trị trung bình của dãy M, Dãy con thứ ba (cuối dãy M) gồm các phần tử có giá trị lớn hơn giá trị trung bình của dãy M, + Nếu dãy con thứ nhất và dãy con thứ ba có nhiều hơn 01 phần tử thì chúng ta lại tiếp tục phân hoạch đệ quy các dãy con này.
Nội dung trích xuất từ tài liệu:
Tìm hiểu tầm quan trọng của cấu trúc dữ liệu và giải thụât trong một đề án tin học phần 2 Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät 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: Trang: 24 Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät 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 Giaùo trình: Caáu Truùc Döõ Lieäu vaø Giaûi Thuaät I X = 15 JM: 45 55 25 20 15 5 25 30 10 3 I X = 15 JM: 3 55 25 20 15 5 25 30 10 45 I X = 15 JM: 3 10 25 20 15 5 25 30 55 45 I X = 15M: 3 10 5 20 15 25 25 30 55 45 J First X = 15 I LastM: 3 10 5 15 20 25 25 30 55 45 JPhaân hoaïch caùc phaàn töû trong daõy con töø First -> J:First = 1 Last = J = 4 X = M[(1+4)/2] = M[2] = 10 First X = 10 LastM: 3 10 5 15 20 25 25 30 55 4 ...