Xem mẫu
- Cấu trúc dữ liệu và giải thuật
Bài 7. Các phương pháp sắp xếp khác
Giảng viên: TS. Ngo Huu Phuc
Tel: 0438 326 077
Mob: 098 5696 580
Email: ngohuuphuc76@gmail.com
1 Ngo Huu Phuc, Le Quy Don Technical University
- Bài 7. Các phương pháp sắp xếp khác
Nội dung:
7.1. ShellSort (8)
7.2. MergeSort (9)
7.3. BucketSort (5)
7.4. RadixSort (6)
Tham khảo:
1. Bucket sort.htm
2. Merge Sort.htm
3. Radix sort.htm
4. ShellSort.htm
5. Bài giảng của TS Nguyên Nam Hồng
2 Ngo Huu Phuc, Le Quy Don Technical University
- 7.1. ShellSort (1/8)
Phương pháp này được Donald Shell giới thiệu
năm 1959.
Với phương pháp sắp xếp chèn: thực hiện ít phép
toán so sánh, nhưng sử dụng nhiều phép di
chuyển thừa.
Với phương pháp sắp xếp chọn: thực hiện ít phép
toán di chuyển, nhưng sử dụng nhiều phép so
sánh.
Có thể có phương pháp hiệu quả hơn không?
3 Ngo Huu Phuc, Le Quy Don Technical University
- 7.1. ShellSort (2/8)
Phương pháp sắp xếp ShellSort còn được gọi là
phương pháp sắp xếp giảm độ tăng - diminishing
increment sort.
Phương pháp sử dụng một dãy tăng: h1, h2, .. ht
Dãy tăng được bắt đầu từ 1, tối đa đến N-1 (trong thực
tế đến N/2). Chưa có đề xuất dãy như thế nào tốt nhất.
Trong dãy này, không nên ch ọn các số là bội của nhau.
Dãy này còn được gọi là dãy khoảng cách, ví dụ 1,3,5.
4 Ngo Huu Phuc, Le Quy Don Technical University
- 7.1. ShellSort (3/8)
Ví dụ: với 13 phần tử, dãy khoảng cách là 1,3,5
STT 0 1 2 3 4 5 6 7 8 9 10 11 12
Ban
81 94 11 96 12 35 17 95 28 58 41 75 15
đầu
KC
35 17 11 28 12 41 75 15 96 58 81 94 95
=5
KC
28 12 11 35 15 41 58 17 94 75 81 96 95
=3
KC
11 12 15 17 28 35 41 58 75 81 94 95 96
=1
5 Ngo Huu Phuc, Le Quy Don Technical University
- 7.1. ShellSort (4/8)
#include for(int i=0;i
- 7.1. ShellSort (5/8)
void printlist(int* list,int n) void shellsort(int *list, int n, int *incs, int t)
{ {
int i; int i,j,k,h;
printf("Cac phan tu cua mang: \n");
int temp;
for(i=0;i0; k--)
printf("%d\t",list[i]);
for(h=incs[k], i=h; i=h && list[j-h]>temp)
{
list[j]=list[j-h];
j-=h;
}
list[j]=temp;
}
}
7 Ngo Huu Phuc, Le Quy Don Technical University
- 7.1. ShellSort (6/8)
Tính hiệu quả của thuật toán ShellSort?
Phụ thuộc vào mảng khoảng cách.
Dạng mặc định, do Shell đề xuất:
ht = N/2, hk = hk+1/2 …
Độ phức tạp của thuật toán - O(N2)
8 Ngo Huu Phuc, Le Quy Don Technical University
- 7.1. ShellSort (7/8)
Dãy khoảng cách của Hibbards:
Hk = 2k-1 i.e. 1, 3, 7,
Độ phức tạp: O(N1.5)
Dãy khoảng cách của Sedgewicks:
Có một số dạng được giới thiệu, nổi tiếng trong
đó có 2 dạng:
9 * 4i – 9 * 2i + 1, và 4i – 3 * 2i + 1
Độ phức tạp: O(N4/3)
9 Ngo Huu Phuc, Le Quy Don Technical University
- 7.1. ShellSort (8/8)
Độ phức tạp của ShellSort trong trường hợp tồi nhất:
O(N2)
Độ phức tạp của ShellSort trong trường hợp tốt nhất:
~ O(N)
Độ phức tạp của ShellSort trong trường hợp trung
bình: ~ O(N7/6)
10 Ngo Huu Phuc, Le Quy Don Technical University
- 7.2. Mergesort (1/9)
MergeSort là một thuật toán sắp xếp cho độ phức
tạp tương đương với Quick Sort.
Ý tưởng:
Ý tưởng cơ bản của MergeSort là nối 2 mảng đã
sắp xếp với kích thước m và n thành mảng mới
có kích thước (m+n).
11 Ngo Huu Phuc, Le Quy Don Technical University
- 7.2. Mergesort (2/9)
Các bước thực hiện:
Bắt đầu từ một mảng có 1 phần tử, nối với mảng thứ hai cũng
có 1 phần tử để tạo thành mảng mới có 2 phần tử.
Một cách tương tự, ta nối mảng ba và mảng bốn để được
mảng mới có 2 phần tử, tiếp tục như trên cho đến khi hết, như
vậy ta đã thực hiện xong một lần sắp xếp (one pass).
Tiếp theo, nối hai mảng có kích thước 2 phần tử lại để được
một mảng có kích thước 4 phần tử. Đến khi kết thúc, ta đã qua
lần sắp xếp thứ hai.
Tiếp tục quá trình trên cho đến khi chỉ còn 1 mảng, khi đó mảng
đã được sắp xếp!!!
12 Ngo Huu Phuc, Le Quy Don Technical University
- 7.2. Mergesort (3/9)
Hoạt động của thuật toán MergeSort
13 Ngo Huu Phuc, Le Quy Don Technical University
- 7.2. Mergesort (4/9)
Để thực hiện được thuật toán này cần thiết xây
dựng:
Một hàm cho phép nối 2 mảng có kích thước m và n
thành mảng có kích thước (m+n).
Cần thêm một hàm cho biết đã nối các mảng liền kề hay
chưa?
14 Ngo Huu Phuc, Le Quy Don Technical University
- 7.2. Mergesort (5/9)
#include mergesort(list,n-1);
#include printf("Cac phan tu cua mang sau khi sap
#include xep:\n");
#include printlist(list,n);
#define MAX 100 getch();
void readlist(int list[],int n); }
void printlist(int list[],int n); void readlist(int list[],int n)
void merge(int list[],int listtemp[],int k,int m,int n);
{
void mpass(int list[],int listtemp[],int l,int n);
int i;
void mergesort(int list[], int n );
printf("Nhap cac phan tu cho mang\n");
void main() {
srand( (unsigned)time(NULL));
int list[MAX], n;
printf("Nhap so phan tu cho mang\n"); for(i=0;i
- 7.2. Mergesort (6/9)
void printlist(int list[],int n) while( i
- 7.2. Mergesort (7/9)
while(i
- 7.2. Mergesort (8/9)
void mergesort(int list[], int n )
{
int l;
int listtemp[MAX];
l =1;
while (l
- 7.2. Mergesort (9/9)
Phân tích độ phức tạp của thuật toán MergeSort:
Trong trường hợp tồi nhất: O(N log N)
Trong trường hợp tốt nhất: O(N log N)
Trong trường hợp trung bình: O(N log N)
Vì sao?
Nếu n là kích thươc của mảng cần sắp xếp, mỗi lần sắp
các nhóm con, độ phức tạp sẽ là O(n), hơn nữa số lần lặp
lại quá trình sắp trên là log2n.
Cho tất cả các trường hợp, độ phức tạp của Merge Sort là
O(n log2(n)), tuy nhiên cần sử dụng thêm một mảng có
kích thước n nữa
19 Ngo Huu Phuc, Le Quy Don Technical University
- 7.3. Bucket sort (1/6)
Giả sử các giá trị cần sắp nằm trong khoảng: 0.. m
Thuật toán Bucket Sort thực hiện:
Khởi tạo m chiếc thùng (buckets) được đánh số: 0 … m.
Kiểm tra từng phần tử S[i] trong danh sách S và đưa vào
thùng thứ i.
Như vậy, ta có m thùng với các giá trị đã được đưa vào theo
đúng trật tự.
Sau đó, sắp lại các phần tử theo từng thùng, dựa trên chỉ số
của thùng.
Phương pháp này không cần phép toán so sánh.
20 Ngo Huu Phuc, Le Quy Don Technical University
nguon tai.lieu . vn
