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

bangtqh@hotmail.com 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 2bangtqh@hotmail.com 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 3bangtqh@hotmail.com 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 4bangtqh@hotmail.com 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 5bangtqh@hotmail.com Đổ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 6bangtqh@hotmail.com Đổ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 7bangtqh@hotmail.com Đổ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 8bangtqh@hotmail.com Đổ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 9bangtqh@hotmail.com Đổ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 10bangtqh@hotmail.com Đổ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 11bangtqh@hotmail.com Đổ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 12bangtqh@hotmail.com Đổ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 13bangtqh@hotmail.com Đổ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 14bangtqh@hotmail.com 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 15bangtqh@hotmail.com Đổ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 16bangtqh@hotmail.com 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 17bangtqh@hotmail.com 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 18bangtqh@hotmail.com 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 19bangtqh@hotmail.com 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 20bangtqh@hotmail.com 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 21bangtqh@hotmail.com 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 22bangtqh@hotmail.com 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 23bangtqh@hotmail.com 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 24bangtqh@hotmail.com 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 25bangtqh@hotmail.com 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 26bangtqh@hotmail.com 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 27bangtqh@hotmail.com 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 28bangtqh@hotmail.com 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 29bangtqh@hotmail.com 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 30bangtqh@hotmail.com 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 31bangtqh@hotmail.com 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 32bangtqh@hotmail.com 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 33bangtqh@hotmail.com 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 34bangtqh@hotmail.com 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 35bangtqh@hotmail.com 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 36bangtqh@hotmail.com Nổi bọt – Bubble Sort 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp 37bangtqh@hotmail.com Nổi bọt – Bubble Sort 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp 38bangtqh@hotmail.com Nổi bọt – Bubble Sort 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp 39bangtqh@hotmail.com Nổi bọt – Bubble Sort 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp 40bangtqh@hotmail.com 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 41bangtqh@hotmail.com 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 42bangtqh@hotmail.com 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 43bangtqh@hotmail.com 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 44bangtqh@hotmail.com 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 45bangtqh@hotmail.com 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 46bangtqh@hotmail.com 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 47bangtqh@hotmail.com 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 48bangtqh@hotmail.com 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 49bangtqh@hotmail.com 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 50bangtqh@hotmail.com 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 51bangtqh@hotmail.com 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 52bangtqh@hotmail.com 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 53bangtqh@hotmail.com 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 54bangtqh@hotmail.com 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 55bangtqh@hotmail.com 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 56bangtqh@hotmail.com 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 57bangtqh@hotmail.com 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 58bangtqh@hotmail.com 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 59bangtqh@hotmail.com • Ñ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 60bangtqh@hotmail.com • Ñ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 61bangtqh@hotmail.com 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 62bangtqh@hotmail.com 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 63bangtqh@hotmail.com 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 64bangtqh@hotmail.com Quick sort – Ví dụ 04/2010 Kỹ thuật lập trình C - Thuật toán sắp xếp 65bangtqh@hotmail.com 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 66bangtqh@hotmail.com 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 67bangtqh@hotmail.com • 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 68bangtqh@hotmail.com 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 69bangtqh@hotmail.com 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 70bangtqh@hotmail.com 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,