Cấu trúc dữ liệu và giải thuật - Các giải thuật sắp xếp

G V : L Ê T H Ị N GỌC HẠN H CÁC GIẢI THUẬT SẮP XẾP 9/4/2015 Data structure & Algorithms 1 GIỚI THIỆU BÀI TOÁN SẮP XẾP  Bài toán 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ử.  Lưu ý: Thứ tự đề cập ở đây là một thứ tự tổng quát. Ví dụ: Danh sách trước khi sắp xếp: {1, 25, 6, 5, 2, 37, 40} Danh sách sau khi sắp xếp: {1, 2, 5, 6, 25, 37, 40} 9/4/2015 Data structure & Algorithms 2 GIỚI THIỆU BÀI TOÁN SẮP XẾP  Khái niệm “Nghịch thế” Xét một mảng các số a0, a1, , an Nếu có iaj 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ế 9/4/2015 Data structure & Algorithms 3 CÁC PHƯƠNG PHÁP SẮP XẾP Quick sort Merge sort Radix sort Shaker sort Radix sort  9/4/2015 Data structure & Algorithms 4 Selection sort  Insertion sort  Interchange sort Bubble sort Shaker sort Binary Insertion sort  ĐỔI CHỖ TRỰC TIẾP – INTERCHANGE SORT  Ý 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 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. 9/4/2015 Data structure & Algorithms 5 INTERCHANGE SORT – THUẬT TOÁN Bước 1: Khởi tạo i=0 // bắt đầu từ đầu dãy Bước 2: j = i+1; //tìm các cặp a[j]I Bước 3: Trong khi j<n thực hiện: Nếu a[j]<a[i] thì hoán vị a[i] và a[j]; j=j+1; Bước 4: i=i+1; Nếu i<n-1 thì lặp lại bước 2 Ngược lại: dừng 9/4/2015 Data structure & Algorithms 6 INTERCHANGE SORT – VÍ DỤ 9/4/2015 Data structure & Algorithms 7 9/4/2015 Data structure & Algorithms 8 INTERCHANGE SORT – VÍ DỤ 9/4/2015 Data structure & Algorithms 9 INTERCHANGE SORT – VÍ DỤ 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ó nghịch thế thì đổi chỗ Swap(a[i],a[j]); } 9/4/2015 Data structure & Algorithms 10 INTERCHANGE SORT – CÀI ĐẶT 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 hoán vị thực hiện tùy thuộc vào kết quả so sánh 9/4/2015 Data structure & Algorithms 11 INTERCHANGE SORT – ĐÁNH GIÁ SẮP XẾP CHỌN – SELECTION SORT 9/4/2015 Data structure & Algorithms 12 SELECTION SORT – Ý TƯỞNG Chọn phần tử nhỏ nhất đặt vào vị trí đầu tiên  Chọn phần tử nhỏ nhất trong số n-1 phần tử còn lại đặt vào vị trí thứ 2.  Lặp lại quá trình cho đến khi mảng chỉ còn 1 phần tử. 9/4/2015 Data structure & Algorithms 13 SELECTION SORT – THUẬT TOÁN  Bước 1: Khởi tạo i = 0.  Bước 2: Khởi đầu min = i, j = i+1  Bước 3: Nếu a[j]<a[min] thì min = j, nếu không thì sang bước 4  Bước 4: Tăng j thêm 1 đơn vị.  Bước 5: Nếu j<n thì quay lại bước 3, nếu không sang bước 6  Bước 6: Đổi chỗ a[min] và a[i], tăng i lên 1 đơn vị  Bước 7: Nếu i<n-1 thì quay lại bước 2, nếu không thì kết thúc. 9/4/2015 Data structure & Algorithms 14 SELECTION SORT – VÍ DỤ 9/4/2015 Data structure & Algorithms 15 9/4/2015 Data structure & Algorithms 16 SELECTION SORT – VÍ DỤ 9/4/2015 Data structure & Algorithms 17 SELECTION SORT – VÍ DỤ SELECTION SORT – VÍ DỤ 9/4/2015 Data structure & Algorithms 18 SELECTION SORT – CÀI ĐẶT 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) hoanvi(a[min],a[i]); } } 9/4/2015 Data structure & Algorithms 19 SELECTION SORT – ĐÁNH GIÁ Số phép so sánh:  Tại lượt i bao giờ cũng cần (n-i-1) số lần so sánh  Không phụ thuộc vào tình trạng dãy số ban đầu  Số phép so sánh: 9/4/2015 Data structure & Algorithms 20 Số phép gán: Tốt nhất: Xấu nhất: 9/4/2015 Data structure & Algorithms 21 SELECTION SORT – ĐÁNH GIÁ 9/4/2015 Data structure & Algorithms 22 CHÈN TRỰC TIẾP – INSERTION SORT CHÈN TRỰC TIẾP – Ý TƯỞNG - Tại bước thứ i thì các phần tử từ a[0] đến a[i-1]đều có thứ tự tăng dần. - Đầu tiên ta bắt đầu với i=1(a[0] không cần sắp) - Tìm vị trí thích hợp để chèn a[1] vào đoạn a[0]a[1] Kế tiếp, tìm vị trí thích hợp để chèn a[2] vào đoạn a[0]a[2] Làm tiếp tục cho đến khi sắp được phần tử cuối cùng. 9/4/2015 Data structure & Algorithms 23 INSERTION SORT – THUẬT TOÁN Bước 1: khởi tạo i=1 Bước 2: pos= i-1, x=a[i] Bước 3: Nếu x<a[pos] thì sang bước 4 không thì sang bước 6. Bước 4: Dời a[pos] sang phải: a[pos+1]=a[pos], giảm pos 1 đơn vị. Bước 5: Nếu pos>=0 thì quay lại bước 3, nếu không sang bước 6. Bước 6: Gán a[pos+1]=x, tăng i thêm 1 đơn vị Bước 7: Nếu i<n thì quay lại bước 2, không thì kết thúc 9/4/2015 Data structure & Algorithms 24 INSERTION SORT – VÍ DỤ 9/4/2015 Data structure & Algorithms 25 9/4/2015 Data structure & Algorithms 26 INSERTION SORT – VÍ DỤ 9/4/2015 Data structure & Algorithms 27 INSERTION SORT – VÍ DỤ 9/4/2015 Data structure & Algorithms 28 INSERTION SORT – VÍ DỤ 9/4/2015 Data structure & Algorithms 29 INSERTION SORT – VÍ DỤ void InsertionSort(int a[],int n) { int pos; int x; //lưu trữa[i] tránh bị ghi đè khi dời chỗ các phần tử. for(int i=1;i<n;i++) //đoạn a[0]đãsắp { x = a[i]; for(pos=i;(pos>0)&&(a[pos-1]>x);pos--) a[pos] = a[pos-1]; a[pos] = x; // chèn x vào dãy } } 9/4/2015 Data structure & Algorithms 30 INSERTION SORT – CÀI ĐẶT  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ượng trong trường hợp sau: 9/4/2015 Data structure & Algorithms 31 INSERTION SORT – ĐÁNH GIÁ 9/4/2015 Data structure & Algorithms 32 SẮP XẾP NỔI BỌT – BUBBLE SORT BUBBLE SORT – Ý TƯỞNG - Đưa dần các phần tử có khóa (giá trị) nhỏ về phía trước. - 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ử đó 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. 9/4/2015 Data structure & Algorithms 33  Bước 1: khởi tạo i=0  Bước 2: j=n-1; //duyệt từ cuối dãy ngược về vị trí i  Bước 3: trong khi j>i thực hiện Nếu a[j]<a[j-1] thì hoán vị a[j] và a[j-1] j=j-1  Bước 4: i=i+1; //lần xử lý kế tiếp Nếu i=n-1: dừng. //hết dãy Ngược lại: Lặp lại bước 2. 9/4/2015 Data structure & Algorithms 34 BUBBLE SORT – THUẬT TOÁN 9/4/2015 Data structure & Algorithms 35 BUBBLE SORT – VÍ DỤ 9/4/2015 Data structure & Algorithms 36 BUBBLE SORT – VÍ DỤ 9/4/2015 Data structure & Algorithms 37 BUBBLE SORT – VÍ DỤ 9/4/2015 Data structure & Algorithms 38 BUBBLE SORT – VÍ DỤ 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]); } 9/4/2015 Data structure & Algorithms 39 BUBBLE SORT – CÀI ĐẶT  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 hoán vị thực hiện tùy thuộc vào kết quả so sánh. 9/4/2015 Data structure & Algorithms 40 BUBBLE SORT – ĐÁNH GIÁ