Giới thiệu
- Sắp xếp nổi bọt (Bubble sort)
- Sắp xếp lựa chọn (Selection sort)
- Sắp xếp chèn vào (Insertion sort)
- Sắp xếp nhanh (Quick sort)
- Sắp xếp trộn (Merge sort)
Chắc hẳn ngồi trên ghế giảng đường đại học thì ai cũng sẽ được làm quen với thuật toán. Nghe thì thật là trừu tượng và mơ hồ, nhưng để tối ưu hóa những bài toán đặt ra thì bắt buộc các bạn phải học đến nó. Mình xin chia sẻ 1 chút lí thuyết mà mình học được về các thuật toán sắp xếp đơn giản, mong là có thể giúp các bạn áp dụng vào bài toán thực tế của mình!
Sắp xếp nổi bọt ( bubble sort)
Ý tưởng
Đây có lẽ là loại sắp xếp quen thuộc nhất với mọi người. Ý tưởng của thuật toán sắp xếp nổi bọt như sau: cho chỉ số i chạy từ 0, 1, ..., n-1, nếu hai phần tử kề nhau không đúng trật tự, có nghĩa là A[i].key > A[i+1].key thì ta tráo đổi hai phần tử A[i] và A[i+1]. Cứ tiếp tục làm như vậy thì ta sẽ đẩy dữ liệu có khóa lớn nhất lên vị trí sau cùng là A[n-1].
Ví dụ
Giả sử ta có mảng số nguyên A[0..4] = (7, 2, 8, 4, 6). Kết quả thực hiện việc tráo đổi sẽ được thực hiện trong bảng sau:
| A[0] | A[1] | A[2] | A[3] | A[4] | Chú thích |
|---|---|---|---|---|---|
| 7 | 2 | 8 | 4 | 6 | Vì 7 > 2, tráo đổi A[0] với A[1] |
| 2 | 7 | 8 | 4 | 6 | Vì 8 > 4, tráo đổi A[2] với A[3] |
| 2 | 7 | 4 | 8 | 6 | Vì 8 > 6, tráo đổi A[3] với A[4] |
| 2 | 7 | 4 | 6 | 8 |
Lặp lại quá trình trên với mảng A[0, ..., n-2] để đẩy phần tử lớn nhất lên vị trí A[n-2], khi đó ta có A[n-2].key <= A[n-1].key. Tiếp tục lặp như vậy với các đoạn đầu A[0..i], với i = n-3, ...., 1, ta sẽ thu được mảng được sắp.
Thuật toán
1void BubbleSort (int A[], int n) {
2 for (int i = n-1; i > 0; i--) {
3 for (int k = 0; k < i; k++) {
4 if (A[k].key > A[k+1].key) {
5 Swap(A[k], A[k+1]); //doi vi tri A[k] và A[k+1]
6 }
7 }
8 }
9}
Ta sẽ dễ thấy thời gian chạy của thuật toán này là O(n2) Tuy nhiên giờ ta cũng có thể cải tiến thuật toán sắp xếp nổi bọt bằng cách thêm 1 biến booblean là
check, biến này trả về true nếu A[0..i] đã được sắp xếp và ngược lại. Nếu check nhận giá trị true thì vòng for đầu tiên sẽ dừng lại. Mục đích là ở lện lặp đầu tiên, nếu đến chỉ số i nào đó mà đoạn đầu A[0..i] đã được sắp xếp thì ta có thể dừng không lặp nữa, giảm thiểu được thời gian chạy.void BubbleSort (int A[], int n) {
for (int i = n-1; i > 0; i--) {
bool check = true;
for (int k = 0; k < i; k++) {
if (A[k].key > A[k+1].key) {
Swap(A[k], A[k+1]);
check = false;
}
}
if (check) {
break;
}
}
}
Sắp xếp lựa chọn (selection sort)
Ý tưởng
Ý tưởng của thuật toán này cũng đơn giản không kém sắp xếp nổi bọt: Giả sử ta chọn được thành phần có khóa nhỏ nhất trên mảng là A[k]. Tráo đổi A[0] với A[k], vậy thì lúc này ta sẽ nhận được A[0] là phần tử có khóa nhỏ nhất. Giả sử đến bước thứ i ta đã có A[0].key <= A[1].key <= ... <= A[i-1].key. Bây giờ ta cần tìm thành phần có khóa nhỏ nhất trong các phần tử từ A[i] đến A[n-1]. Giả sử thành phần đó là A[k] sao cho i <= k <= n-1. Ta lại tráo đổi A[i] với A[k], ta có A[0].key <= A[1].key <= ... <= A[i-1].key <= A[i].key. Lặp lại cho tới i = n-1, ta có mảng A được sắp xếp
Ví dụ
Ta lại xét mảng A ở ví dụ trên A[0..4] = [7, 2, 8, 4, 6]. Kết quả được thể hiện trong bảng sau: Chọn phần tử có khóa nhỏ nhất là A[0]
| A[0] | A[1] | A[2] | A[3] | A[4] | i | k |
|---|---|---|---|---|---|---|
| 7 | 2 | 8 | 4 | 6 | 0 | 1 |
| 2 | 7 | 8 | 4 | 6 | 1 | 3 |
| 2 | 4 | 8 | 7 | 6 | 2 | 4 |
| 2 | 4 | 6 | 7 | 8 |
Ok vậy là bài toán có thể giải quyết nhanh gọn 
Cùng nghía qua phần thuật toán nhé
Cùng nghía qua phần thuật toán nhéThuật toán
1void SelectionSort(int A[], int n) {
2 for (int i = 0; i < n - 1; i++) {
3 int k = i;
4 for (int j = i + 1; j < n; j++) {
5 if (A[j].key < A[k].key) {
6 k = j;
7 Swap(A[i], A[k]); //doi gia tri 2 bien
8 }
9 }
10 }
11}
Thời gian chạy của thuật toán này cũng tương tự như thuật toán sắp xếp nổi bọt là O(n2).
Sắp xếp xen vào (insertion sort)
Đây là thuật toán cuối cùng mà mình sẽ giới thiệu ở bài ngày hôm nay.
Ý tưởng
Cái tên của thuật toán cũng giúp mình hình dung được phần nào ý tưởng của thuật toán. Giả sử đoạn đầu của mảng A[0..i-1] (với i >= 1) đã được sắp xếp, nghĩa là ta đã có A[0].key <= A[1].key <= ... <= A[i-1].key. Ta xen A[i] vào vị trí thích hợp trong đoạn đầu A[0..i-1] để nhận được A[0..i] được sắp xếp. Với i = 1 thì coi như đoạn đã được sắp xếp. Lặp lại quá trình đó với i = 2, ..., n-1 để có được mảng sắp xếp. Việc sắp xếp sẽ được tiến hành như sau: Cho chỉ số k chạy từ i, nếu A[k].key < A[k-1].key thì ta tráo đổi vị trí của A[k] và A[k-1] rồi giảm k đi 1.
Ví dụ
Ta có 1 mảng số nguyên A[0..5] = (1, 3, 7, 2, 8, 4) và đoạn đầu A[0..2] = (1, 3, 7) đã được sắp xếp Đầu tiên ta sẽ chọn i = 3 ( vì giá trị từ 0 đến 2 đã được sắp xếp) và k = i = 3. Nhận thấy A[3] < A[2] nên ta tráo đổi A[3] và A[2], ta có:
| A[0] | A[1] | A[2] | A[3] | A[4] | A[5] |
|---|---|---|---|---|---|
| 1 | 3 | 2 | 7 | 8 | 4 |
Đến đây thì ta có k = 2, A[2] < A[1] nên ta lại tráo A[2] cho A[1]:
| A[0] | A[1] | A[2] | A[3] | A[4] | A[5] |
|---|---|---|---|---|---|
| 1 | 2 | 3 | 7 | 8 | 4 |
Lúc này k = 1 và A[1] >= A[0] nên ta dừng lại và ta đã có đoạn đầu A[0..3] được sắp xếp Lặp lại các bước trên với i = 4, 5 ta sẽ được mảng sắp xếp tăng dần
Thuật toán
Hàm sắp xếp xen vào được viết như sau:
void InsertionSort(A[], int n) {
for (int i = 1; i < n-1; i++) {
for (int k = i; k > 0; k--) {
if (A[k].key < A[k-].key) {
Swap(A[k], A[k-1]); //doi cho A[k] va A[k-1]
} else {
break;
}
}
}
}
Thuật toán sắp xếp này cũng có thời gian chạy là O(n2) Bài này mình xin phép dừng tại đây. Bài sau mình sẽ giới thiệu thêm 1 số thuật toán sắp xếp ít được sử dụng hơn nhưng lại có thời gian chạy nhanh hơn hẳn 3 thuật toán trên. Hi vọng mọi người đón đọc và cho những lời góp ý! Many thanks!
Sắp xếp nhanh (Quick Sort)
1. Giới thiệu
Sắp xếp nhanh (Quick Sort) còn có một tên gọi khác là sắp xếp phân chia (Part Sort) dựa trên ý tưởng thuật toán. Nó được phát minh lần đầu bởi C.A.Hoare vào năm 1960. Có lẽ đây là thuật toán được nghiên cứu và sử dụng rộng rãi nhất trong các thuật toán sắp xếp. Quick sort cũng là thuật toán đệ quy. Ngược với Mergesort gọi đệ quy rồi mới xử lý, Quick sort xử lý xong mới gọi đệ quy.
Ý tưởng của thuật toán này dựa trên phương pháp chia để trị, nghĩa là chia dãy cần sắp xếp thành 2 phần, sau đó thực hiện việc sắp xếp cho mỗi phần độc lập nhau. Để làm việc này thì ta cần phải làm các bước sau:
1. Chọn ngẫu nhiên một phần tử nào đó của dãy làm phần tử khóa (pivot) Kĩ thuật chọn phần tử khóa rất quan trọng vì nếu không may bạn có thể bị rơi vào vòng lặp vô hạn đối với các trường hợp đặc biệt. Tốt nhất là chọn phần tử ở vị trí trung tâm của dãy. Khi đó sau 
lần phân chia ta sẽ đạt tới kích thước danh sách bằng 1. Tuy nhiên điều đó rất khó. Có các cách chọn phần tử khóa như sau:
lần phân chia ta sẽ đạt tới kích thước danh sách bằng 1. Tuy nhiên điều đó rất khó. Có các cách chọn phần tử khóa như sau:- Chọn phần tử đứng đầu hoặc đứng cuối làm phần tử khóa.
- Chọn phần tử đứng giữa danh sách làm phần tử khóa.
- Chọn phần tử trung gian trong 3 phần tử đứng đầu, đứng giữa và đứng cuối làm phần tử khóa.
- Chọn phần tử ngẫu nhiên làm phần tử khóa. (Cách này có thể dẫn đến khả năng rơi vào các trường hợp đặc biệt)
2. Xếp các phần tử nhỏ hơn phần tử chốt ở phía trước phần tử khóa
3. Xếp các phần tử lớn hơn phần tử chốt ở phía sau phần tử khóa Để có được sự phân loại này thì ở 2 bước trên, các phần tử sẽ được so sánh với khóa và hoán đổi vị trí cho nhau hoặc cho khóa nếu nó lớn hơn khóa mà lại nằm trước khóa, hoặc nhỏ hơn mà lại nằm sau khóa. Áp dụng kĩ thuật như trên cho mỗi đoạn đó và tiếp tục làm vậy cho đến khi mỗi đoạn chỉ còn 2 phần tử. Khi đó toàn bộ dãy đã được sắp xếp
Quick sort là một thuật toán dễ cài đặt, hiệu quả trong hầu hết các trường hợp và tiêu tốn ít tài nguyên hơn so với các thuật toán khác. Độ phức tạp trung bình của giải thuật là
O(NlogN).2. Các bước thực hiện giải thuật
Giả sử ta có một dãy các phần tử như sau:
| A[0] | A[1] | A[2] | A[3] | A[4] | A[5] | A[6] | A[7] |
|---|---|---|---|---|---|---|---|
| 28 | 16 | 56 | 30 | 17 | 32 | 24 | 18 |
left = 0; right = 7; Ở ví dụ này ta lấy một phần tử làm khóa, ở đây mình chọn phần tử khóa là A[(0+7)/2] = A[3] = 30 Cho i chạy từ trái sang phải, bắt đầu từ vị trí 0 Cho j chạy từ phải sang trái, bắt đầu từ vị trí 7 Quá trình duyệt từ bên trái với biến duyệt i sẽ dừng lại ở 56 (i=2), vì đây không phải là phần tử nhỏ hơn khóa. Quá trình duyệt từ bên phải với biến duyệt j sẽ dừng lại ở 18 (j=7) vì đây là phần tử nhỏ hơn khóa. Tiến hành đổi chỗ 2 phần tử cho nhau.
| A[0] | A[1] | A[2] | A[3] | A[4] | A[5] | A[6] | A[7] |
|---|---|---|---|---|---|---|---|
| 28 | 16 | 18 | 30 | 17 | 32 | 24 | 56 |
Quá trình duyệt tiếp tục. Khóa ở đây vẫn là 30. Ta tiếp tục tăng biến duyệt i và giảm biến duyệt j, nhận thấy biến duyệt i chạy đến 30 (i=3), còn biến duyệt j dừng lại ở 24 (j=6). Tiến hành đổi chỗ 2 phần tử cho nhau.
| A[0] | A[1] | A[2] | A[3] | A[4] | A[5] | A[6] | A[7] |
|---|---|---|---|---|---|---|---|
| 28 | 16 | 18 | 24 | 17 | 32 | 30 | 56 |
Quá trình duyệt tiếp tục. Khóa ở đây vẫn là 30. Tiếp tục tăng biến duyệt i và giảm biến duyệt j, nhận thấy biến duyệt i chạy đến 32 (i=5), còn biến duyệt j dừng lại ở 30(j=6). Tiến hành đổi chỗ 2 phần tử cho nhau.
| A[0] | A[1] | A[2] | A[3] | A[4] | A[5] | A[6] | A[7] |
|---|---|---|---|---|---|---|---|
| 28 | 16 | 18 | 24 | 17 | 30 | 32 | 56 |
Quá trình duyệt tiếp tục. Khóa ở đây vẫn là 30. Tiếp tục tăng biến duyệt i và giảm biến duyệt j, nhận thấy biến duyệt i và j cùng chạy đến 30. Lúc này ta sẽ chia mảng trên ra làm 2 mảng con A[0..4] và A[5..7], vì ta thấy A[5..7] đã được sắp xếp tăng dần rồi nên ta sẽ xét A[0..4] A[0..4] = [28, 16, 18, 24, 17] Lặp lại những bước trên với phần tử được chọn là khóa là A[(0+4)/2] = A[2] = 18 left = 0; right = 4; Cho i chạy từ trái sang phải bắt đầu từ vị trí 0 Cho j chạy từ phải sang trái bắt đầu từ vị trí 4 Quá trình duyệt từ bên trái với biến duyệt i sẽ dừng lại ở 28(i=0) vì đây không phải là phần tử nhỏ hơn khóa. Quá trình duyệt từ bên phải với biến duyệt j sẽ dừng lại ở 17 (j=4) vì đây là phần tử không lớn hơn khóa. Tiến hành đổi chỗ 2 phần tử cho nhau.
| A[0] | A[1] | A[2] | A[3] | A[4] |
|---|---|---|---|---|
| 17 | 16 | 18 | 24 | 28 |
Quá trình duyệt tiếp tục. Tăng biến duyệt i và giảm biến duyệt j. Lúc này i = j nên ta sẽ chia mảng trên ra làm 2 mảng con A[0..1] và A[2..4]. Ta thấy A[2..4] đã được sắp xếp tăng dần rồi, nên ta chỉ xét A[0..1], vì A[0] > A[1] nên ta đổi chỗ 2 phần tử cho nhau và được mảng sắp xếp tăng dần cuối cùng:
| A[0] | A[1] | A[2] | A[3] | A[4] | A[5] | A[6] | A[7] |
|---|---|---|---|---|---|---|---|
| 16 | 17 | 18 | 24 | 28 | 30 | 32 | 56 |
3. Cài đặt giải thuật
Như đã nói ở trên, Quick sort cũng là một thuật toán đệ quy, bao gồm việc chia mảng thành 2 mảng con thỏa mãn yêu cầu trên, sau đó thực hiện lời gọi đệ quy với 2 mảng con vừa tạo được. Giả sử mảng được giới hạn bởi 2 tham số left và right cho biết chỉ số đầu và cuối của mảng, khi đó thuật toán được cài đặt như sau:
void QuickSort(int left, int right)
{
int x = A[(left + right)/2]; //luu gia tri phan tu giua mang
int i = left;
int j = right;
do {
//tim phan tu khong nho hon x theo i
while(A[i] < x)
i++;
//tim phan tu khong lon hon x theo j
while(A[j] > x)
j--;
//neu i nam truoc j thi thuc hien hoan vi
if(i <= j) {
swap(A[i], A[j]); //hoan vi 2 phan tu tai vi tri i va j
//sau khi hoan vi thi tang i va giam j
i++;
j--;
}
} while(i < j);
//neu left < j thi tiep tuc chia mang de sap xep
if (left < j)
QuickSort(left, j);
//neu i < right thi tiep tuc chia mang de sap xep
if (i < right)
QuickSort(i, right);
}
4. Phân tích
Nhược điểm của Quick Sort là không hiệu quả trên những dãy đã được sắp xếp sẵn. Khi đó ta phải mất N lần gọi đệ quy và mỗi lần chỉ loại được 1 phần tử. Thời gian thực hiện thuật toán trong trường hợp xấu nhất này là O(n2). Trong trường hợp tốt nhất, mỗi lần phân chia sẽ được 2 nửa dãy bằng nhau, khi đó thời gian thực hiện thuật toán là: T(N) = 2T(N/2) + N Khi đó T(N) xấp xỉ bằng NlogN. Như vậy Quick sort là thuật toán hiệu quả trong đa số các trường hợp. Nhưng đối với các trường hợp việc sắp xếp chỉ phải thực hiện ít và lượng dữ liệu lớn thì nên sử dụng một số thuật toán khác ví dụ như Merge sort dưới đây.
Sắp xếp trộn (Merge Sort)
1. Giới thiệu
Trong khoa học máy tính, sắp xếp trộn (merge sort) là một thuật toán sắp xếp để sắp xếp các danh sách (hoặc bất kỳ cấu trúc dữ liệu nào có thể truy cập tuần tự, v.d. luồng tập tin) theo một trật tự nào đó. Nó được xếp vào thể loại sắp xếp so sánh. Thuật toán này là một ví dụ tương đối điển hình của lối thuật toán chia để trị do John von Neumann đưa ra lần đầu năm 1945.
Ý tưởng của giải thuật này bắt nguồn từ việc trộn 2 danh sách đã sắp xếp thành 1 danh sách mới cũng được sắp.
Giả sử có hai danh sách đã được sắp xếp a[1..m] và b[1..n]. Ta có thể trộn chúng lại thành một danh sách mới c[1..m+n] được sắp xếp theo cách sau:
- So sánh hai phần tử đứng đầu của hai danh sách, lấy phần tử nhỏ hơn cho vào danh sách mới. Tiếp tục như vậy cho tới khi một trong hai danh sách là rỗng.
- Khi một trong hai danh sách là rỗng ta lấy phần còn lại của danh sách kia cho vào cuối danh sách mới.
Ví dụ cho 2 danh sách đã được sắp xếp là a = [1, 4, 6, 7] và b = [2, 3, 8] Ta thực hiện trộn như sau:
| Danh sách a | Danh sách b | So sánh | Danh sách c |
|---|---|---|---|
| 1, 4, 6, 7 | 2, 3, 8 | 1 < 2 | 1 |
| 4, 6, 7 | 2, 3, 8 | 2 < 4 | 1, 2 |
| 4, 6, 7 | 3, 8 | 3 < 4 | 1, 2, 3 |
| 4, 6, 7 | 8 | 4 < 8 | 1, 2, 3, 4 |
| 6, 7 | 8 | 6 < 8 | 1, 2, 3, 4, 6 |
| 7 | 8 | 1, 2, 3 ,4 ,6, 7, 8 |
2. Các bước thực hiện giải thuật
Đầu tiên, ta coi các phần tử của dãy như các dãy con có 1 phần tử. Tiến hành trộn từng cặp 2 dãy con này để được các dãy con được sắp xếp gồm 2 phần tử. Tiếp tục trộn từng cặp dãy con 2 phần tử thành các dãy con được sắp gồm 4 phần tử... Quá trình được lặp lại cho tới khi toàn bộ dãy được sắp. Ta vẫn thực hiện với dãy trước:
| A[0] | A[1] | A[2] | A[3] | A[4] | A[5] | A[6] | A[7] |
|---|---|---|---|---|---|---|---|
| 28 | 16 | 56 | 30 | 17 | 32 | 24 | 18 |
Coi mỗi phần tử của dãy như một dãy con đã sắp gồm 1 phần tử. Tiến hành trộn từng cặp dãy con 1 phần tử với nhau, ta sẽ được dãy:
| A[0] | A[1] | A[2] | A[3] | A[4] | A[5] | A[6] | A[7] |
|---|---|---|---|---|---|---|---|
| 16 | 28 | 30 | 56 | 17 | 32 | 18 | 24 |
Sau bước này ta được các dãy con đã sắp gồm 2 phần tử. Tiến hành trộn các cặp dãy con đã sắp gồm 2 phần tử để tạo thành dãy con được sắp gồm 4 phần tử:
| A[0] | A[1] | A[2] | A[3] | A[4] | A[5] | A[6] | A[7] |
|---|---|---|---|---|---|---|---|
| 16 | 28 | 30 | 56 | 17 | 18 | 24 | 32 |
Sau bước này ta được dãy con đã sắp gồm 4 phần tử. Tiến hành trộn các cặp dãy con đã sắp, cuối cùng ta được 1 dãy đã sắp xếp như sau:
| A[0] | A[1] | A[2] | A[3] | A[4] | A[5] | A[6] | A[7] |
|---|---|---|---|---|---|---|---|
| 16 | 17 | 18 | 24 | 28 | 30 | 32 | 56 |
3. Cài đặt giải thuật
void merge(int array[], int first, int middle, int last) {
int temp[last + 1];
int first1, last1, first2, last2;
int index = first;
first1 = first;
last1 = middle;
first2 = middle+1;
last2 = last;
//so sanh cac phan tu 2 mang con va luu vao mang temp
while((first1 <= last1) && (first2 <= last2)) {
if(array[first1] < array[first2]) {
temp[index] = array[first1];
index ++;
first1 ++;
} else {
temp[index] = array[first2];
index ++;
first2 ++;
}
}
//neu mang thu 1 chua het
if(first2 > last2) {
while(first1 <= last1) {
temp[index] = array[first1];
index ++;
first1 ++;
}
}
//neu mang thu 2 chua het
if(first1 > last1) {
while(first2 <= last2) {
temp[index] = array[first2];
index ++;
first2 ++;
}
}
for(int i = first; i <= last; i ++) {
array[i] = temp[i - first];
}
return;
}
//thuat toan sap xep tron
void mergeSort(int array[], int first, int last) {
if(first < last) {
int middle = int((first + last) / 2);
mergeSort(array, first, middle);
mergeSort(array, middle + 1, last);
merge(array, first, middle, last);
}
}
4. Phân tích
Merge sort là một giải thuật sắp xếp mà có thời gian thực hiện là O(NlogN) trong mọi trường hợp, bởi vậy mà với dữ liệu lớn và cần ít thao tác sắp xếp thì nó sẽ tối ưu hơn Quick sort. Nó chỉ có 1 nhược điểm đó là code hơi khó cài đặt.
Tham khảo
- Cấu trúc dữ liệu và giải thuật: https://docs.google.com/viewer?a=v&pid=sites&srcid=ZGVmYXVsdGRvbWFpbnx2YW5tbDE4MnxneDoxNTFhMGU2NGYzZWIwMmM0
- Sắp xếp nhanh: https://vi.wikipedia.org/wiki/Sắp_xếp_nhanh
- Sắp xếp trộn: https://vi.wikipedia.org/wiki/Sắp_xếp_trộn
Tham khảo
Tài liệu cấu trúc dữ liệu và thuật toán - Đinh Mạnh Tường
No comments:
Post a Comment