Bài giảng Cấu trúc dữ liệu và giải thuật chương 3: Sắp xếp trong

CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT Chương III: Sắp xếp trong Khái niệm Sắp thứ tự: Đầu vào: một dãy Đầu ra: dãy có thứ tự tăng (hoặc giảm) trên khóa Phân loại: Sắp thứ tự ngoại (external sort): tập tin Sắp thứ tự nội (internal sort): bộ nhớ Giả thiết: Sắp thứ tự nội Sắp tăng dần Ví dụ Xếp hàng sinh viên một lớp từ thấp đến cao Chọn cách xếp thế nào cho nhanh nhất có thể? Phương pháp sắp xếp trong Có 3 nhóm chính, mỗi nhóm gồm đơn giản và cải tiến PP sắp xếp chọn (Selection Sort) Cải tiến: PP HeapSort PP sắp xếp đổi chổ (Bubble Sort) Cải tiến: PP QuickSort PP sắp xếp chèn (Insertion Sort) Cải tiến: PP ShellSort 1. PP chọn đơn giản Ý tưởng: Mỗi bước ta chọn phần tử nhỏ nhất đưa về đầu dãy và lặp lại với phần còn lại của dãy cho đến hết dãy. Ví dụ: Dãy có 8 phần tử, sắp xếp tăng dần 44 55 12 42 94 18 06 67 Lần lặp thứ nhất 44 55 12 42 94 18 06 67 Lần lặp 2 44 55 12 42 94 18 06 67 Lần lặp 3 44 55 12 42 94 18 06 67 Lần lặp 4 44 55 12 42 94 18 06 67 Lần lặp 5 44 55 12 42 94 18 06 67 Lần lặp 6 44 55 12 42 94 18 06 67 Lần lặp 7 44 55 12 42 94 18 06 67 Đã sắp xong Cài đặt void sapxepchon(mang x, int n) { int csmin; for(int i=0; itam && j>=0) { x[j+1] = x[j]; j--; } x[j+1]=tam; } } Độ phức tạp thuật tóan Txấu=O(n2) Ttốt = O(n) 3. Phương pháp đổi chổ đơn giản(phương pháp nổi bọt hay Bubble Sort) Ý tưởng: Duyệt dãy x1, x2, …, xn, nếu 2 phần tử xi>xi+1 thì hóan đổi cho nhau, mãi đến khi không còn xảy ra 2 phần tử nào đổi chỗ nữa. Ví dụ: Sắp xếp nổi bọt Sắp xếp tăng dãy: 44 55 12 42 94 18 06 67 Ví dụ: Sắp xếp nổi bọt Bước lặp: 1 44 55 12 42 94 18 06 67 Ví dụ: Sắp xếp nổi bọt Bước lặp: 2 44 12 42 55 18 06 67 94 Ví dụ: Sắp xếp nổi bọt Bước lặp: 3 12 42 44 18 06 55 67 94 Ví dụ: Sắp xếp nổi bọt Vòng lặp: 4 12 42 18 06 44 55 67 94 Ví dụ: Sắp xếp nổi bọt Vòng lặp: 5 12 18 06 42 44 55 67 94 Ví dụ: Sắp xếp nổi bọt Vòng lặp: 6 12 06 18 42 44 55 67 94 Ví dụ: Sắp xếp nổi bọt Vòng lặp: 7 06 12 18 42 44 55 67 94 Cài đặt (thuật tóan nổi bọt đơn giản) void BubbleSort(mang x, int n) { for(int i=n-1; i>=1; i--) for(int j=0; jx[j+1]) hoanvi(x[j],x[j+1]); } Độ phức tạp thuật tóan sắp xếp nổi bọt T(n)=O(n2) Sinh viên cần xem thuật tóan được sử dụng trong sách giáo khoa (cải tiến giải thụât trên), và phương pháp đổi chổ cải tiến ShakerSort. 4. Phương pháp sắp xếp chèn cải tiến (ShellSort) Ý tưởng: Phân chia dãy ban đầu thành các dãy con gồm các phần tử cách nhau h vị trí. Tiến hành sắp xếp dãy con theo phương pháp chèn trực tiếp. Sau đó giảm khỏang cách h và tiếp tục quá trình trên đến khi h=1. Ví dụ: Sắp xếp tăng dãy 6 2 8 5 1 12 4 15 Ví dụ: Sắp xếp tăng dãy Xét dãy bước: h[1]=3, h[2]=1 6 2 8 5 1 12 4 15 Ví dụ: Sắp xếp tăng dãy Với: h[1]=3 6 2 8 5 1 12 4 15 Ví dụ: Sắp xếp tăng dãy Với h[1]=3 5 1 8 6 2 12 4 15 Ví dụ: Sắp xếp tăng dãy Với h[2]=1, vòng lặp 1, 2, 3 4 1 8 5 2 12 6 15 Ví dụ: Sắp xếp tăng dãy Với h[2]=1, vòng lặp 4 1 4 5 8 2 12 6 15 Ví dụ: Sắp xếp tăng dãy Với h[2]=1, vòng lặp 5, 6, 7 1 2 4 5 8 12 6 15 Cài đặt void ShellSort(mang x, int n) { int i, j, k, h[Max_Buoc_Chia], len; int tam; TaoDayBuocChia(n,k,h); for(int step=0; step=0 && tam=g, và dãy con phải phần tử xj=g Dãy trái g) j--; if(ii) QuickSort(x,i,R); } Độ phức tạp thuật tóan Txấu(n)=O(n2) Ttb(n)=Ttốt(n)=O(nlog2n) 6. Phương pháp sắp xếp trên cây có thứ tự (HeapSort) Là cải tiến phương pháp sắp xếp chọn, nhưng tận dụng được kết quả so sánh và hóan vị của các lần trước đó. Phương pháp này dựa trên khối HeapSort bằng cách đưa dãy vào cây nhị phân có thứ tự. Định nghĩa của khối (Heap) Định nghĩa: Dãy xm,….,xn là một Heap nếu: xk>=x2k xk>=x2k+1 với mọi k mà: mx2 và x1>x3 (10>6, 10>8) x2>x4 và x2>x5 (6>4, 6>5) Ví dụ 2: x1=6, x2= 10, x3=8, x4= 4, x5= 5 không là một Heap, vì vi phạm : x1=x2i, xi>x2i+1) x1 x2 x3 x7 x4 x5 x6 Ý tưởng phương pháp Nếu biểu diễn một Heap x1, …, xn lên cây nhị phân có thứ tự, ta sẽ thu được dãy có thứ tự bằng cách: Hóan vị nút gốc x1 (lớn nhất) với nút cuối xn. Khi đó x2, …, xn-1 vẫn là một Heap. Bổ sung x1 vào Heap và tạo Heap mới x1, .., xn-1. Lặp lại quá trình trên cho đến khi cây chỉ còn một nút. Ví dụ Sắp xếp dãy số: 44 55 12 42 94 18 06 67 Bước 1: Tạo Heap từ dãy số trên, ta cứ việc đưa dãy đó lên cây sau đó nếu vi phạm thì hóan đổi dần 44 55 12 06 42 94 18 67 Vi phạm 42x[CsCon]) LaHeap=1; else { x[CsCha]=x[CsCon]; CsCha = CsCon; CsCon = 2*CsCha; } x[CsCha] = Cha; }} //Chú ý: Mảng x có chỉ số từ 1  n (Không phải 0  n-1) Cài đặt void TaoHeapDayDu(mang x,int n) { int L=n/2, R=n; while(L>=1) { Shift(x,L,R); L--; } } void HeapSort(mang x, int n) { TaoHeapDayDu(x,n); int L=1, R=n; while(R>1) { hoanvi(x[1],x[R]); Shift(x,L,--R); } } Độ phức tạp thuật tóan Txấu(n)=O(nlog2n)