Kỹ thuật lập trình C Chương 7: Các thuật toán sắp xếp

[email protected] KỸ THUẬT LẬP TRÌNH C Chương 7: Các thuật toán sắp xếp 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Bài toán sắp xếp • Cho tập N phần tử, mỗi phần tử có một số thuộc tính • Dựa vào 1 (hoặc vài) thuộc tính của các phần tử ñể sắp xếp lại chúng theo trật tự mới. 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Bài toán sắp xếp • Gồm 2 bài toán con: – Dựa theo khoá sắp xếp định vị lại thứ tự các phần tử – Chuyển các phần tử cần sắp về vị trí mới. • Hai thao tác cơ bản – So sánh – Gán 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Các giải thuật sắp xếp • Sắp xếp đổi chỗ trực tiếp - Interchange Sort • Sắp xếp chọn trực tiếp – Selection Sort • Sắp xếp chèn trực tiếp – Insertion Sort • Sắp xếp nổi bọt – Buble Sort • Sắp xếp nổi bọt cải tiến - Shaker Sort • Shell sort • Heap sort • Quick sort • Merge sort 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Đổi chỗ trực tiếp – Interchange Sort • Khái niệm nghịch thế: – Xét một mảng các số a0, a1, . an. – Nếu có i aj, thì ta gọi đó là một nghịch thế. • Mảng chưa sắp xếp sẽ có nghịch thế • Mảng đã có thứ tự sẽ không chứa nghịch thế 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Đổi chỗ trực tiếp – Interchange Sort • Tìm tất cả nghịch thế, triệt tiêu chúng bằng cách hoán vị 2 phần tử tương ứng trong nghịch thế 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Đổi chỗ trực tiếp – Interchange Sort • Bước 1 : i = 1; // bắt đầu từ ñầu dãy • Bước 2 : j = i+1; //tìm các phần tử a[j] i • Bước 3 : Trong khi j < N thực hiện Nếu a[j]<a[i] //xét cặp a[i], a[j] Doicho(a[i],a[j]); j = j+1; • Bước 4 : i = i+1; Nếu i < n: Lặp lại Bước 2. Ngược lại: Dừng. 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Đổi chỗ trực tiếp – Interchange Sort • Cho dãy số a: 12 2 8 5 1 6 4 15 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Đổi chỗ trực tiếp – Interchange Sort 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Đổi chỗ trực tiếp – Interchange Sort 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Đổi chỗ trực tiếp – Interchange Sort 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Đổi chỗ trực tiếp – Interchange Sort 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Đổi chỗ trực tiếp – Interchange Sort 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Interchange Sort - Kết quả 12 2 8 5 1 6 4 15 2 12 8 5 1 6 4 15 1 12 8 5 2 6 4 15 1 8 12 5 2 6 4 15 1 5 12 8 2 6 4 15 1 2 12 8 5 6 4 15 1 2 8 12 5 6 4 15 1 2 5 12 8 6 4 15 1 2 4 12 8 6 5 15 1 2 4 8 12 6 5 15 1 2 4 6 12 8 5 15 1 2 4 5 12 8 6 15 1 2 4 5 8 12 6 15 1 2 4 5 6 12 8 15 1 2 4 5 6 8 12 5 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Đổi chỗ trực tiếp – Interchange Sort void InterchangeSort(int a[], int N ) { int i, j; for (i = 0 ; i<N-1 ; i++) for (j =i+1; j < N ; j++) if(a[j ]< a[i])// n
u có s sai v trí thì ñi ch Doicho(a[i],a[j]); } 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Các giải thuật sắp xếp • Sắp xếp đổi chỗ trực tiếp - Interchange Sort • Sắp xếp chọn trực tiếp – Selection Sort • Sắp xếp chèn trực tiếp – Insertion Sort • Sắp xếp nổi bọt – Buble Sort • Sắp xếp nổi bọt cải tiến - Shaker Sort • Shell sort • Heap sort • Quick sort • Merge sort 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Chọn trực tiếp – Selection Sort • Chọn phần tử nhỏ nhất trong N phần tử ban ñầu • Đưa phần tử này về vị trí ñúng là ñầu dãy hiện hành • Xem dãy hiện hành chỉ còn N-1 phần tử của dãy ban đầu – Bắt đầu từ vị trí thứ 2; – Lặp lại quá trình trên cho dãy hiện hành... ñến khi dãy hiện hành chỉ còn 1 phần tử 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Chọn trực tiếp – Selection Sort • Bước 1: i = 1; • Bước 2: Tìm phần tử a[min] nhỏ nhất trong dãy hiện hành từ a[i] ñến a[N] • Bước 3 : Nếu min ≠ i thì ðổi chỗ a[min] và a[i] • Bước 4 : Nếu i < N-1 thì i = i+1; Lặp lại Bước 2 Ngược lại: Dừng. 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Chọn trực tiếp – Selection Sort • Cho dãy số a: 122 8 5 1 6 4 15 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Chọn trực tiếp – Selection Sort 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Chọn trực tiếp – Selection Sort 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Chọn trực tiếp – Selection Sort 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Selection sort 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<N-1 ; 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]); } } 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Các giải thuật sắp xếp • Sắp xếp đổi chỗ trực tiếp - Interchange Sort • Sắp xếp chọn trực tiếp – Selection Sort • Sắp xếp chèn trực tiếp – Insertion Sort • Sắp xếp nổi bọt – Buble Sort • Sắp xếp nổi bọt cải tiến - Shaker Sort • Shell sort • Heap sort • Quick sort • Merge sort 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Chèn trực tiếp – Insertion Sort • Giả sử có một dãy a1 , a2 ,... ,an trong ñó i phần tử đầu tiên a1 , a2 ,... ,ai-1 ñã có thứ tự. • Tìm cách chèn phần tử ai vào vị trí thích hợp của đoạn đã được sắp để có dãy mới a1 , a2 ,... ,ai trở nên có thứ tự. Vị trí này chính là vị trí giữa hai phần tử ak- 1 và ak thỏa ak-1 < ai < ak (1≤k≤i). 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Chèn trực tiếp – Insertion Sort • Bước 1: i = 2; // gi s có ñon a[1] ñã ñ c sp • Bước 2: x = a[i]; Tìm vị trí pos thích hợp trong đoạn a[1] đến a[i-1] ñể chèn a[i] vào • Bước 3: Dời chỗ các phần tử từ a[pos] ñến a[i-1] sang phải 1 vị trí ñể dành chổ cho a[i] • Bước 4: a[pos] = x; // có ñon a[1]..a[i] ñã ñ c sp • Bước 5: i = i+1; Nếu i < n : Lặp lại Bước 2. Ngược lại : Dừng. 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Chèn trực tiếp – Insertion Sort • Cho dãy số : 12 2 8 5 1 6 4 15 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Chèn trực tiếp – Insertion Sort 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Chèn trực tiếp – Insertion Sort 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Insertion Sort – Caøi ñaët void InsertionSort(int a[], int N ) { 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(i=1 ; i<N ; i++) //ñoaïn a[0] ñaõ saép { 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 } } 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Insertion Sort - Kết quả 12 2 8 5 1 6 4 15 12 2 8 5 1 6 4 15 2 12 8 5 1 6 4 15 2 8 12 5 1 6 4 15 2 5 8 12 1 6 4 15 1 2 5 8 12 6 4 15 1 2 5 6 8 12 4 15 1 2 4 5 6 8 12 15 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Các giải thuật sắp xếp • Sắp xếp đổi chỗ trực tiếp - Interchange Sort • Sắp xếp chọn trực tiếp – Selection Sort • Sắp xếp chèn trực tiếp – Insertion Sort • Sắp xếp nổi bọt – Buble Sort • Sắp xếp nổi bọt cải tiến - Shaker Sort • Shell sort • Heap sort • Quick sort • Merge sort 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Nổi bọt – Bubble Sort • Ý tưởng chính của giải thuật là xuất phát từ cuối dãy, ñổi chỗ các cặp phần tử kế cận để ñưa phần tử nhỏ hơn trong cặp phần tử ñó về vị trí ñúng đầu dãy hiện hành, sau đó sẽ không xét đến nó ở bước tiếp theo, do vậy ở lần xử lý thứ i sẽ có vị trí ñầu dãy là i . 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Nổi bọt – Bubble Sort • Bước 1 : i = 1; // ln x lý ñu tiên • Bước 2 : j = N; //Duyt t cui dãy ng c v v trí i Trong khi (j > i) thực hiện: Nếu a[j]<a[j-1] thì Doicho(a[j],a[j-1]);//xét cp phn t k
cn j = j-1; • Bước 3 : i = i+1; // lần xử lý kế tiếp Nếu i > N - 1: Hết dãy. Dừng Ngược lại : Lặp lại Bước 2. 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Nổi bọt – Bubble Sort • Cho dãy số a: 2 12 8 5 1 6 4 15 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Nổi bọt – Bubble Sort 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Nổi bọt – Bubble Sort 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Nổi bọt – Bubble Sort 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Nổi bọt – Bubble Sort 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Bubble sort - Caøi ñaët void BubbleSort(int a[], int N) { int i, j; for (i = 0 ; i < N-1 ; i++) for (j = N-1; j>i ; j --) if(a[j]< a[j-1]) Swap(a[j], a[j-1]); } 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Bubble Sort - Kết quả 12 2 8 5 1 6 4 15 12 2 8 5 1 4 6 15 12 2 8 1 5 4 6 15 12 2 1 8 5 4 6 15 12 1 2 8 5 4 6 15 1 12 2 8 5 4 6 15 1 12 2 8 4 5 6 15 1 12 2 4 8 5 6 15 1 2 12 4 8 5 6 15 1 2 12 4 5 8 6 15 1 2 4 12 5 8 6 15 1 2 4 12 5 6 8 15 1 2 4 5 12 6 8 15 1 2 4 5 6 12 8 15 1 2 4 5 6 8 12 15 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Các giải thuật sắp xếp • Sắp xếp đổi chỗ trực tiếp - Interchange Sort • Sắp xếp chọn trực tiếp – Selection Sort • Sắp xếp chèn trực tiếp – Insertion Sort • Sắp xếp nổi bọt – Buble Sort • Sắp xếp nổi bọt cải tiến - Shaker Sort • Shell sort • Heap sort • Quick sort • Merge sort 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Shaker Sort • Dựa trên nguyên tắc đổi chỗ trực tiếp Khắc phục nhược điểm của Bubble Sort. • Trong mỗi lần sắp xếp, duyệt mảng theo 2 lượt từ 2 phiá khác nhau : – Lượt đi: đẩy phần tử nhỏ về ñầu mảng – Lượt về: đẩy phần tử lớn về cuối mảng • Ghi nhận lại những đoạn đã sắp xếp nhằm tiết kiệm các phép so sánh thừa. 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Shaker Sort void ShakeSort(int data[], int n){ int i, j, left, right, k; left = 0; right = d.n-1; k = n-1; while (left < right) { for (j = right; j > left; j--) if (data[j]< data[j-1]){ Doicho(data[j], data[j-1]); k =j; } left = k; for (j = left; j < right; j++) if (data[j]> data[j+1]) { Doicho(data[j],data[j-1]); k = j; } right = k; } } 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Các giải thuật sắp xếp • Sắp xếp đổi chỗ trực tiếp - Interchange Sort • Sắp xếp chọn trực tiếp – Selection Sort • Sắp xếp chèn trực tiếp – Insertion Sort • Sắp xếp nổi bọt – Buble Sort • Sắp xếp nổi bọt cải tiến - Shaker Sort • Shell sort • Heap sort • Quick sort • Merge sort 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Saép xeáp vun ñoáng - Heap sort • Ñònh nghóa heap: – Heap laø moät daõy caùc phaàn töû aleft, aleft+1,... , aright thoaû caùc quan heä: • ai ≥ a2i • ai ≥ a2i+1 vôùi ∀i ∈ [left, right] – Khi ñoù (ai , a2i), (ai ,a2i+1) ñöôïc goïi laø caùc caëp phaàn töû lieân ñôùi. – Heap ñöôïc ñònh nghóa nhö treân ñöôïc 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 chieàu caùc quan heä. 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Ví duï daõy laø heap: 12 8 5 1 4 6 215 2 3 4 5 6 7 81 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Saép xeáp vun ñoáng – Heap sort a2 a3 a4 a5 a6 a7 a8 a1 Caùc phaàn töû cuûa daõy ñöôïc bieåu dieãn theo caùc moái quan heä lieân ñôùi 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Saép xeáp vun ñoáng - Heap sort • Moät soá tính chaát cuûa Heap: – Tính chaát 1: Neáu aleft, aleft+1, …, aright laø moä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 laø moät heap. – Tính chaát 2: Neáu a1, a2, …, an laø moät heap thì phaàn töû a1 (ñaàu heap) luoân laø phaàn töû lôùn nhaát trong heap. – Tính chaát 3: Moïi daõy con aleft, aleft+1, ..., aright thoûa: 2left > right ñeàu laø heap. 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Saép xeáp vun ñoáng - Heap sort • Saép xeáp daõy taêng daàn qua 2 giai ñoaïn: – Giai ñoaïn 1: hieäu chænh daõy ban ñaàu thaønh heap – Giai ñoaïn 2: saép xeáp heap coù ñöôïc sau giai ñoaïn 1 thaønh daõy taêng daàn 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Heap sort – Giai ñoaïn 1 //input: daõy (a, N) //output: daõy (a, N) laø moät heap • Böôùc 1: left = N/2; //Theâm caùc phaàn töû aleft, .., a1 vaøo heap • Böôùc 2: Trong khi left > 0 //Löu yù: ñoaïn aleft+1, …, aN ñaõ laø heap • Böôùc 21: Hieäu chænh ñoaïn aleft, …, aN thaønh heap • Böôùc 22: left = left - 1; //Heát laëp 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Tạo heap • n = 8, n/2 = 4 • Xuất phát từ a[4], so sánh với a[8] ñổi chổ • a[3] so sánh với a[6], a[7] • a[2] so sánh với a[4], a[5] a[2]↔a[4] lan truyền so sánh a[4] với a[8] • … 1 2 3 4 5 6 7 8 12 2 8 5 1 6 4 15 12 2 8 15 1 6 4 5 12 15 8 2 1 6 4 5 12 15 8 5 1 6 4 2 15 12 8 5 1 6 4 2 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Heap sort – Giai ñoaïn 2 • Vaán ñeà: Saép xeáp heap a1, …, aN thaønh daõy taêng daàn //Ñaët: right = N Ł daõy a1, …, aright laø heap. • YÙ töôûng: – Theo tính chaát 2: a1 seõ laø phaàn töû lôùn nhaát, vì vaäy vò trí ñuùng cuûa a1 phaûi laø right - cuoái daõy. Ł Ñoåi choå (a1, aright) Ł ñöôïc theâm moät phaàn töû ôû ñuùng vò trí q Theo tính chaát 3: daõy con a2, …, aright-1 vaãn laø heap Ł Giaûm right, theâm a1 vaøo daõy vaø hieäu chænh laïi Ł daõy a1, …, aright laø heap. 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Heap sort – Giai ñoaïn 2 //input: daõy (a, N) laø heap //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 2: Trong khi right > 1 //Ñöa phaàn töû lôùn nhaát (a1)veà vò trí right • Böôùc 2.1: Hoaùnvò (a1 , aright); //Loaïi boû phaàn töû lôùn nhaát ra khoûi heap • Böôùc 2.2: right := right -1; • Böôùc 2.3: Hieäu chænh ñoaïn a1, a2, …, aright thaønh heap //Heát laëp 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Hiệu chỉnh heap • Đỗi chổ a[1] ↔ a[8] có 1 phần tử ñã ñúng vị trí • Tiến hành tương tự cho dãy n-1 phần tử Lưu ý: Chỉ cần xét phần tử a[1] 1 2 3 4 5 6 7 8 15 12 8 5 1 6 4 2 2 12 8 5 1 6 4 15 12 2 8 5 1 6 4 15 12 5 8 2 1 6 4 15 4 5 8 2 1 6 12 15 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Các giải thuật sắp xếp • Sắp xếp đổi chỗ trực tiếp - Interchange Sort • Sắp xếp chọn trực tiếp – Selection Sort • Sắp xếp chèn trực tiếp – Insertion Sort • Sắp xếp nổi bọt – Buble Sort • Sắp xếp nổi bọt cải tiến - Shaker Sort • Shell sort • Heap sort • Quick sort • Merge sort 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Quick sort – YÙ töôûng • Giaûi thuaät QuickSort saép xeáp daõy a1, a2 ..., aN döïa treân vieäc phaân hoaïch daõy ban ñaàu thaønh 3 phaàn : – Phaàn 1: Goàm caùc phaàn töû coù giaù trò khoâng lôùn hôn x – Phaàn 2: Goàm caùc phaàn töû coù giaù trò baèng x – Phaàn 3: Goàm caùc phaàn töû coù giaù trò khoâng beù hôn x vôùi x laø giaù trò cuûa moät phaàn töû tuøy yù trong daõy ban ñaàu. 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Quick sort – YÙ töôûng • Sau khi thöïc hieän phaân hoaïch, daõy ban ñaàu ñöôïc phaân thaønh 3 ñoaïn: – 1. ak < x , vôùi k = 1 .. j – 2. ak = x , vôùi k = j+1 .. i-1 – 3. ak > x , vôùi k = i..N 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] • Ñoaïn thöù 2 ñaõ coù thöù töï. • Neáu caùc ñoaïn 1 vaø 3 chæ coù 1 phaàn töû: ñaõ coù thöù töï khi ñoù daõy con ban ñaàu ñaõ ñöôïc saép. Quick sort – YÙ töôûng 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] • Ñoaïn thöù 2 ñaõ coù thöù töï. • Neáu caùc ñoaïn 1 vaø 3 coù nhieàu hôn 1 phaàn töû thì daõy ban ñaàu chæ coù thöù töï khi caùc ñ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 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 … Quick sort – YÙ töôûng 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Quick sort – Giải thuật • Böôùc 1: Neáu left ≥ right //daõy coù ít hôn 2 phaàn töû Keát thuùc; //daõy ñaõ ñöôïc saép xeáp • Böôùc 2: Phaân hoaïch daõy aleft … aright thaønh caùc ñoaïn: aleft.. aj, aj+1.. ai-1, ai.. Aright Ñoaïn 1 ≤ x Ñoaïn 2: aj+1.. ai-1 = x Ñoaïn 3: ai.. aright ≥ x • Böôùc 3: Saép xeáp ñoaïn 1: aleft.. aj • Böôùc 4: Saép xeáp ñoaïn 3: ai.. aright 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Quick sort – Phaân hoaïch daõy //input: daõy con aleft, …, aright //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 con laø giaù trò moác: x = a[p]; • Böôùc 2: Duyeät töø 2 ñaàu daõy ñeå phaùt hieän vaø hieäu chænh caëp phaàn töû a[i], a[j] vi phaïm ñieàu kieän – Böôùc 21: i = left; j = right; – Böôùc 22: Trong khi (a[i]<x) i++; – Böôùc 23: Trong khi (a[j]>x) j--; – Böôùc 24: Neáu i<= j // a[i] ≥ x ≥ a[j] maø a[j] ñöùng sau a[i] • Hoaùn vò (a[i],a[j]); i++; j--; – Böôùc 25: Neáu i < j: Laëp laïi Böôùc 22.//chöa xeùt heát maûng //Heát duyeät 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Quick sort – Ví dụ • Cho dãy số a: 12 2 8 5 1 6 4 15 Phân hoạch đoạn l =1, r = 8: x = A[4] = 5 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Quick sort – Ví dụ 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Quick sort – Ví dụ • Phân hoạch đoạn l =1, r = 3: x = A[2] = 2 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Quick sort – Ví dụ • Phân hoạch đoạn l = 5, r = 8: x = A[6] = 6 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] • Phân hoạch đoạn l = 7, r = 8: x = A[7] = 6 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Quick sort – Caøi ñaët 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ò moác 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--; } } if(left < j) QuickSort(a, left, j); if(i < right) QuickSort(a, i, right); } 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Các giải thuật sắp xếp • Sắp xếp đổi chỗ trực tiếp - Interchange Sort • Sắp xếp chọn trực tiếp – Selection Sort • Sắp xếp chèn trực tiếp – Insertion Sort • Sắp xếp nổi bọt – Buble Sort • Sắp xếp nổi bọt cải tiến - Shaker Sort • Shell sort • Heap sort • Quick sort • Merge sort 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp [email protected] Merge sort – YÙ töôûng • Giaûi thuaät Merge sort saép xeáp daõy a1, a2, ..., an döïa treân nhaän xeùt sau: – Moãi daõy a1, a2, ..., an 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ù thöù töï. • Ví duï: daõy 12, 2, 8,