Nguồn mình Coppy: www.nguyenvanquan7826.com .
Ý tưởng: QuickSort chia mảng thành hai danh sách
bằng cách so sánh từng phần tử của danh sách với một phần tử được chọn
được gọi là phần tử chốt. Những phần tử nhỏ hơn hoặc bằng phần tử chốt
được đưa về phía trước và nằm trong danh sách con thứ nhất, các phần tử
lớn hơn chốt được đưa về phía sau và thuộc danh sách con thứ hai. Cứ
tiếp tục chia như vậy tới khi các danh sách con đều có độ dài bằng 1
Có các cách chọn phần tử chốt như sau:
– Chọn phần tử đứng đầu hoặc đứng cuối làm phần tử chốt.
– Chọn phần tử đứng giữa danh sách làm phần tử chốt.
– Chọn phần tử trung vị trong 3 phần tử đứng đầu, đứng giữa và đứng cuối làm phần tử chốt.
– Chọn phần tử ngẫu nhiên làm phần tử chốt (Cách này hay được chọn vì tránh được các trường hợp đặc biệt)
Hình minh họa:
Cài đặt bằng C:
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
#include<stdio.h>
#include<stdlib.h>
#include<time.h> // thu vien de khoi tao tham so cho ham rand()
#define swap(type, a, b) {type temp = a; a = b; b = temp; } // hang hoan vi
void quickSort(int *a, int l, int r)
{
srand(time(NULL));
int key = a[l + rand() % (r-l+1)];
int i = l, j = r;
while(i <= j)
{
while(a[i] < key) i++;
while(a[j] > key) j--;
if(i <= j)
{
if (i < j)
swap(int, a[i], a[j]);
i++;
j--;
}
}
if (l < j) quickSort(a, l, j);
if (i < r) quickSort(a, i, r);
}
int main ()
{
int i, arr[] = { 40, 10, 100, 90, 20, 25 };
quickSort(arr, 0, 5);
for (i=0; i<6; i++)
printf ("%d ", arr[i]);
return 0;
}
|
Thuật toán được cài đặt từ dòng 6 đến dòng 29. Trong đó có dòng 21 swap(int, a[i], a[j]);
là một hằng dùng để hoán vị 2 số a[i] và a[j] được định nghĩa tại dòng 4
và nó tương đương với đoạn code sau (bạn có thể thay nó trực tiếp vào):
1
2
3
4
5
|
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
|
Bạn cũng có thể xem đoạn code sau, với
đoạn code này tôi đã in ra màn hình mọi sự biến đổi của mảng, của l, r,
i, j giúp chúng ra quan sát được chính xác sự thay đổi trong từng bước:
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
#include<stdio.h>
#include<stdlib.h>
#include<time.h> // thu vien de khoi tao tham so cho ham rand()
#define swap(type, a, b) {type temp = a; a = b; b = temp; } // hang hoan vi
void quickSort(int *a, int l, int r)
{
srand(time(NULL));
int key = a[l + rand() % (r-l+1)];
int i = l, j = r;
printf("nnl = %d r = %d select: key = %d (random) ",l, r, key);
while(i <= j)
{
printf("nnti : %d", i);
while (a[i] < key) { i++; printf(" -> %d",i); }
printf("ntj : %d", j);
while (a[j] > key) { j--; printf(" -> %d",j); }
if(i <= j)
{
if (i < j)
{
swap(int, a[i], a[j]);
printf("ntswap(a[%d], a[%d]) swap(%d, %d)", i, j, a[i], a[j]);
}
i++;
j--;
printf("ntarr[] : ");
for (int i=0; i<8; i++)
printf ("%d ", a[i]);
}
}
if (l < j) quickSort(a, l, j);
if (i < r) quickSort(a, i, r);
}
int main ()
{
int i, arr[] = { 2, 8, 7, 1, 3, 5, 6, 4 };
int n = 8;
printf("nnArray befor sort: ");
for (i=0; i<n; i++)
printf ("%d ", arr[i]);
quickSort(arr, 0, n-1);
printf("nnArray after sort: ");
for (i=0; i<n; i++)
printf ("%d ", arr[i]);
}
|
Ta nhận thấy hiệu quả của thuật toán phụ thuộc vào việc chọn giá trị mốc (hay phần tử chốt).
– Trường hợp tốt nhất:
mỗi lần phân hoạch ta đều chọn được phần tử median (phần tử lớn hơn hay
bằng nửa số phần tử và nhỏ hơn hay bằng nửa số phần tử còn lại) làm mốc.
Khi đó dãy được phân hoạch thành hai phần bằng nhau, và ta cần log2(n)
lần phân hoạch thì sắp xếp xong. Ta cũng dễ nhận thấy trong mỗi lần phân
hoạch ta cần duyệt qua n phần tử. Vậy độ phức tạp trong trường hợp tốt
nhất thuộc O(nlog2(n)).
– Trường hợp xấu nhất:
mỗi lần phần hoạch ta chọn phải phần tử có giá trị cực đại hoặc cực tiểu
làm mốc. Khi đó dãy bị phân hoạch thành hai phần không đều: một phần
chỉ có một phần tử, phần còn lại có n-1 phần tử. Do đó, ta cần tới n lần
phân hoạch mới sắp xếp xong. Vậy độ phức tạp trong trường hợp xấu nhất
thuộc O(n2).
* Vậy ta có độ phức tạp của Quick Sort như sau:
– Trường hợp tốt nhất: O(nlog2n)
– Trường hợp xấu nhất: O(n2)
– Trường hợp trung bình: O(nlog2n)
Khử đệ quy trong Quic Sort
Bản chất của các giải thuật đệ quy là lưu
trữ các tham biến đệ quy vào một ngăn xếp (stack) để lần lượt lấy ra xử
lý. Như vậy nếu gặp dữ liệu lớn sẽ dễ gây tràn stack. Khi khử đệ quy
của giải thuật đệ quy, với mỗi lần cần gọi hàm quicksort trong đệ quy ta
thay bằng cách lưu lại các giá trị bên trái và bên phải của 2 dãy con
vào 2 stack Sl và Sr, khi nào cần sẽ gọi ra. Ngoài ra chúng ta cũng có
thể lưu chung các giá trị bên trái và bên phải vào 1 Stack, khi lấy ra
sẽ lấy 2 phần tử liên tiếp.
b1: Khởi tạo 2 Stack rỗng Sl, Sr để lưu các giá trị l và các giá trị r của mỗi mảng con.
b2: Ban đầu dãy đang xét từ 0 đến n-1, ta lưu l vào Sl và r vào Sr
b3: Lấy l ra từ Sl, r ra từ Sr
b4: Phân hoạch dãy A[L] .. A[R] thành 2 dãy A[l]..A[j] và A[i]..A[r]
b5: Nếu l < j lưu l và j vào Sl và Sr, Nếu i < r lưu i và r vào Sl và Sr,
b6: Nếu Stack không rỗng quay lại b3.
Sau đây là code cài đặt, trong code có dùng đến
stack trong C++, nếu bạn không muốn hoặc chưa quen dùng stack trong C++ có thể tham khảo cách xây dựng 1 Stack tại
đây.
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
#include<stdio.h>
#include<stdlib.h>
#include<time.h> // thu vien de khoi tao tham so cho ham rand()
#include<stack> // Su dung Stack trong C++
#define swap(type, a, b) {type temp = a; a = b; b = temp; }
using namespace std;
void quickSortUnRecursive(int *a, int l, int r)
{
srand(time(NULL));
stack Sl;
stack Sr;
Sl.push(l);
Sr.push(r);
while(!Sl.empty())
{
int l = Sl.top(); Sl.pop();
int r = Sr.top(); Sr.pop();
int key = a[l + rand() % (r-l+1)];
int i = l, j = r;
while (i <= j)
{
while (a[i] < key) i++;
while (a[j] > key) j--;
if(i <= j)
{
if (i < j)
swap(int, a[i], a[j]);
i++;
j--;
}
}
if (l < j) { Sl.push(l); Sr.push(j); }
if (i < r) { Sl.push(i); Sr.push(r); }
}
}
int main ()
{
int i, arr[] = { 40, 10, 100, 90, 20, 25 };
quickSortUnRecursive(arr, 0, 5);
for (i=0; i<6; i++)
printf ("%d ", arr[i]);
return 0;
}
|
Sử dụng đệ quy đuôi trong Quick Sort
Ta cũng có thể sử dụng thuật toán đệ quy
đuôi để xây dựng thuật toán Quick Sort, tức là chỉ dùng một lời gọi đệ
quy trong hàm, tuy nhiên để thực hiện việc này chúng ta sẽ phải chọn
phần tử chốt là phần tử đầu tiên hoặc cuối cùng của mảng cần sắp xếp. Ta
Có thể phân tích trường hợp này như sau:
Trước tiên ta xác định việc phân dãy ra làm 2 mảng con như sau:
01
02
03
04
05
06
07
08
09
10
11
12
13
|
int partition(int *a, int l, int r)
{
int key = a[r];
int i = l - 1, j;
for (j=l; j<r; j++)
if (a[j] <= key)
{
i++;
swap(int, a[i], a[j]);
}
swap(int, a[i+1], a[r]);
return i + 1;
}
|
Sau khi phân chia dãy ta được 2 dãy, dãy
bên trái là những phần tử nhỏ hơn hoặc bằng key, bên phải là dãy các
phần tử lớn hơn key.
Bây giờ ta xây dựng Quick Sort đệ quy đuôi như sau:
1
2
3
4
5
6
7
8
9
|
void TailRecursiveQuicksort(int *a, int l, int r)
{
while (l<r)
{
int q = partition(a,l,r);
TailRecursiveQuicksort(a, l, q-1);
l = q + 1;
}
}
|
Ngoài ra, nhằm mục đích sao cho khi gọi
đệ quy, Stack của chúng ta có thể phải chứa càng ít càng tốt, vì vậy ta
cải tiến một chút giải thuật như sau:
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
|
void TailRecursiveQuicksort_2(int *a, int l, int r)
{
while (l<r)
{
int q = partition(a,l,r);
if (q < (l + (r-l)/2))
{
TailRecursiveQuicksort_2(a, l, q-1);
l = q + 1;
}
else
{
TailRecursiveQuicksort_2(a, q + 1, r);
r = q-1;
}
}
}
|
Sử dụng Quick Sort xây dựng sẵn trong C++
Trong thư viện của C++ đã xây dựng sẵn cho chúng ta hàm qsort và chúng ta có thể sử dụng ngay nó.
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
|
#include<stdio.h>
#include<stdlib.h>
int arr[] = { 40, 10, 100, 90, 20, 25 };
int compare (const void * a, const void * b)
{
return ( *(int*)a > *(int*)b );
}
int main ()
{
int n;
qsort (arr + 1, 4, sizeof(int), compare);
for (n=0; n<6; n++)
printf ("%d ",arr[n]);
return 0;
}
|
Trong lời gọi hàm qsort: qsort (arr + 1, 4, sizeof(int), compare);
arr + 1 chính là vị trí mảng bắt đầu sắp xếp, ở đây tương đương với sắp xếp từ phần tử a[1] = 10 và sắp xếp 4 phần tử tức là từ a[1] đến a[4].
sizeof(int) là kích thước 1 phần tử trong mảng. Nếu mảng là kiểu thực ta sẽ có là sizeof(float).
compare được xây dựng với cấu trúc như sau dùng để xác định mảng được sắp xếp tăng hay giảm
1
2
3
4
|
int compareMyType (const void * a, const void * b)
{
return ( *(MyType*)a @ *(MyType*)b );
}
|
Trong đó MyType là kiểu của các phần tử
mảng. “@” là một phép toán nào đó được định nghĩa. Trong thư viện đã
định nghĩa sẵn cho chúng ta 3 phép toán >, ==, <. Trong ví dụ này
ta dùng *(int*)a > *(int*)b để sắp xếp tăng, ngược lại nếu *(int*)b
> *(int*)a sẽ sắp xếp giảm.
Sắp xếp mảng cấu trúc bằng Quick Sort có sẵn trong C++
Tiếp theo chúng ta sẽ làm thế nào nếu chúng ta có 1 mảng các phẩn tử cấu trúc Struct và muốn sắp xếp theo 1 trường nào đó.
Ta sẽ định nghĩa 1 phép toán “@” để so sánh 1 trường nào đó bằng hàm bool operator sau đó xây dựng lại hàm int compare thep phép toán đã được xây dựng:
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
#include<iostream>
#include<cstdlib>
using namespace std;
struct St
{
string name;
int scores;
};
bool operator * ( const St &t, const St &u )
{
return t.name > u.name;
}
bool operator/( const St &t, const St &u )
{
return t.scores < u.scores;
}
int compare_name (const void * a, const void * b)
{
return ( *( St*)a * *(St*)b );
}
int compare_scores (const void * a, const void * b)
{
return ( *( St*)a / *(St*)b );
}
int main ()
{
St arr[] = { {"Hien", 9}, {"Cuong", 7}, {"Nhung", 8}, {"Nam", 6} };
int n = sizeof( arr ) / sizeof( St );
qsort (arr, n, sizeof(St), compare_name);
cout << "nDanh sach xap xep tang dan theo ten:n";
for (int i = 0; i < n; i++ )
cout << arr[ i ].name << ' ' << arr[ i ].scores << endl;
qsort (arr, n, sizeof(St), compare_scores);
cout << "nDanh sach xap xep giam dan theo diem:n";
for (int i = 0; i < n; i++ )
cout << arr[ i ].name << ' ' << arr[ i ].scores << endl;
return 0;
}
|
Trong đoạn code trên tôi đã dùng các ký
hiệu đặc biệt * và / (mà chính xác hơn là các ký hiệu bình thừong được
dùng làm phép toán nhân và chia) để định nghĩa phép toán cho cách sắp
xếp. Chúng ta có thể dùng một số ký tự phép toán khác như %, ^, *, /, +,
-, >, =, < để định nghĩa phép toán mới.
Posts
