Bài giảng Cấu trúc dữ liệu: Sắp xếp - TS. Lê Minh Trung & Th.S Lương Trần Ngọc Khiết

Bài giảng Cấu trúc dữ liệu: Sắp xếp cung cấp cho người học những kiến thức như: Chọn trực tiếp (Selection Sort); Chèn trực tiếp (Insertion Sort); Nổi bọt (Bubble Sort); Merge Sort; Quick Sort; Heap Sort; Radix Sort. Mời các bạn cùng tham khảo!
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu: Sắp xếp - TS. Lê Minh Trung & Th.S Lương Trần Ngọc Khiết TS. Lê Minh Trung Th.S Lương Trần Ngọc KhiếtKhoa CNTT, Đại học Sư phạm TP. HCMNội dung Chọn trực tiếp (Selection Sort) Chèn trực tiếp (Insertion Sort) Nổi bọt (Bubble Sort) Merge Sort Quick Sort Heap Sort Radix SortKhái niệm Sắp thứ tự:  Đầu vào: một mảng  Đầu ra: mảng 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ầnChọn trực tiếp Input: int a[n] Output: mảng đã được sắp xếp Ý tưởng:  Với mỗi i=0, 1, 2,…, n-2  Tìm phần tử nhỏ nhất của mảng con a[i..n-1] và hoán vị phần tử này với a[i].Sorted Unsorted 23 78 45 8 32 56 Original List 8 78 45 23 32 56 After pass 1 8 23 45 78 32 56 After pass 2 After pass 3 8 23 32 78 45 56 8 23 32 45 78 56 After pass 4 After pass 5 8 23 32 45 56 78Chọn trực tiếpChọn trực tiếpvoid SelectionSort(int a[], int n){ for(int i=0;iĐánh giá chọn trực tiếp Vòng lặp for ngoài có n-1 lần lặp i=0,1,…,n-2 Số phép so sánh của lần lặp thứ i: n-i-1 Số phép so sánh: ?−2 ?−1 ?  ?? = ?=0 ? − ? − 1 =? − 1 + ? − 2 + ⋯+ 1 = 2 Độ phức tạp của thuật toán: ? ?2Chèn trực tiếp (Insertion Sort) Input: int a[n] Output: mảng đã được sắp xếp Ý tưởng:  Với mỗi i=1,2,…,n-1  Mảng con a[0..i-1] đã được sắp thứ tự tăng, chèn a[i] vào vị trí thích hợp để mảng con a[0..i] sắp thứ tự tăng.Sorted Unsorted23 78 45 8 32 56 Original List23 78 45 8 32 56 After pass 123 45 78 8 32 56 After pass 2 After pass 38 23 45 78 32 568 23 32 45 78 56 After pass 4 After pass 58 23 32 45 56 78Chèn trực tiếpChèn trực tiếpvoid InsertionSort(int a[], int n){ for(int i=1;ix){ a[j+1]=a[j];j--; if(j==-1)break; } a[j+1]=x; }}Đánh giá chèn trực tiếp Vòng lặp for ngoài có n-1 lần lặp i=1,2,…,n-1 Tốt nhất  ?? = ?−1 ?=1 1 = ? − 1 ≈ ?(?) Xấu nhất ?−1  ?? = ?=1 2? = 2 1 + 2 + ⋯ + ? − 1 = ?(? − 1) ≈ ?(?2 ) Trung bình  ?? ≈ ?(?2 )Nổi bọt (Bubble Sort) Input: int a[n] Output: mảng đã được sắp xếp Ý tưởng:  Với mỗi i=n-1, n-2,…, 1  Với mỗi j=0, 1,…, i  Nếu a[j]Nổi bọt sorted Bước 1 6 4 7 2 3 sorted Bước 2 4 6 2 3 7 sorted Bước 3 4 2 3 6 7 sorted Bước 4 2 3 4 6 7Nổi bọtvoid BubbleSort(int a[],int n){ for(int i=n-1;i>=1;i--){ for(int j=1; ja[j]){ int temp =a[j-1]; a[j-1]=a[j]; a[j] = temp; } }}Đánh giá Bubble Sort Vòng lặp for ngoài có n-1 lần lặp i=n-1, n-2, …, 2, 1 Vòng lặp for trong có i lần lặp j=1, 2, …, i Mỗi lần lặp có 1 phép so sánh, số phép so sánh: ?−1 ?−1 ?  ?? = ?=1 ? = 1 + 2 + ⋯+ ? − 1 = ≈ ?(?2 ) 2 Độ phức tạp của thuật toán: ?(?2 )Cải tiến Bubble Sort Cho phép nổi bọt theo hai chiều  Nổi bọt xuống, nổi bọt lên Khi nổi bọt ghi nhận lại  Có sự nổi bọt thật sự hay không  exchange =false  mảng đã được sắp thứ tụ  Vị trí nổi bọt cuối cùngBubble Sort cải tiếnvoid BubbleSort(int a[],int n){ int iMax=n-1, jMax=0,t,k; bool exchange = true; do { exchange =false; for(int i=jMax;ia[i+1]){t=a[i]; a[i]=a[i+1]; a[i+1]=t;exchange=true;k=i;} iMax =k; if(!exchange)break; //nếu không có hoán vị nào trước đó thì thoát vì mảng đã được sắp thứ tự exchange = false; for(int i=iMax;i>jMax;i--) //nổi bọt lên if(a[i]Chia để trị Ý tưởng:  Chia danh sách ra làm 2 phần  Sắp thứ tự riêng cho từng phần  Trộn 2 danh sách riêng đó thành danh sách có thứ tự Hai giải thuật:  Merge sort:  Chia đều thành 2 danh sách  Sắp thứ tự riêng  Trộn lại  Quick sort:  Chia thành 3 phần: nhỏ, giữa (pivot), lớn  Sắp thứ tự riêng ...