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

Chia sẻ: Conbongungoc09 | Ngày: | Loại File: PDF | Số trang:65

Thêm vào BST

Báo xấu

42
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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ết Khoa CNTT, Đại học Sư phạm TP. HCM
Nộ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 Sort
Khá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ần
Chọ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 78
Chọn trực tiếp
Chọn trực tiếp void 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: 𝑂 𝑛2
Chè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 Unsorted 23 78 45 8 32 56 Original List 23 78 45 8 32 56 After pass 1 23 45 78 8 32 56 After pass 2 After pass 3 8 23 45 78 32 56 8 23 32 45 78 56 After pass 4 After pass 5 8 23 32 45 56 78
Chèn trực tiếp
Chèn trực tiếp void 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 7
Nổi bọt void 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ùng
Bubble Sort cải tiến void 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