6.1. Thuật toán QuickSort (1/6)
Giải thuật Quick-sort là
phương pháp sắp xếp dựa
trên chiến lược chia để trị.
Giải thuật gồm các bước:
Phép chia: chọn ngẫu nhiên
một phần tử x làm khóa,
chia tập dữ liệu S ban đầu
thành 3 phần:
L chứa các phần tử nhỏ hơn x
E chứa các phần tử bằng x
G chứa các phần tử lớn hơn x
Bước lặp: sắp xếp 2 tập L
và G
Hiệu chỉnh lại các tập L, E
và G
6.1. Thuật toán QuickSort (1/6)
Giải thuật Quick-sort là
phương pháp sắp xếp dựa
trên chiến lược chia để trị.
Giải thuật gồm các bước:
Phép chia: chọn ngẫu nhiên
một phần tử x làm khóa,
chia tập dữ liệu S ban đầu
thành 3 phần:
L chứa các phần tử nhỏ hơn x
E chứa các phần tử bằng x
G chứa các phần tử lớn hơn x
Bước lặp: sắp xếp 2 tập L
và G
Hiệu chỉnh lại các tập L, E
và G
27 trang |
Chia sẻ: thanhle95 | Lượt xem: 745 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệu Bài giảng Cấu trúc dữ liệu và giải thuật - Bài 6: Sắp xếp nhanh - Quick Sorts - Ngô Hữu Phước, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Lecturer: PhD. Ngo Huu Phuc
Tel: 0438 326 077
Mob: 098 5696 580
Email: ngohuuphuc76@gmail.com
Cấu trúc dữ liệu và giải thuật
Bài 6. Sắp xếp nhanh - Quick Sorts
Ngo Huu Phuc, Le Quy Don Technical University1
Bài 6. Quick Sorts
Nội dung:
6.1. Thuật toán QuickSort (6)
6.2. Ví dụ về QuickSort (7)
6.3. Hoạt động của QuickSort (6)
6.4. Hiệu quả của QuickSort (6)
Tham khảo:
1. Intro to Algorithms Chapter 8 QuickSort.htm
2. Lecture 5 – quicksort.htm
3. Quick Sort.htm
4. Bài giảng của TS Nguyễn Nam Hồng
Ngo Huu Phuc, Le Quy Don Technical University2
6.1. Thuật toán QuickSort (1/6)
Giải thuật Quick-sort là
phương pháp sắp xếp dựa
trên chiến lược chia để trị.
Giải thuật gồm các bước:
Phép chia: chọn ngẫu nhiên
một phần tử x làm khóa,
chia tập dữ liệu S ban đầu
thành 3 phần:
L chứa các phần tử nhỏ hơn x
E chứa các phần tử bằng x
G chứa các phần tử lớn hơn x
Bước lặp: sắp xếp 2 tập L
và G
Hiệu chỉnh lại các tập L, E
và G
Ngo Huu Phuc, Le Quy Don Technical University3
x
x
L GE
x
6.1. Thuật toán QuickSort (2/6)
Các bước cơ bản của thuật toán:
Chia tập dữ liệu ban đầu thành 2 tập con:
sao cho, tất cả các phần tử bên trái nhỏ hơn tất
cả các phần tử bên phải.
Sắp xếp 2 tập con một cách độc lập và nối chúng
lại với nhau:
như vậy, ta được dãy đã sắp xếp.
Ngo Huu Phuc, Le Quy Don Technical University4
6.1. Thuật toán QuickSort (3/6)
Với mỗi tập con trên, mỗi tập chia thành 02 tập
con nếu có thể
như vậy, ta có tối đa 04 tập con.
tập các phần tử nhỏ nhất ở bên trái cùng, tập
các phần tử lớn nhất ở bên phải cùng.
Lặp lại quá trình trên cho đến khi tập chỉ có 1
phần tử
nối tất cả các tập với nhau ta được dãy đã sắp
xếp.
Ngo Huu Phuc, Le Quy Don Technical University5
6.1. Thuật toán QuickSort (4/6)
Ta chia tập dữ liệu ban đầu như sau:
Trên tập S, lấy mỗi phần tử y được lấy ra khỏi
tập
Đưa phần tử y vào tập L, E hay G, tùy thuộc
vào phép so sánh với khóa x
Với mỗi phép lấy 1 phần tử và đưa chúng vào tập
tương ứng, độ phức tạp của phép toán đó là
O(1).
Như vậy, phép chia dữ liệu của thuật toán
QuickSort có độ phức tạp O(n).
Ngo Huu Phuc, Le Quy Don Technical University6
6.1. Thuật toán QuickSort (5/6)
Ngo Huu Phuc, Le Quy Don Technical University7
7 4 9 6 2 → 2 4 6 7 9
4 2 → 2 4 7 9 → 7 9
2 → 2 9 → 9
6.1. Thuật toán QuickSort (6/6)
Ngo Huu Phuc, Le Quy Don Technical University8
Việc thực thi giải thuật
QuickSort được mô tả qua
cây nhị phân:
Mỗi node biểu diễn một
lần gọi đệ quy và lưu giữ:
Dãy chưa được sắp xếp và
khóa.
Dãy sau khi sắp xếp.
Gốc của cây là lần gọi đệ
quy đầu tiên.
Các lá của cây là lần gọi
ứng với dãy con có kích
thước 0 hoặc 1.
6.2. Ví dụ về QuickSort (1/7)
Ngo Huu Phuc, Le Quy Don Technical University9
Chọn khóa
6.2. Ví dụ về QuickSort (2/7)
Ngo Huu Phuc, Le Quy Don Technical University10
Phân chia dãy ban đầu bằng gọi đệ quy với khóa đã chọn.
6.2. Ví dụ về QuickSort (3/7)
Ngo Huu Phuc, Le Quy Don Technical University11
Gọi đệ quy cho dãy con, với khóa mới
6.2. Ví dụ về QuickSort (4/7)
Ngo Huu Phuc, Le Quy Don Technical University12
Tương tự, gọi đệ quy, sau đó nối kết quả.
6.2. Ví dụ về QuickSort (5/7)
Ngo Huu Phuc, Le Quy Don Technical University13
Tương tự cho phần bên phải.
6.2. Ví dụ về QuickSort (6/7)
Ngo Huu Phuc, Le Quy Don Technical University14
Gọi đệ quy cho dãy con, với khóa mới
6.2. Ví dụ về QuickSort (7/7)
Ngo Huu Phuc, Le Quy Don Technical University15
Nối kết quả cho gốc của cây.
6.3. Hoạt động của QuickSort (1/6)
Có thể mô tả như sau:
Với tập ban đầu, chọn 1 phần tử làm khóa.
Đổi chỗ phần tử đầu tiên với khóa.
Sử dụng 2 chỉ số i và j để duyệt phần còn lại trên dãy.
Chỉ số i tăng đến khi tại vị trí i đó, phần tử này có giá trị lớn hơn
khóa. Chỉ số j giảm đến khi giá trị tại vị trí j nhỏ hơn khóa.
So sánh giữa i và j, nếu i<j, đổi chỗ 2 phần tử này cho nhau.
Nếu không, đổi chỗ khóa (phần tử đầu tiên) với phần tử j.
Khi đó, có thể chia mảng đã cho thành 2 mảng con, mảng thứ
nhất từ vị trí 1 đến vị trí j-1, mảng thứ 2 từ vị trí j+1 đến n. Sau
đó có thể lặp lại quá trình trên cho các mảng con.
Ngo Huu Phuc, Le Quy Don Technical University16
6.3. Hoạt động của QuickSort (2/6)
Chọn khóa:
Ta có thể chọn bất kỳ phần tử nào trong mảng làm khóa.
Nếu chọn phần tử đầu tiên của mảng làm khóa, lựa chọn này là tồi
nếu mảng đã sắp xếp. Khi đó, một mảng con có 0 phần tử. Thông
thường, chọn khóa gần với giữa của mảng với hi vọng lựa chọn này
sẽ cho 2 mảng con có số phần tử gần bằng nhau.
Ngo Huu Phuc, Le Quy Don Technical University17
Hàm chọn vị trí có dạng:
int getkeyposition(int i,int j)
{
return(( i+j )/ 2);
}
Việc chọn này cũng tùy ý, có
thể sử dụng hàm random để
chọn khóa. Hàm này có dạng:
int getkeyposition(int i, int j)
{
return(random number in the
range of i to j);
}
6.3. Hoạt động của QuickSort (3/6)
Xây dựng hàm đệ quy:
Hàm đệ quy cho giải thuật có thể gọi
QSort(S, a, b)
sắp dãy con trong dãy ban đầu S tử chỉ số a đến
chỉ số b.
Với QSort(L, 0, n-1) sắp mảng L từ phần tử
đầu tiên đến phần tử cuối n-1.
QSort(S, a, b) sẽ được gọi đệ quy cho các
mảng con nhỏ hơn, với chỉ số thay đổi.
Ngo Huu Phuc, Le Quy Don Technical University18
6.3. Hoạt động của QuickSort (4/6)
Chia dữ liệu:
Với khóa đã chọn x
Tổ chức lại tập S sao cho:
S[a]S[t-1] là các phần tử < x
S[t] = x
S[t+1]S[b] là các phần tử > p
Ngo Huu Phuc, Le Quy Don Technical University19
6.3. Hoạt động của QuickSort (5/6)
#include "stdio.h"
#include "conio.h"
#define MAX 100
void swap(int *x,int *y);
int getkeyposition(int i,int j);
void qsort(int list[],int m,int n);
void inputdata(int list[],int n);
void printlist(int list[],int n);
void main() {
int list[MAX], n;
printf("Nhap so phan tu cho mang\n");
scanf("%d",&n);
inputdata(list,n);
printf("Cac phan tu da nhap:\n");
printlist(list,n);
qsort(list,0,n-1);
printf("\nCac phan tu da sap xep:\n");
printlist(list,n); getch(); }
Ngo Huu Phuc, Le Quy Don Technical University20
void inputdata(int list[],int n)
{
int i;
printf("Nhap cac phan tu cho mang\n");
for(i=0;i<n;i++)
scanf("%d",&list[i]);
fflush(stdin);
}
void printlist(int list[],int n)
{
int i;
printf("Cac phan tu trong mang: \n");
for(i=0;i<n;i++)
printf("%d\t",list[i]);
printf("\n");
}
6.3. Hoạt động của QuickSort (6/6)
void swap(int *x,int *y)
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}
int getkeyposition(int i,int j )
{
return((i+j) /2);
}
void qsort(int list[],int m,int n)
{
int key,i,j,k;
if( m < n)
{
k = getkeyposition(m,n);
swap(&list[m],&list[k]);
Ngo Huu Phuc, Le Quy Don Technical University21
key = list[m];
i = m+1;
j = n;
while(i <= j)
{
while((i <= n) && (list[i] <= key))
i++;
while((j >= m) && (list[j] > key))
j--;
if( i < j)
swap(&list[i],&list[j]);
}
swap(&list[m],&list[j]);
qsort(list,m,j-1);
qsort(list,j+1,n);
}
}
6.4. Hiệu quả của Quicksort (1/6)
Trong trường hợp tốt nhất:
Giả sử, tại mỗi lần chia, tập S được chia thành 2 tập con
có kích thước gần bằng nhau.
Nếu số phần tử là n, lần đầu tiên sẽ chia thành 2 tập con
có kích thước gần bằng n/2.
Tiếp theo, mỗi tập con lại được chia thành 2 tập con có
kích thước gần bằng n/4, thực hiện điều này đến khi kích
thước mỗi mảng bằng 1.
Ngo Huu Phuc, Le Quy Don Technical University22
6.4. Hiệu quả của Quicksort (2/6)
Trong trường hợp tốt nhất (tiếp):
Gọi T(n) là thời gian cần thiết để sắp n phần tử.
Vì thời gian để sắp n phần tử là tổng thời gian cần để đưa
khóa về đúng vị trí và thời gian để sắp 2 tập con có kích
thước gần bằng n/2. Do đó:
T(n) = c*n + 2*T(n/2)
Ngo Huu Phuc, Le Quy Don Technical University23
6.4. Hiệu quả của Quicksort (3/6)
Trong trường hợp tốt nhất (tiếp):
Một cách tương tự, ta có:
T(n/2) = c*n/2 + 2*T(n/4)
T(n/4) = c*n/4 + 2*T(n/8), giả thiết T(1) = 1.
Như vậy:
T(n) = c*n + 2(c*(n/2) + 2T(n/4))
T(n) = c*n + c*n + 4T(n/4)) = 2*c*n + 4T(n/4) = 2*c*n + 4(c*(n/4) +
2T(n/8))
T(n) = 2*c*n + c*n + 8T(n/8) = 3*c*n + 8T(n/8)
T(n) = (log n)*c*n + n T(n/n)= (log n)*c*n + n T(1) = n + n*(log n) *c
T(n) = O( n log(n))
Ngo Huu Phuc, Le Quy Don Technical University24
6.4. Hiệu quả của Quicksort (4/6)
Trong trường hợp tồi nhất:
Xem xét trường hợp, khóa chính là phần tử lớn
nhất (hoặc) nhỏ nhất trên mỗi tập con.
Như vậy, tất cả các phần tử sẽ nằm về một phía.
Ví dụ, xem xét dãy sau:
[5 3 2 1 4 6 8]
1 được lấy làm khóa.
rõ ràng, vẫn còn n – 1 phần tử chưa sắp.
điều này tiếp tục xuất hiện với các tập con.
Ngo Huu Phuc, Le Quy Don Technical University25
6.4. Hiệu quả của Quicksort (5/6)
Như vậy, với mỗi lần thực hiện Quick Sort, chỉ có
1 phần tử được sắp.
Thực hiện việc này n lần.
Mỗi lần, thời gian thực hiện cho quá trình chia
mảng con là O(n).
Như vậy, thời gian cho Quick sort trong trường
hợp này: O(n2).
Ngo Huu Phuc, Le Quy Don Technical University26
6.4. Hiệu quả của Quicksort (6/6)
Đối với trường hợp trung bình?
đã chứng minh được, độ phức tạp: O(nlogn)
Trong thực tế, quicksort thường cho thấy sự hiệu
quả trong sắp xếp.
có thể hình dung qua xác suất.
với các tập có ít hơn 30 phần tử, quicksort
chưa cho thấy sự hiệu quả.
Ngo Huu Phuc, Le Quy Don Technical University27