Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 6: Sắp xếp nhanh - Quick Sorts - Ngô Hữu Phước

Lecturer: PhD. Ngo Huu Phuc Tel: 0438 326 077 Mob: 098 5696 580 Email: ngohuuphuc76@gmail.com Cấu trúc dữ liệu và giải thuật Bài 6. Sắp xếp nhanh - Quick Sorts Ngo Huu Phuc, Le Quy Don Technical University1 Bài 6. Quick Sorts Nội dung: 6.1. Thuật toán QuickSort (6) 6.2. Ví dụ về QuickSort (7) 6.3. Hoạt động của QuickSort (6) 6.4. Hiệu quả của QuickSort (6) Tham khảo: 1. Intro to Algorithms Chapter 8 QuickSort.htm 2. Lecture 5 – quicksort.htm 3. Quick Sort.htm 4. Bài giảng của TS Nguyễn Nam Hồng Ngo Huu Phuc, Le Quy Don Technical University2 6.1. Thuật toán QuickSort (1/6)  Giải thuật Quick-sort là phương pháp sắp xếp dựa trên chiến lược chia để trị.  Giải thuật gồm các bước:  Phép chia: chọn ngẫu nhiên một phần tử x làm khóa, chia tập dữ liệu S ban đầu thành 3 phần:  L chứa các phần tử nhỏ hơn x  E chứa các phần tử bằng x  G chứa các phần tử lớn hơn x  Bước lặp: sắp xếp 2 tập L và G  Hiệu chỉnh lại các tập L, E và G Ngo Huu Phuc, Le Quy Don Technical University3 x x L GE x 6.1. Thuật toán QuickSort (2/6) Các bước cơ bản của thuật toán:  Chia tập dữ liệu ban đầu thành 2 tập con:  sao cho, tất cả các phần tử bên trái nhỏ hơn tất cả các phần tử bên phải.  Sắp xếp 2 tập con một cách độc lập và nối chúng lại với nhau:  như vậy, ta được dãy đã sắp xếp. Ngo Huu Phuc, Le Quy Don Technical University4 6.1. Thuật toán QuickSort (3/6)  Với mỗi tập con trên, mỗi tập chia thành 02 tập con nếu có thể  như vậy, ta có tối đa 04 tập con.  tập các phần tử nhỏ nhất ở bên trái cùng, tập các phần tử lớn nhất ở bên phải cùng.  Lặp lại quá trình trên cho đến khi tập chỉ có 1 phần tử  nối tất cả các tập với nhau ta được dãy đã sắp xếp. Ngo Huu Phuc, Le Quy Don Technical University5 6.1. Thuật toán QuickSort (4/6)  Ta chia tập dữ liệu ban đầu như sau:  Trên tập S, lấy mỗi phần tử y được lấy ra khỏi tập  Đưa phần tử y vào tập L, E hay G, tùy thuộc vào phép so sánh với khóa x  Với mỗi phép lấy 1 phần tử và đưa chúng vào tập tương ứng, độ phức tạp của phép toán đó là O(1).  Như vậy, phép chia dữ liệu của thuật toán QuickSort có độ phức tạp O(n). Ngo Huu Phuc, Le Quy Don Technical University6 6.1. Thuật toán QuickSort (5/6) Ngo Huu Phuc, Le Quy Don Technical University7 7 4 9 6 2 → 2 4 6 7 9 4 2 → 2 4 7 9 → 7 9 2 → 2 9 → 9 6.1. Thuật toán QuickSort (6/6) Ngo Huu Phuc, Le Quy Don Technical University8 Việc thực thi giải thuật QuickSort được mô tả qua cây nhị phân:  Mỗi node biểu diễn một lần gọi đệ quy và lưu giữ:  Dãy chưa được sắp xếp và khóa.  Dãy sau khi sắp xếp.  Gốc của cây là lần gọi đệ quy đầu tiên.  Các lá của cây là lần gọi ứng với dãy con có kích thước 0 hoặc 1. 6.2. Ví dụ về QuickSort (1/7) Ngo Huu Phuc, Le Quy Don Technical University9  Chọn khóa 6.2. Ví dụ về QuickSort (2/7) Ngo Huu Phuc, Le Quy Don Technical University10  Phân chia dãy ban đầu bằng gọi đệ quy với khóa đã chọn. 6.2. Ví dụ về QuickSort (3/7) Ngo Huu Phuc, Le Quy Don Technical University11  Gọi đệ quy cho dãy con, với khóa mới 6.2. Ví dụ về QuickSort (4/7) Ngo Huu Phuc, Le Quy Don Technical University12  Tương tự, gọi đệ quy, sau đó nối kết quả. 6.2. Ví dụ về QuickSort (5/7) Ngo Huu Phuc, Le Quy Don Technical University13  Tương tự cho phần bên phải. 6.2. Ví dụ về QuickSort (6/7) Ngo Huu Phuc, Le Quy Don Technical University14  Gọi đệ quy cho dãy con, với khóa mới 6.2. Ví dụ về QuickSort (7/7) Ngo Huu Phuc, Le Quy Don Technical University15  Nối kết quả cho gốc của cây. 6.3. Hoạt động của QuickSort (1/6) Có thể mô tả như sau:  Với tập ban đầu, chọn 1 phần tử làm khóa.  Đổi chỗ phần tử đầu tiên với khóa.  Sử dụng 2 chỉ số i và j để duyệt phần còn lại trên dãy.  Chỉ số i tăng đến khi tại vị trí i đó, phần tử này có giá trị lớn hơn khóa. Chỉ số j giảm đến khi giá trị tại vị trí j nhỏ hơn khóa.  So sánh giữa i và j, nếu i<j, đổi chỗ 2 phần tử này cho nhau. Nếu không, đổi chỗ khóa (phần tử đầu tiên) với phần tử j.  Khi đó, có thể chia mảng đã cho thành 2 mảng con, mảng thứ nhất từ vị trí 1 đến vị trí j-1, mảng thứ 2 từ vị trí j+1 đến n. Sau đó có thể lặp lại quá trình trên cho các mảng con. Ngo Huu Phuc, Le Quy Don Technical University16 6.3. Hoạt động của QuickSort (2/6) Chọn khóa:  Ta có thể chọn bất kỳ phần tử nào trong mảng làm khóa.  Nếu chọn phần tử đầu tiên của mảng làm khóa, lựa chọn này là tồi nếu mảng đã sắp xếp. Khi đó, một mảng con có 0 phần tử. Thông thường, chọn khóa gần với giữa của mảng với hi vọng lựa chọn này sẽ cho 2 mảng con có số phần tử gần bằng nhau. Ngo Huu Phuc, Le Quy Don Technical University17 Hàm chọn vị trí có dạng: int getkeyposition(int i,int j) { return(( i+j )/ 2); } Việc chọn này cũng tùy ý, có thể sử dụng hàm random để chọn khóa. Hàm này có dạng: int getkeyposition(int i, int j) { return(random number in the range of i to j); } 6.3. Hoạt động của QuickSort (3/6) Xây dựng hàm đệ quy:  Hàm đệ quy cho giải thuật có thể gọi QSort(S, a, b) sắp dãy con trong dãy ban đầu S tử chỉ số a đến chỉ số b.  Với QSort(L, 0, n-1) sắp mảng L từ phần tử đầu tiên đến phần tử cuối n-1.  QSort(S, a, b) sẽ được gọi đệ quy cho các mảng con nhỏ hơn, với chỉ số thay đổi. Ngo Huu Phuc, Le Quy Don Technical University18 6.3. Hoạt động của QuickSort (4/6) Chia dữ liệu:  Với khóa đã chọn x  Tổ chức lại tập S sao cho:  S[a]S[t-1] là các phần tử < x  S[t] = x  S[t+1]S[b] là các phần tử > p Ngo Huu Phuc, Le Quy Don Technical University19 6.3. Hoạt động của QuickSort (5/6) #include "stdio.h" #include "conio.h" #define MAX 100 void swap(int *x,int *y); int getkeyposition(int i,int j); void qsort(int list[],int m,int n); void inputdata(int list[],int n); void printlist(int list[],int n); void main() { int list[MAX], n; printf("Nhap so phan tu cho mang\n"); scanf("%d",&n); inputdata(list,n); printf("Cac phan tu da nhap:\n"); printlist(list,n); qsort(list,0,n-1); printf("\nCac phan tu da sap xep:\n"); printlist(list,n); getch(); } Ngo Huu Phuc, Le Quy Don Technical University20 void inputdata(int list[],int n) { int i; printf("Nhap cac phan tu cho mang\n"); for(i=0;i<n;i++) scanf("%d",&list[i]); fflush(stdin); } void printlist(int list[],int n) { int i; printf("Cac phan tu trong mang: \n"); for(i=0;i<n;i++) printf("%d\t",list[i]); printf("\n"); } 6.3. Hoạt động của QuickSort (6/6) void swap(int *x,int *y) { int temp; temp = *x; *x = *y; *y = temp; } int getkeyposition(int i,int j ) { return((i+j) /2); } void qsort(int list[],int m,int n) { int key,i,j,k; if( m < n) { k = getkeyposition(m,n); swap(&list[m],&list[k]); Ngo Huu Phuc, Le Quy Don Technical University21 key = list[m]; i = m+1; j = n; while(i <= j) { while((i <= n) && (list[i] <= key)) i++; while((j >= m) && (list[j] > key)) j--; if( i < j) swap(&list[i],&list[j]); } swap(&list[m],&list[j]); qsort(list,m,j-1); qsort(list,j+1,n); } } 6.4. Hiệu quả của Quicksort (1/6) Trong trường hợp tốt nhất:  Giả sử, tại mỗi lần chia, tập S được chia thành 2 tập con có kích thước gần bằng nhau.  Nếu số phần tử là n, lần đầu tiên sẽ chia thành 2 tập con có kích thước gần bằng n/2.  Tiếp theo, mỗi tập con lại được chia thành 2 tập con có kích thước gần bằng n/4, thực hiện điều này đến khi kích thước mỗi mảng bằng 1. Ngo Huu Phuc, Le Quy Don Technical University22 6.4. Hiệu quả của Quicksort (2/6) Trong trường hợp tốt nhất (tiếp):  Gọi T(n) là thời gian cần thiết để sắp n phần tử.  Vì thời gian để sắp n phần tử là tổng thời gian cần để đưa khóa về đúng vị trí và thời gian để sắp 2 tập con có kích thước gần bằng n/2. Do đó: T(n) = c*n + 2*T(n/2) Ngo Huu Phuc, Le Quy Don Technical University23 6.4. Hiệu quả của Quicksort (3/6) Trong trường hợp tốt nhất (tiếp):  Một cách tương tự, ta có: T(n/2) = c*n/2 + 2*T(n/4) T(n/4) = c*n/4 + 2*T(n/8), giả thiết T(1) = 1. Như vậy:  T(n) = c*n + 2(c*(n/2) + 2T(n/4))  T(n) = c*n + c*n + 4T(n/4)) = 2*c*n + 4T(n/4) = 2*c*n + 4(c*(n/4) + 2T(n/8))  T(n) = 2*c*n + c*n + 8T(n/8) = 3*c*n + 8T(n/8)  T(n) = (log n)*c*n + n T(n/n)= (log n)*c*n + n T(1) = n + n*(log n) *c T(n) = O( n log(n)) Ngo Huu Phuc, Le Quy Don Technical University24 6.4. Hiệu quả của Quicksort (4/6) Trong trường hợp tồi nhất:  Xem xét trường hợp, khóa chính là phần tử lớn nhất (hoặc) nhỏ nhất trên mỗi tập con.  Như vậy, tất cả các phần tử sẽ nằm về một phía.  Ví dụ, xem xét dãy sau:  [5 3 2 1 4 6 8]  1 được lấy làm khóa.  rõ ràng, vẫn còn n – 1 phần tử chưa sắp.  điều này tiếp tục xuất hiện với các tập con. Ngo Huu Phuc, Le Quy Don Technical University25 6.4. Hiệu quả của Quicksort (5/6)  Như vậy, với mỗi lần thực hiện Quick Sort, chỉ có 1 phần tử được sắp. Thực hiện việc này n lần. Mỗi lần, thời gian thực hiện cho quá trình chia mảng con là O(n).  Như vậy, thời gian cho Quick sort trong trường hợp này: O(n2). Ngo Huu Phuc, Le Quy Don Technical University26 6.4. Hiệu quả của Quicksort (6/6) Đối với trường hợp trung bình?  đã chứng minh được, độ phức tạp: O(nlogn)  Trong thực tế, quicksort thường cho thấy sự hiệu quả trong sắp xếp.  có thể hình dung qua xác suất.  với các tập có ít hơn 30 phần tử, quicksort chưa cho thấy sự hiệu quả. Ngo Huu Phuc, Le Quy Don Technical University27