Bài giảng Cấu trúc dữ liệu và thuật toán - Phần 1: Giới thiệu về thuật toán - Chương 5: Sắp xếp - Nguyễn Duy Hiệp
3/29/2011
Nội dung
Bài toán sắp xếp
Chương 5
Sắp xếp
Một số thuật toán sắp xếp
Sắp xếp chèn – insertion sort
Sắp xếp lựa chọn – selection sort
Sắp xếp nổi bọt – bubble sort
Sắp xếp shell-sort
Sắp xếp trộn – merge sort
Sắp xếp nhanh – quick sort
Sắp xếp vun đống – heap sort
Bài toán sắp xếp
Bài toán sắp xếp
Để tìm kiếm thông tin hiệu quả ta phải lưu giữ chúng theo
một thứ tự nào đó.
Mỗi bản ghi có một khóa (key), ta có thể áp dụng các
phép so sánh < , > , <=, >=, ==, != trên khóa.
Cách sắp xếp sách trong thư viện
Lưu trữ từ trong từ điển
Sắp xếp các bản ghi bằng cách sắp xếp đối với khóa
tương ứng của chúng.
Sắp xếp là một trong những bài toán quan trọng trong xử
struct node
{
lý thông tin
Nhiều thuật toán đã được đề xuất.
long masoSV;
char hoten[30];
char diachi[50];
float diemTB;
};
Ta chỉ xét bài toán sắp xếp trong, không xét sắp xếp
ngoài
1
3/29/2011
Các phương pháp sắp xếp
cơ bản
Sắp xếp chèn
•Sắp xếp chèn
•Sắp xếp chèn
•Sắp xếp lựa chọn
•Sắp xếp nổi bọt
•Sắp xếp shellsort
•Cài đặt bằng mảng
•Cài đặt bằng danh sách moc nối
•Phân tích
•Bài tập
Sắp xếp chèn
Sắp xếp chèn
Sắp xếp bằng cách chèn:
Bắt đầu bằng một danh sách có thứ tự rỗng
Lần lượt chèn thêm các phần tử cần sắp xếp vào
danh sách có thứ tự đó. (Trong quá trình chèn phải
đảm bảo danh sách vẫn đúng thứ tự)
Kết thúc ta thu được danh sách các phần tử đã được
sắp xếp theo thứ tự
Chèn một phần tử mới vào một danh sách có thứ tự
VD. Danh sách các con vật sắp theo thứ tự bảng chữ cái
2
3/29/2011
Sắp xếp chèn
Sắp xếp chèn
Danh sách lưu trữ bằng mảng
Các phần tử cần sắp xếp: hen, cow, cat, ram, ewe, dog
cat
cat
cow
dog
ewe
hen
ram
cow
dog
ewe
hen
ram
cat
cow
ewe
hen
ram
0
1
2
3
4
MAX-1
cat
cow
hen
ram
……
cat
cow
hen
cow
hen
Còn trống
hen
Đã được xắp xếp
Thêm
hen
Thêm
cow
Thêm
cat
Thêm
ram
Thêm
ewe
Thêm
dog
Chỉ số phần tử cuối
(end)
Sắp xếp chèn
Sắp xếp chèn
Lưu trữ bằng mảng:
Hàm sắp xếp chèn, các phần tử cần sắp xếp được lưu ở
mảng B, kết quả được lưu ở mảng A, n là số phần tử
void insert (int A[], int &end, int value)
{
if(end==‐1)
{
void insertionSort(const int B[], int n, int A[])
{
int end=‐1;
for(int i=0; i<n; i++)
insert(A, end, B[i]);
}
end++;
A[end]=value;
}
else
{
int pos=0, i;
while(A[pos]<value) pos++;
for(i=end; i>=pos; i‐‐) A[i+1]=A[i];
A[pos]=value;
end=end+1;
}
}
3
3/29/2011
Sắp xếp chèn
Sắp xếp chèn
Lưu trữ bằng danh sách móc nối
Định nghĩa một nút
Phần tử cần
chèn
typedef struct node
{
pHead
NULL
long masoSV;
char hoten[30];
char diachi[50];
float diemTB; struct node *pNext;
} NODE;
pHead
NULL
Danh sách
NODE *list=NULL;
Sắp xếp chèn
Sắp xếp chèn
int insert(NODE *&pHead, long msSV, char ht[], char dc[], float diem)
{
NODE* ptr=(NODE*)malloc(sizeof(NODE));
ptr‐>masoSV=msSV;
strcpy(ptr‐>hoten,ht);
strcpy(ptr‐>diachi,dc);
ptr‐>diemTB = diem;
else
{
NODE *preQ=pHead;
NODE *q=pHead‐>pNext;
while(q!=NULL && q‐>masoSV < msSV)
{
if(pHead==NULL)
{
ptr‐>pNext=NULL;
pHead=ptr;
}
else
preQ=q;
q=q‐>pNext;
}
ptr‐>pNext=q;
preQ‐>pNext=ptr;
{
}
if(pHead‐>masoSV >= msSV)
{
ptr‐>pNext=pHead;
pHead=ptr;
}
}
}
4
3/29/2011
Phân tích
Phân tích
Thời gian thực hiện thuật toán chèn chính bằng tổng thời
gian thực hiện các phép chèn vào danh sách có thứ tự.
Trong trường hợp cài đặt bằng mảng:
Số lệnh và phép so sánh thực hiện :
Trong trường hợp cài đặt bằng mảng:
Danh sách rỗng thì cần 1 so sánh + 2 phép gán
Tại thời điểm danh sách có end (0≤i<n) phần tử cần:
. 1 phép so sánh
Danh sách rỗng
Danh sách khác rỗng
O(1)
O(n2)
. (i-k+1) phép so sánh và k phép dịch chuyển vị trí
(k là vị trí cần chèn) tổng là i
n1
n(n 1)
T(n) O(1) i O(1)
O(n2 )
. Hai phép gán
2
i1
n là số lượng phần tử cần sắp xếp
Phân tích
Phân tích
Trường hợp sử dụng danh sách móc nối
Khi cài đặt trên mảng, số lượng các phần tử phải dịch là
lớn, nhất là khi sắp xếp với số lượng phần tử lớn, làm
ảnh hưởng rất nhiều tới hiệu quả của thuật toán
Nếu danh sách rỗng cần 5 lệnh gán + 1 so sánh + 2
gán
Khi áp dụng trên danh sách móc nối thì không phải thực
hiện dịch chuyển phần tử mà chỉ thay đổi giá trị một vài
con trỏ
Danh sách khác rỗng (có k>0 phần tử) vòng lặp while
thực hiện j lần (1≤j≤k) trung bình là k/2
Giá trị của k sẽ là từ 1 đến n-1 (số lượng phần tử).
Sắp xếp chèn hiệu quả khi thực hiện trên danh sách móc
nối !
Vậy
n1
j
n(n 1)
T(n) O(1)
O(1)
O(n2 )
j1 2
4
5
3/29/2011
Bài tập
Bài tập 1: Trường hợp tồi nhất của thuật toán sắp xếp
chèn (số lượng phép so sánh phải thực hiện lớn nhất).
Và trường hợp tốt nhất.
Sắp xếp lựa chọn
Bài tập 2: Minh họa từng bước thuật toán sắp xếp chèn
đối với các dãy sau theo thứ tự tăng dần:
a) 26 33 35 29 19 12 22
b) 12 19 33 26 29 35 22
c) 12 14 36 41 60 81
d) 81 60 41 36 14 12
•Sắp xếp lựa chọn
•Cài đặt
•Phân tích
•Bài tập
e) Tim Dot Eva Roy Tom Kim Guy Amy Jon Ann Jim
Kay Ron Jan
Sắp xếp lựa chọn
Sắp xếp lựa chọn
3
5
2
7
8
5
1
Dãy ban đầu
Nhược điểm của thuật toán chèn: cần rất nhiều thao
tác di chuyển các bản ghi trong trường hợp lưu trữ bằng
mảng.
Bước 1
Bước 2
Bước …
3
3
5
5
2
2
7
7
8
1
5
5
1
8
3
3
5
5
2
2
7
5
1
1
5
7
8
8
Kích thước bản ghi lớn, gồm nhiều trường và lưu trữ liên
tục tốc độ thực hiện sẽ bị ảnh hưởng rất lớn.
Khắc phục bằng phương pháp sắp xếp lựa chọn
3
5
2
5
1
7
8
Dãy cuối cùng
1
2
3
5
5
7
8
6
3/29/2011
Sắp xếp lựa chọn
Sắp xếp lựa chọn
void SelectionSort(NODE A[], int n)
{
Một phần tử:
int i,j;
int pos;
for(i=n‐1;i>=1;i‐‐)
{
typedef struct node
{
char hoten [30];
float diem;
} NODE;
pos=0;
for(j=1;j<=i;j++)
{
if(A[j].diem > A[pos].diem) pos=j;
}
swap(A,pos,i);
}
}
Sắp xếp lựa chọn
Phân tích
Hàm swap
Vòng lặp ngoài cùng với biến chạy i thực hiện n-1 lần.
Vòng lặp bên trong
void swap(NODE A[], int pos, int i)
{
Lần thứ nhất thực hiện n-1 lần
Lần thứ hai thực hiện n-2 lần
….
char tmp[30];
float d;
strcpy(tmp,A[pos].hoten);
strcpy(A[pos].hoten,A[i].hoten);
strcpy(A[i].hoten,tmp);
Lần thứ i thực hiện n-i lần
n(n 1)
d=A[pos].diem;
A[pos].diem=A[i].diem;
A[i].diem=d;
T(n) (n 1) (n 2) ..1
O(n2 )
2
}
7
3/29/2011
Phân tích
Bài tập
Sắp xếp lựa chọn giảm số lần phải dịch chuyển dữ liệu
tới mức tối thiểu.
Bài tập 1. Minh họa sắp xếp lựa chọn trên các dãy
a) 26 33 35 29 19 12 22 theo thứ tự tăng
b) 12 19 33 26 29 35 22 theo thứ tự giảm
Cho hiệu quả tốt khi áp dụng sắp xếp với cấu trúc dữ liệu
lưu trữ liên tiếp trong bộ nhớ (VD. Mảng)
c) Tim Dot Eva Roy Tom Kim Guy Amy Jon Ann Jim Kay
Không hiệu quả so với sắp xếp chèn khi thực hiện trên
danh sách móc nối đơn!
Ron Jan theo thứ tự tăng của bảng chữ cái
Bài tập 2. viết lại hàm sắp xếp lựa chọn trên mảng để có
thể đếm được số lần hoán đổi dữ liệu.
Tại sao lại kém
hiệu quả hơn
sắp xếp chèn
trên danh sách
móc nối ?
Bài tập 3. Áp dụng hàm đếm số lần hoán đổi dữ liệu khi
thực hiện sắp xếp chèn và lựa chọn trên mảng để so
sánh hiệu quả của 2 phương pháp với 1 mảng số đầu
vào có n phần tử (n=1000) sinh ngẫu nhiên
Sắp xếp nổi bọt
Dựa trên ý tưởng trong tuyển quặng: "Quặng nặng thì
chìm xuống dưới còn tạp chất nhẹ thì nổi lên trên"
Thực hiện so sánh lần lượt các phần tử nằm kề nhau,
nếu chúng không đúng thứ tự thì ta đổi chỗ chúng cho
nhau.
Sắp xếp nổi bọt
các phần tử có giá trị khóa lớn sẽ bị đẩy về cuối và khóa
nhỏ sẽ bị đẩy lên trên (trong trường hợp sắp xếp tăng
dần)
•Sắp xếp nổi bọt
•Cài đặt
•Phân tích
•Bài tập
8
3/29/2011
Sắp xếp nổi bọt
Sắp xếp nổi bọt
Dãy ban đầu
3
5
2
7
1
3
2
5
1
7
2
Lần lặp 2
3
2
5
1
7
3
3
5
1
1
5
7
7
3
3
5
5
2
2
7
7
1
1
lần lặp 1
3
2
5
7
1
2
2
3
3
5
5
1
1
7
7
3
3
2
2
5
5
7
7
1
1
2
3
2
5
1
7
2
3
1
5
7
kết thúc lần lặp 2
3
2
5
1
7
kết thúc lần lặp 1
Sắp xếp nổi bọt
Sắp xếp nổi bọt
Lần lặp 3
Lần lặp 4
3
2
1
5
7
2
1
3
5
7
2
1
3
5
7
1
2
3
5
7
3
2
2
1
1
5
5
7
7
2
3
1
5
7
7
3
2
1
3
5
1
2
3
5
7
kết thúc lần lặp 4
2
1
3
5
7
kết thúc lần lặp 3
Dãy đã được sắp xếp !
9
3/29/2011
Sắp xếp nổi bọt
Phân tích
void BubbleSort(int A[], int n)
{
O (n 2 )
Giống như sắp xếp lựa chọn, thời gian thực hiện cỡ
int i,j;
for(i=n‐1;i>0;i‐‐)
Số lần thực hiện đổi chỗ các phần tử là nhiều hơn so với
sắp xếp lựa chọn.
for(j=1;j<=i;j++)
{
không hiệu quả khi thực hiện trên danh sách với kích
thước lớn
if(A[j]<A[j‐1])
{
int k=A[j];
A[j]=A[j‐1];
A[j‐1]=k;
}
}
}
Bài tập
Bài tập 1. mô phỏng hoạt động của thuật toán sắp xếp
nổi bọt với các dãy sau
a) 26 33 35 29 19 12 22 theo thứ tự tăng
b) 12 19 33 26 29 35 22 theo thứ tự giảm
Shellsort
c) Tim Dot Eva Roy Tom Kim Guy Amy Jon Ann Jim Kay
Ron Jan theo thứ tự tăng của bảng chữ cái
•Shellsort
•Cài đặt
Bài tập 2. Cải tiến hàm BubbleSort để có thể đếm được
số lần thực hiện đổi chỗ các phần tử
•Phân tích
•Bài tập
10
3/29/2011
Shellsort
Shellsort
Trong các phương pháp sắp xếp trên thì:
Sắp xếp chèn phải di chuyển nhiều phần tử vì nó chỉ di
chuyển các phần tử nằm gần nhau, nếu ta di chuyển các
phần tử ở xa thì hiệu quả thu được sẽ tốt hơn
Sắp xếp lựa chọn thực hiện việc di chuyển phần tử ít
nhất, tuy nhiên nó vẫn phải thực hiện nhiều phép so
sánh không cần thiết
Sắp xếp chèn (trong trường hợp tốt nhất) phải thực
hiện ít phép so sánh nhất
D. L. SHELL(1959) đề xuất phương pháp sắp xếp
diminishing-increment sort (sắp xếp độ tăng giảm dần),
thường gọi là shellsort
Cải tiến các phương pháp sắp xếp trên để tránh được
các nhược điểm đó
Shellsort
Shellsort
Ý tưởng của shellsort:
Ban đầu so sánh và sắp xếp các khóa ở cách nhau k vị
trí
Sau mỗi lần sắp xếp hết các phần tử cách nhau k vị trí
trong dãy ta cho k giảm đi
Giá trị cuối cùng của k=1, ta chỉ việc sắp xếp các phần
tử kề nhau, và dãy thu được sau bước này chính là dãy
đã được sắp xếp
Để sắp xếp các phần tử ta sử dụng phương pháp sắp xếp
Ban đầu các phần tử cách nhau 5 vị trí được sắp xếp,
sau đó đến các phần tử cách nhau 3 vị trí, và cuối cùng là
các phần tử nằm cạnh nhau (cách 1 vị trí)
chèn
Dãy các số k được gọi là một dãy tăng(hoặc chuỗi khoảng
cách)
VD: 5, 3, 1 hoặc 1, 4, 10
11
3/29/2011
Shellsort
Shellsort
void InsertIncSort(int A[], int n, int inc)
{
int i,j,count,pos,tmp;
for(i=0; i<inc; i++) //duyet het cac phan tu
{
void shellSort(int A[], int n)
{
count = (n‐1‐i)/inc; //so luong phan tu
for(j=0; j<count; j++) //sap xep chen
{
InsertIncSort(A,n,5);
InsertIncSort(A,n,2);
InsertIncSort(A,n,1);
tmp=A[i+(j+1)*inc];
pos=i+(j+1)*inc;
while(((pos‐inc)>=0)&&(A[pos‐inc]>tmp))
{
}
A[pos]=A[pos‐inc];
pos=pos‐inc;
}
A[pos]=tmp;
}
}
}
Phân tích
Bài tập
Cách chọn dãy tăng ảnh hưởng tới thời gian thực hiện của
thuật toán ShellSort
Bài tập 1: Giải thích tại sao ShellSort không dùng được với
danh sách móc nối.
Dãy tăng gồm các mũ của 2 là dãy tăng tồi nhất
(VD. 8, 4, 2, 1): thời gian thực hiện bằng thời gian thực
hiện insertionSort
Bài tập 2: Minh họa ShellSort với dãy tăng 1,4,10 khi thực
hiện trên các dãy số sau:
Thời gian thực hiện tồi nhất: O(n2) với dãy tăng là ban
đầu là n/2 sau đó giảm dần bằng cách chia đôi cho tới 1
a) 32, 95, 16, 82, 24, 66, 35, 19, 75, 54, 40, 43, 93, 68, 98, 23
b) 3, 7, 9, 0, 5, 1, 6, 8, 4, 2, 0, 6, 1, 5, 7, 3, 4, 9, 8, 2
c) 20, 18, 17, 15, 14, 13, 12, 9, 8, 5, 2, 1
k
O(n3/2 )
Thời gian thực hiện tồi nhất:
với dãy tăng
2 1
i
i
94i 92i 1
4/3
O(n )
với dãy tăng
hoặc
4 32 1
2
2i3j
với dãy tăng
O(nlog n)
Dãy tốt nhất : 1, 4, 10, 23, 57, 132, 301, 701, 1750
12
3/29/2011
Các phương pháp sắp xếp
nâng cao
Sắp xếp trộn – mergeSort
(John von Neumann 1945)
•Sắp xếp trộn – MergeSort
•Sắp xếp nhanh – QuickSort
•Sắp xếp đống – HeapSort
•Sắp xếp trộn
•Cài đặt
•Phân tích
•Bài tập
Sắp xếp trộn
Sắp xếp trộn
Danh sách cần sắp xếp ban đầu là :
Mỗi danh sách chứa 1 phần tử là danh sách đã sắp xếp.
26 33 35 29 19 12 22
Bước tiếp theo (bước trộn) ta lần lượt trộn các danh
sách con lại với nhau để được danh sách có thứ tự.
Ban đầu (bước chia) ta chia đôi danh sách thành các danh
sách con, với mỗi danh sách con ta lại chia đôi cho đến khi
các danh sách con chỉ có một phần tử
Danh sách sau
khi chia
Danh sách ban đầu
Trộn lần 1
Chia lần 1
Chia lần 2
Trộn lần 2
Trộn lần 3
Chia lần 3
13
3/29/2011
Sắp xếp trộn
Sắp xếp trộn
Cài đặt trên danh sách móc nối
typedef struct node
{
int data;
struct node *pNext;
} NODE;
Cây đệ quy của sắp xếp trộn của danh sách
26 33 35 29 19 12 22
Sắp xếp trộn
Sắp xếp trộn
Hàm chia tách danh sách thành 2 nửa
void merge(NODE *first, NODE *second, NODE *&third)
{
NODE *ptr;
void split(NODE *&first, NODE *&second)
{
third=(NODE*)malloc(sizeof(NODE));
third‐>pNext=NULL;
ptr=third;
NODE *start=first;
NODE *end=first‐>pNext;
while(end‐>pNext!=NULL && end‐>pNext‐>pNext!=NULL)
{
NODE *p=first;
NODE *q=second;
while(p!=NULL && q!=NULL)
{
start = start‐>pNext;
end = end‐>pNext‐>pNext;
}
if(p‐>data <= q‐>data)
{
second = start‐>pNext;
start‐>pNext=NULL;
ptr‐>pNext=p;
p=p‐>pNext;
}
ptr=ptr‐>pNext;
ptr‐>pNext=NULL;
}
14
3/29/2011
Sắp xếp trộn
Sắp xếp trộn
else
{
void MergeSort(NODE *&pHead)
{
ptr‐>pNext=q;
q=q‐>pNext;
ptr=ptr‐>pNext;
ptr‐>pNext=NULL;
if(pHead!=NULL && pHead‐>pNext!=NULL)
{
NODE *second=NULL;
split(pHead,second);
MergeSort(pHead);
MergeSort(second);
NODE *third=NULL;
merge(pHead,second,third);
pHead=third;
}
}
if(p==NULL) ptr‐>pNext=q;
else ptr‐>pNext=p;
ptr=third;
third=third‐>pNext;
free(ptr);
}
}
}
Sắp xếp trộn
Sắp xếp trộn
Phân tích thao tác chia:
Mỗi lần chia đôi ta phải duyệt hết danh sách
Danh sách ban đầu có n phần tử thì cần thực hiện n
lần duyệt.
Lần chia thứ nhất danh sách chia thành 2 danh sách
con n/2 phần tử. Mỗi danh sách con khi chia nhỏ ta
cũng phải duyệt n/2 lần tổng là n/2+ n/2 =n lần
….
Tổng cộng mỗi lần chia phải thực hiện n thao tác
duyệt, mà có logn lần chia vậy độ phức tạp của thao
tác chia là O(nlogn)
15
3/29/2011
Sắp xếp trộn
Sắp xếp trộn
Phân tích: trong thao tác kết hợp
Độ phức tạp tính toán trung bình của sắp xếp trộn là O(nlogn)
Đánh giá thời gian thực hiện thuật toán thông qua số
lượng phép so sánh.
Trong trường hợp cài đặt với danh sách liên tục (VD. Mảng)
thì ta gặp vấn đề khó khăn với thao tác kết hợp là:
Tại một mức số lượng phép so sánh tối đa không thể
vượt số lượng phần tử của danh sách con tại mức đó
Phải sử dụng thêm bộ nhớ phụ (dùng mảng phụ để tránh
phải dịch chuyển các phần tử)
Mức nhỏ nhất là logn thì có n danh sách con, để kết
hợp thành n/2 danh sách cần n nhiều nhất phép so
sánh
Nếu không sử dụng bộ nhớ phụ thì thời gian thực hiện là
O(n2) – chi phí cho việc dịch các phần tử trong mảng
Chương trình viết phức tạp hơn so với dùng danh sách
móc nối
….
Tổng cộng mỗi mức phải thực hiện nhiều nhất n phép
so sánh, mà có logn mức nên thời gian thực hiện
thao tác kết hợp cỡ O(nlogn)
Bài tập
Bài tập 1. Minh họa MergeSort (vẽ cây đệ quy) cho các
danh sách sau
a) Tim Dot Eva Roy Tom Kim Guy Amy Jon Ann Jim
Kay Ron Jan
Sắp xếp nhanh – QuickSort
(C. A. R. Hoare 1962)
b) 32, 95, 16, 82, 24, 66, 35, 19, 75, 54, 40, 43, 93, 68
•Sắp xếp nhanh
•Cài đặt
Bài tập 2. Cài đặt MergerSort cho trường hợp sắp xếp
trên mảng. Gợi ý: sử dụng thêm một danh sách phụ để
lưu trữ.
•Phân tích
•Bài tập
16
3/29/2011
Sắp xếp nhanh
Sắp xếp nhanh
Ý tưởng: giống như sắp xếp trộn là chia danh sách thành
2 phần, tuy nhiên trong sắp xếp nhanh ý tưởng chia khác
một chút.
Dãy ban đầu
26 33 35 29 12 22
Một phần tử trong danh sách được chọn làm phần tử
‘chốt’ (thường là phần tử đầu danh sách).
Chọn chốt 26,
26
12 22
33 35 29
dãy chia làm 2
phần
Danh sách sau đó được chia thành 2 phần, phần đầu
gồm các phần tử nhỏ hơn hoặc bằng chốt, phần còn
lại là các phần tử lớn hơn chốt.
26
12
22
33
29
35
Chia tiếp 2 dãy con
Kết hợp 2 dãy con
và khóa
Sau đó hai danh sách con lại được chọn chốt và chia
tiếp cho đến khi danh sách con chỉ có 1 phần tử
26
12 22
29 33 35
Cuối cùng ta kết hợp 2 danh sách con và phần tử
chốt từng mức lại ta được danh sách đã sắp xếp
12 22 26 29 33 35
Sắp xếp nhanh
Sắp xếp nhanh
Sắp xếp nhanh trên mảng: Cách chia danh sách với phần
tử chốt
void qSort(int A[], int start, int end)
{
//chon phan tu dau lam chot
if(start<end) //co nhieu hon 1 phan tu
{
25 23 35 29 24 22
25 23 35 29 24 22
25 23 22 24 29 35
int p,q,tmp;
25 23 22 24 29 35
p=start; q=end;
while(p<q)
{
25 23 35 29 24 22
25 23 22 29 24 35
25 23 22 29 24 35
24 23 22 25 29 35
while(A[p]<=A[start]) p++;
while(A[q]>A[start]) q‐‐;
24 23 22
25
29 35
17
3/29/2011
Sắp xếp nhanh
Sắp xếp nhanh
if(p<q)
{
Hàm thực hiện QuickSort
tmp=A[p];
A[p]=A[q];
A[q]=tmp;
void quickSort(int A[], int n)
}
}
{
qSort(A,0,n‐1);
tmp=A[start];
A[start]=A[q];
A[q]=tmp;
}
//goi de quy
qSort(A,start,q‐1);
qSort(A,q+1,end);
}
}
Phân tích
Phân tích
Cách chọn chốt ảnh hưởng đến việc chia danh sách. Ví dụ
xét danh sách : 13, 14, 12, 19, 21, 17, 54, 71
Chọn chốt:
Cách chọn tồi nhất: chọn phần tử có khóa lớn nhất,
hoặc nhỏ nhất là chốt
13
19
21,54,71
13,14,12,17
12
14
54
14,19,21,17,54,71
19,21,17,54,71
Chọn chốt tốt nhất : chọn khóa mà chia dãy thành 2
phần đều nhau
14
21
71
19
12
17
Số lượng phép so sánh và đổi chỗ
C(n) số lượng phép so sánh
17
21
13
21,54,71
C(n) n 1 C(r) C(n r 1)
S(n) số lượng phép đổi chỗ
C(1) C(0) 0
n 2
54
54,71
Chọn chốt là phần
tử giữa
Chọn chốt là phần
tử đầu
S(n) p 1 S(p 1) S(n p)
71
18
3/29/2011
Phân tích
Phân tích
Trong trường hợp tồi nhất
Trong trường hợp trung bình
C(n) n 1 C(0) C(n 1) n 1 C(n 1)
C(n) 1.39nlog n O(n)
n(n 1)
C(n) n 1 n 2 ..1 0
2
S(n) 0.69nlog n O(n)
S(n) n 1 S(n 1)
(n 1)(n 2)
Độ phức tạp của thuật toán QuickSort
Trong trường hợp tồi nhất O(n2)
Trường hợp trung bình O(nlogn)
S(n) (n 1) n ..3
3
S(2) 3
2
Phân tích
Bài tập
QuickSort tồi hơn sắp xếp chèn với mảng kích thước nhỏ,
nên chỉ dùng khi mảng có kích thước lớn
Bài tập 1. Minh họa QuickSort cho các danh sách sau
(với 2 cách chọn chốt là đầu và chốt giữa)
Hiệu quả phụ thuộc vào cách chọn chốt, có nhiều
phương pháp chọn chốt : chốt đầu, giữa, ngẫu nhiên,
trung vị của 3 khóa …
a) Tim Dot Eva Roy Tom Kim Guy Amy Jon Ann Jim
Kay Ron Jan
So với sắp xếp trộn-mergerSort (cài đặt trên mảng) thì
QuickSort cho hiệu quả tốt hơn
b) 32, 95, 16, 82, 24, 66, 35, 19, 75, 54, 40, 43, 93, 68
c) 8, 8, 8, 8, 8 ,8 (các phần tử bằng nhau)
Không phải sử dụng bộ nhớ phụ
Không cần thực hiện thao tác trộn
Bài tập 2. Cải tiến hàm quickSort để có thể đếm được số
phép so sánh và dịch chuyển phần tử.
Nhưng kém hơn so với mergesort cài đặt trên danh sách
móc nối tương ứng
19
3/29/2011
Bài tập
Sắp xếp vun đống
Bài tập 3. Cải tiến thuật toán QuickSort để có thể tìm
HeapSort
được phần tử lớn nhất thứ k trong danh sách gồm n phần
tử.
•Đống
•Sắp xếp vun đống
•Cài đặt
•Phân tích
•Bài tập
HeapSort
HeapSort
2-tree : là cây nhị phân mà các nút trong (internal node)
đều có đầy đủ 2 con
Định nghĩa đống – Heap:
là 2-tree cân bằng,
lệch trái – left justified (nút lá xếp đầy phía bên trái
trước)
Không nút con nào có giá trị lớn hơn giá trị nút cha
của nó
Khái niệm Heap này khác với khái niệm vùng nhớ rỗi
HEAP trong tổ chức bộ nhớ của chương trình
Heap không phải là một cây nhị phân tìm kiếm
20
Tải về để xem bản đầy đủ
26 trang
19840
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Cấu trúc dữ liệu và thuật toán - Phần 1: Giới thiệu về thuật toán - Chương 5: Sắp xếp - Nguyễn Duy Hiệp", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_cau_truc_du_lieu_va_thuat_toan_phan_1_gioi_thieu_v.pdf
