Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 5: Phương pháp sắp xếp đơn giản - 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 5. Phương pháp sắp xếp đơn giản Ngo Huu Phuc, Le Quy Don Technical University1 Bài 5: Các phương pháp sắp xếp đơn giản Nội dung: 6.1. Khái niệm và vai trò của sắp xếp (13) 6.2. Sắp xếp chèn (6) 6.3. Sắp xếp chọn (4) 6.4. Sắp xếp nổi bọt (4) Tham khảo: 1. Lecture 16 Introduction to Sorting.htm 2. Data Structures and Algorithms Sorting.htm 3. Tham khảo bài giảng của TS Nguyễn Nam Hồng Ngo Huu Phuc, Le Quy Don Technical University2 5.1. Khái niệm và vai trò của sắp xếp 5.1.1. Các thuật toán sắp xếp. 5.1.2. Vai trò của sắp xếp. 5.1.3. Các vấn đề của sắp xếp. 5.1.4. Một số ứng dụng của sắp xếp. 5.1.5. Ý tưởng sắp xếp và phương pháp thực hiện. 5.1.6. Phân tích hiệu quả của giải thuật sắp xếp. Ngo Huu Phuc, Le Quy Don Technical University3 5.1.1. Các thuật toán sắp xếp (1/2) Thế nào là sắp xếp?  Đưa một dãy các đối tượng về dạng thứ bậc nào đó. Giải thuật sắp xếp dựa trên sự so sánh nào đó.  Việc sắp xếp chỉ dựa trên phép toán so sánh. Các phép toán cơ bản của sắp xếp.  So sánh.  Tráo đổi giữa các phần tử. Ngo Huu Phuc, Le Quy Don Technical University4 5.1.1. Các thuật toán sắp xếp (1/2) Quy ước.  Phương pháp sắp xếp của chương này là sắp xếp trong.  Các giải thuật có thể thay thế cho nhau được.  Mỗi mảng có một số phần tử.  Thành phần để xem xét trong sắp xếp có thể so sánh được.  N là số phần tử cần sắp xếp. Ngo Huu Phuc, Le Quy Don Technical University5 5.1.2. Vai trò của sắp xếp (1/2)  Nếu các đối tượng trong một mảng nào đó đã được sắp theo trật tự nào đó, có thể truy xuất thông tin nhanh chóng và chính xác.  Việc xây dựng giải thuật cho phép sắp xếp từng phần tử của mảng sẽ mất nhiều thời gian, độ phức tạp của giải thuật cỡ O(n2).  ≈ 50,000,000,000,000 bước cho việc sắp một mảng có 10,000,000 phần tử ⇒ 500,000 giây = 58 ngày, với máy tính có thể thực hiện 100 triệu phép tính toán/giây.  Với giải thuật sắp xếp cho cả mảng, độ phức tạp của giải thuật cỡ O(nlogn).  ≈ 250,000,000 bước cho việc sắp một mảng có 10,000,000 phần tử ⇒ 2.5 giây, với máy tính có thể thực hiện 100 triệu phép tính toán/giây. Ngo Huu Phuc, Le Quy Don Technical University6 5.1.2. Vai trò của sắp xếp (2/2)  Như vậy, sắp xếp là giải thuật cơ bản.  Thông thường, 25% khả năng của CPU dành cho việc sắp xếp.  Sắp xếp là bước cơ bản cho một số giải thuật khác, ví dụ: tìm kiếm nhị phân.  Có nhiều cách tiếp cận đến giải thuật sắp xếp, từ đó, có nhiều giải thuật săp xếp khác nhau. Ngo Huu Phuc, Le Quy Don Technical University7 5.1.3. Các vấn đề của sắp xếp  Sắp xếp theo trật tự tăng hay giảm?  Với cùng một giải thuật sắp xếp, có thể dùng cho cả sắp theo trật tăng hay giảm, bằng việc thay đổi phép so sánh: =.  Các khóa của giải thuật sắp xếp?  Có thể dùng nhiều khóa cho cùng một giải thuật sắp xếp. Cần lưu ý đến ý tưởng của bài toán.  Với các dữ liệu không phải là số thì sao? Với chuỗi, sử dụng phép so sánh chuỗi, từ điển, hay quy tắc nào đó. Ví dụ: Sắp chuỗi Brown-Williams, Brown America, Brown, John? Ngo Huu Phuc, Le Quy Don Technical University8 5.1.4. Một số ứng dụng của sắp xếp (1/2)  Với kết quả của quá trình sắp xếp, một số vấn đề có thể được thực hiện dễ dàng.  Nói chung, nếu có quá trình sắp xếp sẽ tăng tốc cho tìm kiếm trong ứng dụng cụ thể.  Ví dụ, nếu có một mảng đã sắp, có thể dễ dàng tìm được phần tử lớn thứ k trong mảng, với thời gian hằng số. Ngo Huu Phuc, Le Quy Don Technical University9 5.1.4. Một số ứng dụng của sắp xếp (2/2) Một số ứng dụng có dùng sắp xếp.  Các từ trong từ điển đã được sắp xếp.  Thông thường, các Files trong thư mục được sắp theo một trật tự nào đó.  Trong thư viện, các quyển sách được sắp theo một trật tự nào đó.  Các khóa học của một trường đại học được sắp theo khoa, theo mã của khóa học.  Các sự kiện được sắp theo thời gian.  Ngo Huu Phuc, Le Quy Don Technical University10 5.1.5. Ý tưởng sắp xếp và phương pháp thực hiện (1/2) Có nhiều ý tưởng cho giải thuật sắp xếp:  Chèn - Insertion: đặt các phần tử vào một vị trí thích hợp của một dãy các phần tử đã sắp.  Tráo đổi - Exchange: với mỗi cặp các phần tử, tráo đổi chúng về đúng thứ tự, thực hiện cho đến khi không còn cặp nào chưa đưa về đúng thứ tự.  Chọn - Selection: chọn phần tử lớn nhất (nhỏ nhất) trong danh sách, đưa về đúng vị trí.  Phân loại - Distribution: chia nhỏ thành nhiều mảnh dựa trên tiêu chí nào đó, sau đó sắp từng mảnh.  Hợp - Merging: có thể nối 2 dãy đã sắp xếp thành 1 dãy được sắp xếp. Ngo Huu Phuc, Le Quy Don Technical University11 5.1.5. Ý tưởng sắp xếp và phương pháp thực hiện (2/2) Phương pháp sắp xếp:  Sắp xếp chọn:  Tìm phần tử lớn nhất (nhỏ nhất) trong số các phần tử chưa xét và đặt chúng vào đúng vị trí.  Thực hiện cho đến khi các phần tử đều được xét.  Sắp xếp chèn:  Với mỗi phần tử, chèn chúng vào mảng con đã sắp đúng trật tự.  Thực hiện tương tự cho các phần tử còn lại.  So sánh và tráo đổi – Sắp xếp nổi bọt:  Tìm 2 phần tử trong dãy không đúng trật tự, tráo đổi vị trí của chúng.  Giữ lại danh sách đã hiệu chỉnh. Ngo Huu Phuc, Le Quy Don Technical University12 5.1.6. Phân tích hiệu quả của giải thuật sắp xếp (1/2)  Sự hiệu quả:  Với trường hợp tồi nhất của giải thuật, độ phức tạp là thế nào?  Trong trường hợp trung bình có tốt hơn trường hợp tồi nhất không?  Yêu cầu của dữ liệu là gì?  Có thể truy xuất ngẫu nhiên được không?  Có cần thêm thao tác nào không ngoài “so sánh” và “tráo đổi”?  Không gian bộ nhớ sử dụng: Thuật toán có cần thêm không gian phụ nào nào không? Ngo Huu Phuc, Le Quy Don Technical University13 5.1.6. Phân tích hiệu quả của giải thuật sắp xếp (2/2)  Tính ổn định: Thuật toán có tính ổn định không?  Sự hiệu quả, nếu dãy đã gần sắp: Thuật toán có hiệu quả hơn nếu như dãy đã cho gần được sắp? (nhiều phần tử đã đúng thứ tự, chỉ có một số chưa đúng thứ tự) Ngo Huu Phuc, Le Quy Don Technical University14 5.2. Sắp xếp chèn (1/6) Ví dụ minh họa:  Xem xét người chơi bài (sắp theo chiều giảm dần) Quân bài thứ nhất được sắp.  Với các quân bài còn lại:  Tìm từ cuối dãy cho đến khi tìm thấy quân bài lớn hơn quân bài mới,  Di chuyển các quân bài nhỏ về sau một bậc.  Chèn quân bài mới vào vị trí đó. Ngo Huu Phuc, Le Quy Don Technical University15   Q  2  9  A  K  10  J  2  2  9   5.2. Sắp xếp chèn (2/6)  Đây là phương pháp sắp hiệu quả nếu có ít phần tử cần sắp.  Mã lệnh cho phương pháp khá đơn giản.  Cách thức làm việc của Sắp xếp chèn.  Sử dụng biến để chia tập thành 2 vùng: vùng đẵ sắp và vùng chưa sắp.  Vùng đã sắp bắt đầu từ phần tử đầu tiên của dãy.  Lấy phần tử đầu tiên của vùng chưa sắp và chèn vào vùng đã sắp.  Như vậy, vùng đã sắp sẽ có thêm một phần tử.  Thực hiện tương tư cho đến khi vùng chưa sắp không còn phần tử nào. Ngo Huu Phuc, Le Quy Don Technical University16 5.2. Sắp xếp chèn (3/6) Ngo Huu Phuc, Le Quy Don Technical University17 8 5 2 6 9 4 6 Chuỗi đã sắp Phần tử sẽ được chèn 5 8 2 6 9 4 6 Giá trị 5 nhỏ hơn 8, 5 sẽ thay thế cho 8, dãy đã sắp sẽ có kích thước tăng lên 1 (có 2 phần tử đã được sắp. Giả sử: Sắp xếp dãy các số nguyên theo phương pháp chèn. Hoạt động của Insertion Sort 5.2. Sắp xếp chèn (4/6) #include #include #define MAX 100 void inputdata(int* list,int n); void printlist(int* list,int n); void insertionsort(int* list, int n); void main() { int list[MAX], n; printf("Nhap so phan tu cua mang, toi da = 100\n"); scanf("%d",&n); inputdata(list,n); printf("Mang da nhap:\n"); printlist(list,n); insertionsort(list,n); printf("Mang da sap xep:\n"); printlist(list,n); getch(); } Ngo Huu Phuc, Le Quy Don Technical University18 void inputdata(int* list,int n) { int i; printf("Nhap cac phan tu cua 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 cua mang: \n"); for(i=0;i<n;i++) printf("%d\t",list[i]); printf("\n"); } 5.2. Sắp xếp chèn (5/6) Ngo Huu Phuc, Le Quy Don Technical University19 void insertionsort(int *list, int n) { int pos,i,x; for(i=1;i<n;i++) { x=list[i]; pos=i-1; while((pos>=0) && (list[pos]>x)) { list[pos+1]=list[pos]; pos--; } list[pos+1]=x; } } 5.2. Sắp xếp chèn (6/6) Phân tích sắp xếp chèn:  Trường hợp tồi nhất:  Với dữ liệu dạng nào cho kết quả tồi nhất?  Dữ liệu được sắp theo chiều ngược lại.  Độ phức tạp trong trường hợp này?  O(N2) – phép so sánh: N2, phép tráo đổi: N2  Trường hợp tốt nhất:  Với dữ liệu dạng nào cho kết quả tốt nhất?  Dữ liệu đã được sắp.  Độ phức tạp trong trường hợp này?  O(N) – phép so sánh: N, phép tráo đổi: none  Trường hợp trung bình:  Với dữ liệu dạng nào cho kết quả trung bình?  Dữ liệu dạng ngẫu nhiên.  Độ phức tạp trung bình?  O(N2) – phép so sánh: N2, phép tráo đổi: N2 Ngo Huu Phuc, Le Quy Don Technical University20 5.3. Sắp xếp chọn (1/5)  Phương pháp sắp xếp chọn - Selection Sort  Đây cũng là phương pháp sắp xếp đơn giản.  Tại mỗi bước, chọn phần tử lớn nhất (nhỏ nhất) trong số phần tử chưa sắp và đưa về đúng vị trí.  Ý tưởng: (với sắp xếp tăng dần)  Bước 1: Tìm phần tử nhỏ nhất trong dãy và đưa nó về vị trí đầu tiên của dãy.  Bước 2: Tìm phần tử nhỏ thứ hai và đưa nó về vị trí thứ 2 trong dãy.  Bước tiếp: Lặp lại quá trình trên cho đến khi tất các phần tử đã sắp đúng thứ tự. Ngo Huu Phuc, Le Quy Don Technical University21 5.3. Sắp xếp chọn (2/5) Ngo Huu Phuc, Le Quy Don Technical University22 6 4 92 3 2 4 96 3 2 4 96 3 Tìm được phần tử có giá trị 2, nhỏ nhất trong dãy. Tráo đổi nó với phần tử đầu tiên của dãy, phần tử có giá trị 6. Tìm phần tử nhỏ nhất trong số những phần tử chưa sắp, phần tử có giá trị 3 và trao đổi nó với phần tử đứng thứ 2 trong dãy, có giá trị 4. Giả sử, cho 5 phần tử như sau, chưa sắp. Sắp lại dãy số trên theo phương pháp sắp xếp chọn. Hoạt động của Selection Sort cách trực tiếp. 5.2. Sắp xếp chọn (3/5) #include "stdio.h" #include "conio.h" #define MAX 100 void swap(int *x,int *y); void selectionsort(int list[], 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 cua mang\n"); scanf("%d",&n); inputdata(list,n); printf("Mang da nhap:\n"); printlist(list,n); selectionsort(list,n); printf("Mang da sap xep:\n"); printlist(list,n); getch(); } Ngo Huu Phuc, Le Quy Don Technical University23 void inputdata(int list[],int n) { int i; printf("Nhap cac phan tu cua 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 cua mang: \n"); for(i=0;i<n;i++) printf("%d\t",list[i]); printf("\n"); } 5.2. Sắp xếp chọn (4/5) Ngo Huu Phuc, Le Quy Don Technical University24 void swap(int *x,int *y) { int temp; temp = *x; *x = *y; *y = temp; } void selectionsort(int list[], int n) { int i,j,minpos; for(i=0;i<(n-1);i++) { minpos=i; for(j=i+1;j<n;j++) if (list[j]<list[minpos]) minpos=j; if(minpos!=i) swap(&list[minpos],&list[i]); } } 5.3. Sắp xếp chọn (5/5) Phân tích hiệu quả của sắp xếp chọn:  Độ phức tạp: Trong trường hợp tồi nhất: O(n2) Trung bình, độ phức tạp cũng là O(n2).  Thuật toán thích hợp với sắp xếp dãy, với mỗi phần tử trong dãy có kích thước lớn, vì đòi hỏi ít phép tráo đổi.  Với dữ liệu đã gần được sắp, thuật toán không cho thấy chúng tốt hơn. Ngo Huu Phuc, Le Quy Don Technical University25 5.4. Sắp xếp nổi bọt - Bubble Sort (1/5)  Sắp xếp nổi bọt là kỹ thuật sắp xếp đơn giản, trong kỹ thuật này tổ chức các phần tử của mảng thành các cặp liền kề.  Với các cặp liền kề, thứ i và thứ i+1, đổi chỗ các phần tử này nếu chúng không đúng trật tự sắp xếp. Sau mỗi lần thực hiện việc đổi chỗ, ta thu được 1 phần tử đã ở đúng vị trí.  Thực hiện lặp lại quá trình trên cho n-1 phần tử còn lại.  Thuật toán dừng khi không còn cặp nào sai vị trí. Ngo Huu Phuc, Le Quy Don Technical University26 5.4. Sắp xếp nổi bọt (2/5) Ngo Huu Phuc, Le Quy Don Technical University27 3 2 2 2 2 3 3 3 4 4 4 1 1 1 1 4 5 5 5 5 2 2 2 3 3 1 1 1 3 4 4 4 5 5 5 2 1 1 2 3 3 4 4 5 5 1 2 3 4 5 5.2. Sắp xếp nổi bọt (3/5) #include #include #define MAX 100 void inputdata(int list[],int n); void printlist(int list[],int n); void swap(int *x,int *y); void bubblesort(int list[], int n); void main() { int list[MAX], n; printf("Nhap so phan tu cua mang\n"); scanf("%d",&n); inputdata(list,n); printf("Mang da nhap:\n"); printlist(list,n); bubblesort(list,n); printf("Mang da sap xep:\n"); printlist(list,n); getch(); } Ngo Huu Phuc, Le Quy Don Technical University28 void inputdata(int list[],int n) { int i; printf("Nhap cac phan tu cua 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 cua mang: \n"); for(i=0;i<n;i++) printf("%d\t",list[i]); printf("\n"); } 5.2. Sắp xếp nổi bọt (4/5) Ngo Huu Phuc, Le Quy Don Technical University29 void swap(int *x,int *y) { int temp; temp = *x; *x = *y; *y = temp; } void bubblesort(int list[], int n) { int i,j; for(i=0;i<(n-1);i++) for(j=n-1;j>i;j--) if(list[j]<list[j-1]) swap(&list[j],&list[j-1]); } 5.4. Sắp xếp nổi bọt (5/5) Phân tích hiệu quả của thuật toán sắp xếp nổi bọt:  Độ phức tạp:  Trong trường hợp tồi nhất: O(n2)  Trong trường hợp trung bình: O(n2)  Đối với dữ liệu:  Dữ liệu cho phép truy cập ngẫu nhiên.  Cần có phép toán so sánh và tráo đổi.  Đối với dữ liệu đã gần được sắp:  Số phép tráo đổi có thể ít, nhưng số phép so sánh nhiều. Tổng quát, không tốt hơn so với dữ liệu random. Ngo Huu Phuc, Le Quy Don Technical University30 Nhận xét  Trong bài 5, giới thiệu một số thuật toán sắp xếp đơn giản.  Sắp xếp chèn,  Sắp xếp chọn,  Sắp xếp nổi bọt.  Các giải thuật này được thực hiện với dữ liệu cho phép truy cập ngẫu nhiên (sắp xếp trong).  Độ phức tạp trong trường hợp trung bình là O(n2).  Trong bài 6, giới thiệu một số giải thuật sắp xếp cho hiệu quả cao hơn. Ngo Huu Phuc, Le Quy Don Technical University31