›
›

Cấu trúc dữ liệu và giải thuật - Chương 4: Sắp xếp (sorting)

pdf 71 trang vanle 2490
Download
Bạn đang xem 20 trang mẫu của tài liệu "Cấu trúc dữ liệu và giải thuật - Chương 4: Sắp xếp (sorting)", để tải tài liệu gốc về máy bạn click vào nút DOWNLOAD ở trên

Tài liệu đính kèm:

  • pdfcau_truc_du_lieu_va_giai_thuat_chuong_4_sap_xep_sorting.pdf

Nội dung text: Cấu trúc dữ liệu và giải thuật - Chương 4: Sắp xếp (sorting)

  1. CHƯƠNG 4: SẮP XẾP (SORTING)
  2. Nội dung 2  Tổng quan  Các phương pháp sắp xếp thơng dụng Chương 4: Sắp xếp
  3. Tổng quan 3  Tại sao phải sắp xếp?  Để cĩ thể sử dụng thuật tốn tìm nhị phân  Để thực hiện thao tác nào đĩ được nhanh hơn  Định nghĩa bài tốn sắp xếp  Sắp xếp là quá trình xử lý một danh sách các phần tử (hoặc các mẫu tin) để đặt chúng theo một thứ tự thỏa mãn một tiêu chuẩn nào đĩ dựa trên nội dung thơng tin lưu giữ tại mỗi phần tử Chương 4: Sắp xếp
  4. Các phương pháp sắp xếp thơng dụng 4  Phương pháp Đổi chỗ trực tiếp (Interchange sort)  Phương pháp Nổi bọt (Bubble sort)  Phương pháp Chèn trực tiếp (Insertion sort)  Phương pháp Chọn trực tiếp (Selection sort)  Phương pháp dựa trên phân hoạch (Quick sort) Chương 4: Sắp xếp
  5. Interchange Sort 5  Khái niệm nghịch thế:  Xét một mảng các số a[0], a[1], a[n-1]  Nếu cĩ i a[j], 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ế a[0] a[1] a[n -1] Chương 4: Sắp xếp
  6. Interchange Sort – Ý tưởng 6  Nhận xét:  Để sắp xếp một dãy số, ta cĩ thể xét các nghịch thế cĩ trong dãy và làm triệt tiêu dần chúng đi  Ý tưởng:  Xuất phát từ đầu dãy, tìm tất cả nghịch thế chứa phần tử này, triệt tiêu chúng bằng cách đổi chỗ phần tử này với phần tử tương ứng trong cặp nghịch thế  Lặp lại xử lý trên với các phần tử tiếp theo trong dãy Chương 4: Sắp xếp
  7. Interchange Sort – Thuật tốn 7 // input: dãy (a, n) // output: dãy (a, n) đã được sắp xếp  Bước 1: i = 0; // bắt đầu từ đầu dãy  Bước 2: j = i+1;  Bước 3: Trong khi j a[j] thì đổi chỗ a[i], a[j]  j = j+1;  Bước 4: i = i+1;  Nếu (i < n-1): Lặp lại Bước 2  Ngược lại: Dừng Chương 4: Sắp xếp
  8. Interchange Sort – Ví dụ 8 j 1 2 3 4 5 6 7 8 121 2 8 5 1 6 4 15 i Nếu a[i] > a[j] thì đổi chỗ a[i], a[j] Chương 4: Sắp xếp
  9. Interchange Sort – Ví dụ 9 j 1 2 3 4 5 6 7 8 1 122 8 5 2 6 4 15 i Nếu a[i] > a[j] thì đổi chỗ a[i], a[j] Chương 4: Sắp xếp
  10. Interchange Sort – Ví dụ 10 j 1 2 3 4 5 6 7 8 1 2 124 8 5 6 4 15 i Nếu a[i] > a[j] thì đổi chỗ a[i], a[j] Chương 4: Sắp xếp
  11. Interchange Sort – Ví dụ 11 j 1 2 3 4 5 6 7 8 1 2 4 125 8 6 5 15 i Nếu a[i] > a[j] thì đổi chỗ a[i], a[j] Chương 4: Sắp xếp
  12. Interchange Sort – Ví dụ 12 1 2 3 4 5 6 7 8 1 2 4 5 6 8 12 15 Nếu a[i] > a[j] thì đổi chỗ a[i], a[j] Chương 4: Sắp xếp
  13. Interchange Sort - Cài đặt 13 void InterchangeSort(int a[], int n) { for (int i=0 ; i a[j]) //nếu cĩ nghịch thế thì đổi chỗ Swap(a[i], a[j]); } void Swap(int &a, int &b) { int temp = a; a = b; b = temp; }
  14. Interchange Sort - Đánh giá giải thuật 14  Số lượng các phép so sánh xảy ra khơng phụ thuộc vào tình trạng của dãy số ban đầu  Số lượng phép hốn vị thực hiện tùy thuộc vào kết quả so sánh Chương 4: Sắp xếp
  15. Các phương pháp sắp xếp thơng dụng 15  Phương pháp Đổi chỗ trực tiếp (Interchange sort)  Phương pháp Nổi bọt (Bubble sort)  Phương pháp Chèn trực tiếp (Insertion sort)  Phương pháp Chọn trực tiếp (Selection sort)  Phương pháp dựa trên phân hoạch (Quick sort) Chương 4: Sắp xếp
  16. Bubble Sort – Ý tưởng 16  Xuất phát từ cuối (đầu) dãy, đổi chỗ các cặp phần tử kế cận để đưa phần tử nhỏ (lớn) hơn trong cặp phần tử đĩ về vị trí đúng đầu (cuối) dãy hiện hành, sau đĩ sẽ khơng xét đến nĩ ở bước tiếp theo  Ở lần xử lý thứ i cĩ vị trí đầu dãy là i  Lặp lại xử lý trên cho đến khi khơng cịn cặp phần tử nào để xét
  17. Bubble Sort – Thuật tốn 17 // input: dãy (a, n) // output: dãy (a, n) đã được sắp xếp  Bước 1: i = 0;  Bước 2: j = n-1; //Duyệt từ cuối dãy ngược về vị trí i  Trong khi (j > i) thực hiện:  Nếu a[j]<a[j-1] thì đổi chỗ a[j], a[j-1]  j = j-1;  Bước 3: i = i+1; // lần xử lý kế tiếp  Nếu i = n: Dừng // Hết dãy  Ngược lại: Lặp lại Bước 2
  18. Bubble Sort – Ví dụ 18 j 1 2 3 4 5 6 7 8 121 2 8 5 1 6 4 15 i Nếu a[j]<a[j-1] thì đổi chỗ a[j], a[j-1]
  19. Bubble Sort – Ví dụ 19 j 1 2 3 4 5 6 7 8 1 122 2 8 5 4 6 15 i Nếu a[j]<a[j-1] thì đổi chỗ a[j], a[j-1]
  20. Bubble Sort – Ví dụ 20 j 1 2 3 4 5 6 7 8 1 2 124 4 8 5 6 15 i Nếu a[j]<a[j-1] thì đổi chỗ a[j], a[j-1]
  21. Bubble Sort – Ví dụ 21 j 1 2 3 4 5 6 7 8 1 2 4 125 8 5 6 15 i Nếu a[j]<a[j-1] thì đổi chỗ a[j], a[j-1]
  22. Bubble Sort – Ví dụ 22 j 1 2 3 4 5 6 7 8 1 2 4 5 126 8 6 15 i Nếu a[j]<a[j-1] thì đổi chỗ a[j], a[j-1]
  23. Bubble Sort – Ví dụ 23 j 1 2 3 4 5 6 7 8 1 2 4 5 6 128 8 15 i Nếu a[j]<a[j-1] thì đổi chỗ a[j], a[j-1]
  24. Bubble Sort – Ví dụ 24 j 1 2 3 4 5 6 7 8 1 2 4 5 6 8 1212 15 i Nếu a[j]<a[j-1] thì đổi chỗ a[j], a[j-1]
  25. Bubble Sort - Cài đặt 25 void BubbleSort(int a[], int n) { for (int i=0; i i; j ) if(a[j] < a[j-1]) Swap(a[j], a[j-1]); }
  26. Bubble Sort - Đánh giá giải thuật 26  Số lượng các phép so sánh xảy ra khơng phụ thuộc vào tình trạng của dãy số ban đầu  Số lượng phép hốn vị thực hiện tùy thuộc vào kết quả so sánh
  27. Bubble Sort - Đánh giá giải thuật 27  Khuyết điểm:  Khơng nhận diện được tình trạng dãy đã cĩ thứ tự hay cĩ thứ tự từng phần  Các phần tử nhỏ được đưa về vị trí đúng rất nhanh, trong khi các phần tử lớn lại được đưa về vị trí đúng rất chậm
  28. Các phương pháp sắp xếp thơng dụng 28  Phương pháp Đổi chỗ trực tiếp (Interchange sort)  Phương pháp Nổi bọt (Bubble sort)  Phương pháp Chèn trực tiếp (Insertion sort)  Phương pháp Chọn trực tiếp (Selection sort)  Phương pháp dựa trên phân hoạch (Quick sort)
  29. Insertion Sort – Ý tưởng 29  Nhận xét:  Mọi dãy a[0] , a[1] , , a[n-1] luơn cĩ i-1 phần tử đầu tiên a[0] , a[1] , ,a[i-2] đã cĩ thứ tự (2 ≤ i)  Ý tưởng chính:  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 a[0] , a[1] , ,a[i-1] trở nên cĩ thứ tự  Vị trí này chính là pos thỏa : a[pos-1] a[i ]< a[pos] (1 pos i)
  30. Insertion Sort – Ý tưởng 30 Chi tiết hơn:  Dãy ban đầu a[0] , a[1] , , a[n-1], xem như đã cĩ đoạn gồm một phần tử a[0] đã được sắp  Thêm a[1] vào đoạn a[0] sẽ cĩ đoạn a[0] a[1] được sắp  Thêm a[2] vào đoạn a[0] a[1] để cĩ đoạn a[0] a[1] a[2] được sắp  Tiếp tục cho đến khi thêm xong a[n-1] vào đoạn a[0] a[1] a[n- 1] sẽ cĩ dãy a[0] a[1] A[n-1] được sắp
  31. Insertion Sort – Thuật tốn 31 // input: dãy (a, n) // output: dãy (a, n) đã được sắp xếp  Bước 1: i = 2; // giả sử cĩ đoạn a[0] đã được sắp  Bước 2: x = a[i]; //Tìm vị trí pos thích hợp trong đoạn a[0] //đến a[i] để chèn x 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 x  Bước 4: a[pos] = x; // cĩ đoạn a[0] a[i] đã được sắp  Bước 5: i = i+1; Nếu i n: Lặp lại Bước 2 Ngược lại: Dừng
  32. Insertion Sort – Ví dụ 32 1 2 3 4 5 6 7 8 12 2 8 5 1 6 4 15
  33. Insertion Sort – Ví dụ 33 Chèn a[1] vào (a[0], a[1]) pos 1 2 3 4 5 6 7 8 122 2 8 5 1 6 4 15 i x
  34. Insertion Sort – Ví dụ 34 Chèn a[2] vào (a[0] a[2]) pos 1 2 3 4 5 6 7 8 2 128 8 5 1 6 4 15 i x
  35. Insertion Sort – Ví dụ 35 Chèn a[3] vào (a[0] a[3]) pos 1 2 3 4 5 6 7 8 2 58 12 5 1 6 4 15 i x
  36. Insertion Sort – Ví dụ 36 Chèn a[4] vào (a[0] a[4]) pos 1 2 3 4 5 6 7 8 21 5 8 12 1 6 4 15 i x
  37. Insertion Sort – Ví dụ 37 Chèn a[5] vào (a[0] a[5]) pos 1 2 3 4 5 6 7 8 1 2 5 68 12 6 4 15 i x
  38. Insertion Sort – Ví dụ 38 Chèn a[6] vào (a[0] a[6]) pos 1 2 3 4 5 6 7 8 1 2 54 6 8 12 4 15 i x
  39. Insertion Sort – Ví dụ 39 Chèn a[7] vào (a[0] a[7]) pos 1 2 3 4 5 6 7 8 1 2 4 5 6 8 12 1515 i x
  40. Insertion Sort – Ví dụ 40 pos 1 2 3 4 5 6 7 8 1 2 4 5 6 8 12 15
  41. Insertion Sort – Cài đặt 41 void InsertionSort(int a[], int n){ int pos, x; for(int i=0; i =0 && a[pos]>x) { a[pos+1] = a[pos]; pos ; } a[pos] = x; } }
  42. Insertion Sort – Nhận xét 42  Khi tìm vị trí thích hợp để chèn a[i] vào đoạn a[0] đến a[i-1], do đoạn đã được sắp nên cĩ thể sử dụng giải thuật tìm nhị phân để thực hiện việc tìm vị trí pos giải thuật sắp xếp chèn nhị phân Binary Insertion Sort  Lưu ý: Chèn nhị phân chỉ làm giảm số lần so sánh, khơng làm giảm số lần dời chỗ  Ngồi ra, cĩ thể cải tiến giải thuật chèn trực tiếp với phần tử cầm canh để giảm điều kiện kiểm tra khi xác định vị trí pos
  43. Insertion Sort – Đánh giá giải thuật 43  Các phép so sánh xảy ra trong mỗi vịng lặp tìm vị trí thích hợp pos. Mỗi lần xác định vị trí pos đang xét khơng thích hợp dời chỗ phần tử a[pos-1] đến vị trí pos  Giải thuật thực hiện tất cả N-1 vịng lặp tìm pos, do số lượng phép so sánh và dời chỗ này phụ thuộc vào tình trạng của dãy số ban đầu, nên chỉ cĩ thể ước lược trong từng trường hợp như sau:
  44. Các phương pháp sắp xếp thơng dụng 44  Phương pháp Đổi chỗ trực tiếp (Interchange sort)  Phương pháp Nổi bọt (Bubble sort)  Phương pháp Chèn trực tiếp (Insertion sort)  Phương pháp Chọn trực tiếp (Selection sort)  Phương pháp dựa trên phân hoạch (Quick sort)
  45. Selection Sort – Ý tưởng 45  Nhận xét  Mảng cĩ thứ tự thì a[i]=min(a[i], a[i+1], , a[n-1])  Ý tưởng: mơ phỏng một trong những cách sắp xếp tự nhiên nhất trong thực tế:  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ử Cấu trúc Dữ liệu - Tìm kiếm và Sắp xếp
  46. Selection Sort – Thuật tốn 46 // input: dãy (a, n) // output: dãy (a, n) đã được sắp xếp  Bước 1 : i = 0  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-1]  Bước 3 : Nếu min i: Đổi chỗ a[min] và a[i]  Bước 4 : Nếu i < n:  i =i+1  Lặp lại Bước 2 Ngược lại: Dừng. //n phần tử đã nằm đúng vị trí
  47. Selection Sort – Ví dụ 47 Find MinPos(1, 8) Swap(a[i], a[min]) min 1 2 3 4 5 6 7 8 12 2 8 5 1 6 4 15 i
  48. Selection Sort – Ví dụ 48 Find MinPos(2, 8) Swap(a[i], a[min]) min 1 2 3 4 5 6 7 8 1 2 8 5 12 6 4 15 i
  49. Selection Sort – Ví dụ 49 Find MinPos(3, 8) Swap(a[i], a[min]) min 1 2 3 4 5 6 7 8 1 2 8 5 12 6 4 15 i
  50. Selection Sort – Ví dụ 50 Find MinPos(4, 8) Swap(a[i], a[min]) min 1 2 3 4 5 6 7 8 1 2 4 5 12 6 8 15 i
  51. Selection Sort – Ví dụ 51 Find MinPos(5, 8) Swap(a[i], a[min]) min 1 2 3 4 5 6 7 8 1 2 4 5 12 6 8 15 i
  52. Selection Sort – Ví dụ 52 Find MinPos(6, 8) Swap(a[i], a[min]) min 1 2 3 4 5 6 7 8 1 2 4 5 6 12 8 15 i
  53. Selection Sort – Ví dụ 53 Find MinPos(7, 8) Swap(a[i], a[min]) min 1 2 3 4 5 6 7 8 1 2 4 5 6 8 12 15 i
  54. Selection Sort – Cài đặt 54 void SelectionSort(int a[], int n ) { int min; // chỉ số phần tử nhỏ nhất trong dãy hiện hà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 nhận vị trí phần tử nhỏ nhất if (min != i) Swap(a[min], a[i]); } }
  55. Selection Sort – Đánh giá giải thuật 55  Ở lượt thứ i, cần (n-i) lần so sánh để xác định phần tử nhỏ nhất hiện hành  Số lượng phép so sánh khơng phụ thuộc vào tình trạng của dãy số ban đầu  Trong mọi trường hợp, số lần so sánh là: n 1 n(n 1) (n i) i 1 2
  56. Các phương pháp sắp xếp thơng dụng 56  Phương pháp Đổi chỗ trực tiếp (Interchange sort)  Phương pháp Nổi bọt (Bubble sort)  Phương pháp Chèn trực tiếp (Insertion sort)  Phương pháp Chọn trực tiếp (Selection sort)  Phương pháp dựa trên phân hoạch (Quick sort)
  57. Quick Sort – Ý tưởng 57  Một vài hạn chế của thuật tốn Đổi chỗ trực tiếp:  Mỗi lần đổi chỗ chỉ thay đổi 1 cặp phần tử trong nghịch thế; các trường hợp như: i aj > ak (*) chỉ cần thực hiện 1 lần đổi chổ (ai, ak): thuật tốn khơng làm được  Độ phức tạp của thuật tốn O(N2) khi N đủ lớn thuật tốn sẽ rất chậm  Ý tưởng: phân chia dãy thành các đoạn con tận dụng được các phép đổi chỗ dạng (*) và làm giảm độ dài dãy khi sắp xếp cải thiện đáng kể độ phức tạp của thuật tốn
  58. Quick Sort – Ý tưởng 58  Giải thuật QuickSort sắp xếp dãy a[0], a[1] , a[n-1] dựa trên việc phân hoạch dãy ban đầu thành 3 phần:  Phần 1: Gồm các phần tử cĩ giá trị khơng lớn hơn x  Phần 2: Gồm các phần tử cĩ giá trị bằng x  Phần 3: Gồm các phần tử cĩ giá trị khơng bé hơn x với x là giá trị của một phần tử tùy ý trong dãy ban đầu.  Sau khi thực hiện phân hoạch, dãy ban đầu được phân thành 3 đoạn: 1. a[k] ≤ x , với k = 1 j 2. a[k ] = x , với k = j+1 i-1 3. a[k ] x , với k = i n-1
  59. Quick Sort – Ý tưởng 59  Đoạn thứ 2 đã cĩ thứ tự  Nếu các đoạn 1 và 3 chỉ cĩ 1 phần tử thì chúng cũng đã cĩ thứ tự, khi đĩ dãy con ban đầu đã được sắp  Ngược lại, nếu các đoạn 1 và 3 cĩ nhiều hơn 1 phần tử thì dãy con ban đầu chỉ cĩ thứ tự khi các đoạn 1, 3 được sắp  Để sắp xếp các đoạn 1 và 3, ta lần lượt tiến hành việc phân hoạch từng dãy con theo cùng phương pháp phân hoạch dãy ban đầu vừa trình bày
  60. Quick Sort – Giải thuật 60 // input: dãy con (a, left, right) // output: dãy con (a, left, right) được sắp tăng dần  Bước 1: Nếu left = right // dãy cĩ ít hơn 2 phần tử Kết thúc; // dãy đã được sắp xếp  Bước 2: Phân hoạch dãy a[left] a[right] thành các đoạn: a[left] a[j], a[j+1] a[i-1], a[i] a[right] // Đoạn 1 x // Đoạn 2: a[j+1] a[i-1] = x // Đoạn 3: a[i] a[right] x  Bước 3: Sắp xếp đoạn 1: a[left] a[j]  Bước 4: Sắp xếp đoạn 3: a[i] a[right]
  61. Quick Sort – Phân hoạch dãy 61 // input: dãy con a[left], , a[right] // output: dãy con chia thành 3 đoạn: đoạn 1 ≤ đoạn 2 ≤ đoạn 3  Bước 1: Chọn tùy ý một phần tử a[p] trong dãy con là giá trị mốc: x = a[p];  Bước 2: Duyệt từ 2 đầu dãy để phát hiện và hiệu chỉnh cặp phần tử a[i], a[j] vi phạm điều kiện  Bước 2.1: i = left; j = right;  Bước 2.2: Trong khi (a[i] x) j ;  Bước 2.4: Nếu i<= j // a[i] x a[j] mà a[j] đứng sau a[i]  Hốn vị (a[i], a[j]); i++; j ;  Bước 2.5: Nếu i < j: Lặp lại Bước 2.2 //chưa xét hết mảng //Hết duyệt
  62. Quick Sort – Ví dụ Phân hoạch dãy 62 X 5 i j 1 2 3 4 5 6 7 8 12 2 8 5 1 6 4 15 left right STOP STOP Khơng nhỏ hơn x Khơng lớn hơn x
  63. Quick Sort – Ví dụ Phân hoạch dãy 63 X 5 i j 1 2 3 4 5 6 7 8 4 2 8 5 1 6 12 15 left right STOP STOP Khơng nhỏ hơn x Khơng lớn hơn x
  64. Quick Sort – Ví dụ 64 j i 1 2 3 4 5 6 7 8 4 2 1 5 8 6 12 15 left right
  65. Quick Sort – Ví dụ Phân hoạch dãy 65 X 6 i j 1 2 3 4 5 6 7 8 1 2 4 5 8 6 12 15 left right Sắp xếp đoạn 3 STOP STOP Khơng nhỏ hơn x Khơng lớn hơn x
  66. Quick Sort – Ví dụ 66 j i 1 2 3 4 5 6 7 8 1 2 4 5 6 8 12 15 left right Sắp xếp đoạn 3
  67. Quick Sort – Ví dụ 67 1 2 3 4 5 6 7 8 1 2 4 5 6 8 12 15
  68. Quick Sort – Cài đặt 68 void QuickSort(int a[], int left, int right) { int i, j, x; if (left right) return; x = a[(left+right)/2]; // chọn phần tử giữa làm giá trị mốc i = left; j = right; do{ while(a[i] x) j ; if(i <= j) { Swap(a[i], a[j]); i++ ; j ; } } while(i < j); if(left<j) QuickSort(a, left, j); if(i<right) QuickSort(a, i, right); }
  69. Quick Sort – Đánh giá giải thuật 69  Về nguyên tắc, cĩ thể chọn giá trị mốc x là một phần tử tùy ý trong dãy, nhưng để đơn giản, phần tử cĩ vị trí giữa thường được chọn, khi đĩ p = (l +r)/ 2  Giá trị mốc x được chọn sẽ cĩ tác động đến hiệu quả thực hiện thuật tốn vì nĩ quyết định số lần phân hoạch  Số lần phân hoạch sẽ ít nhất nếu ta chọn được x là phần tử trung vị (median), nhiều nhất nếu x là cực trị của dãy  Tuy nhiên do chi phí xác định phần tử median quá cao nên trong thực tế người ta khơng chọn phần tử này mà chọn phần tử nằm chính giữa dãy làm mốc với hy vọng nĩ cĩ thể gần với giá trị median
  70. Quick Sort – Đánh giá giải thuật 70 Hiệu quả phụ thuộc vào việc chọn giá trị mốc:  Trường hợp tốt nhất: mỗi lần phân hoạch đều chọn phần tử median làm mốc, khi đĩ dãy được phân chia thành 2 phần bằng nhau và cần log2(n) lần phân hoạch thì sắp xếp xong  Nếu mỗi lần phân hoạch chọn phần tử cĩ giá trị cực đại (hay cực tiểu) là mốc dãy sẽ bị phân chia thành 2 phần khơng đều: một phần chỉ cĩ 1 phần tử, phần cịn lại gồm (n-1) phần tử, do vậy cần phân hoạch n lần mới sắp xếp xong
  71. Quick Sort – Đánh giá giải thuật 71  Độ phức tạp thuật tốn Trường hợp Độ phức tạp Tốt nhất O(NlogN) Trung bình O(NlogN) Xấu nhất O(N2) Chương 4: Sắp xếp