Với tất cả các loại sort, thì mình sẽ sử dụng hàm swap (hoán vị) để thuận tiện cho việc thao tác nhé!
1
2
3
4
5
6
| void swap(int&a, int&b){ int temp = a; a = b; b = temp;} |
Và mình quy ước: a là tên mảng, n là số phần tử 😀
1. Bubble sort
Bubble sort (hay còn gọi là Sắp xếp nổi bọt) là 1 thuật toán dễ cài đặt nhất trong tất cả các loại thuật toán, vì vậy nó được mấy bạn học sinh, sinh viên ưa xài (mình lâu lâu làm biếng cũng hay xài :v). Như tên gọi, thuật toán này sẽ tìm vị trí được xem là nhỏ nhất trong dãy bằng cách bắt cặp so sánh, rồi cho nó “trồi” lên vị trí đầu tiên, tiếp tục tới những phần tử tiếp theo, nó cứ trồi lên từ bé đến lớn, giống như những bong bóng nổi bọt vậy.
1
2
3
4
5
6
7
8
9
10
| void BubbleSort(int a[], int n){ for (int i = 0; i < n - 1; i++) { for (int j = n - 1; j > i; j--) { if (a[j] < a[j - 1]) swap(a[j], a[j - 1]); } }} |
Vì đây là thuật toán dễ cài đặt, sử dụng nên nó cũng khá là chậm. Với trường hợp xấu nhất có thể xảy ra, độ phức tạp của thuật toán này là O(n2), chậm nhất
2. Insertion sort
Insertion sort (hay còn gọi là Sắp xếp chèn) là 1 thuật toán khá đơn giản bằng cách chọn những phần tử nhỏ nhất để đưa lên đầu trong 1 dãy. Giống như ta đánh bài “tiến lên miền Nam” (mình không có tuyên truyền cờ bạc nha :v), chọn 13 lá. Duyệt từ trái qua phải, thấy lá nào nhỏ hơn 1 dãy lá bài bên trái thì bốc ra và nhét vào đúng vị trí sao cho dãy đã sắp xếp luôn tăng/giảm dần.
Insertion sort cũng vậy, ban đầu ta có 1 vị trí gọi là x. Dãy các phần tử từ 0 -> (x – 1) là dãy đã sắp xếp, còn dãy từ x -> n là dãy chưa được sắp xếp. Nhiệm vụ của ta là duyệt dãy x -> n, thấy phần tử nào thì tìm vị trí phù hợp trong dãy 0 -> (x – 1) mà nhét vào.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| void InsertionSort(int a[], int n){ int x, temp; for (int i = 1; i < n; i++) { x = i - 1; // Bắt đầu tìm x temp = a[i]; // Duyệt ngược từ phải qua, tìm vị trí phù hợp để chèn while (x >= 0 && a[x] > temp) { a[x + 1] = a[x]; x--; } a[x + 1] = temp; // Gán vào vị trí x đã tìm }} |
Insertion sort trong trường hợp tốt nhất (tất cả các phần tử đã được sắp xếp sẵn) thì độ phức tạp của thuật toán là O(n) (vì chỉ cần duyệt n lần từ trái qua, không có chèn). Tuy nhiên, với trường hợp xấu nhất thì độ phức tạp có thể lên tới O(n2).
3. Selection sort
Selection sort (hay còn gọi là Sắp xếp chọn), là 1 trong những thuật toán dễ cài đặt và học nhất. Đúng như tên gọi, ta chỉ cần duyệt hết mảng, thấy thằng nào nhỏ nhất thì nắm đầu nó vứt lên đầu bảng.
Để làm được điều này, ta cần có 1 biến x tương tự như Insertion sort. Ta duyệt từ x -> n, nếu tìm được phần tử nhỏ nhất thì ta hoán vị nó với vị trí x.
1
2
3
4
5
6
7
8
9
| void SelectSort(int a[], int n){ for (int i = 0; i < n; i++) { int x = i; for (int j = x; j < n; j++) if (a[x] > a[j]) x = j; swap(a[i], a[x]); }} |
Thuật toán này mặc dù có ưu việt là ít đổi chỗ các phần tử nhất, tuy nhiên vì ta phải tìm x, nên độ phức tạp của thuật toán cũng tương đương là O(n2).
4. Merge sort
Merge sort (hay còn gọi là Sắp xếp trộn) là 1 thuật toán điển hình của lối thuật toán Chia để trị(Divide and Conquer, D&C). Về ý tưởng thì ta chia 1 mảng lớn thành 2 mảng con, đến 1 điều kiện cụ thể (thường là chỉ còn 2 phần tử) rồi so sánh, sau đó gom từng mảng con lại thành mảng lớn để ra kết quả.
Giả sử ta có 2 mảng đã được sắp xếp sẵn là A = { 1, 3, 6, 9 } và B = { 2, 4, 5 }, ta muốn trộn 2 mảng đó thành 1 mảng lớn là AB thì ta cần phải so sánh 2 vị trí đầu tiên, nếu vị trí nào bé/lớn hơn thì ta cho vào mảng trộn:
- A = { 1, 3, 6, 9 }, B = { 2, 4, 5 }, 1 < 2 => AB = { 1 }
- A = { 3, 6, 9 }, B = { 2, 4, 5 }, 3 > 2 => AB = { 1, 2 }
- A = { 3, 6, 9 }, B = { 4, 5 }, 3 < 4 => AB = { 1, 2, 3 }
- A = { 6, 9 }, B = { 4, 5 }, 6 > 4 => AB = { 1, 2, 3, 4 }
- A = { 6, 9 }, B = { 5 }, 6 > 5 => AB = { 1, 2, 3, 4, 5 }
- A = { 6, 9 }, B = { }, B rỗng => nhét toàn bộ mảng A vào AB = { 1, 2, 3, 4, 5, 6, 9 }
1
2
3
4
5
6
7
8
9
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
54
55
56
57
58
59
| void Merge(int a[], int left, int mid, int right){ // Tạo 2 vị trí mảng con left -> mid và mid + 1 -> right int left1 = left, right1 = mid, left2 = mid + 1, right2 = right; int index = left; int *b = new int[right - left + 1]; while (left1 <= right1 && left2 <= right2) { if (a[left1] < a[left2]) // So sánh 2 vị trí đầu trong 2 mảng con { b[index] = a[left1]; // Bắt đầu trộn index++; left1++; // Xê dịch vị trí để tiếp tục so sánh } else { // Tương tự trên b[index] = a[left2]; index++; left2++; } } // Trường hợp 1 trong 2 mảng đã hết phần tử if (left2 > right2) { while (left1 <= right1) { b[index] = a[left1]; index++; right1++; } } if (left1 > right1) { while (left2 <= right2) { b[index] = a[left2]; index++; left2++; } } // Cuối cùng, ta gán mảng đã trộn lại vào mảng gốc for (index = left; index <= right; index++) { a[index] = b[index]; }}void MergeSort(int a[], int left, int right){ if (left < right) { int mid = (left + right) / 2; // Bắt đầu chia mảng lớn thành 2 mảng con MergeSort(a, left, mid); MergeSort(a, mid + 1, right); // Chia xong thì trộn thôi :3 Merge(a, left, mid, right); }} |
Tất nhiên, Merge sort có ưu điểm là nhanh hơn hẳn 3 loại sort phía trên, độ phức tạp của thuật toán O(n*log(n)). Tuy nhiên bạn phải hiểu rõ cơ chế của thuật toán, cộng với việc cài đặt tương đối khó.
5. Heap sort
Heap sort (hay còn gọi là Sắp xếp vun đống) là dạng sắp xếp dựa trên cây nhị phân. Cây nhị phân được xác định như sau: tại nút i có nút con trái là 2*(i + 1) – 1 và nút con phải là 2*(i + 1).
Ta xây dựng heap sao cho nút cha đều lớn hơn 2 nút con. Khi đó nút gốc có giá trị lớn nhất. Sau đó ta hoán vị nút gốc với nút thứ n – 1 và xây dựng lại heap mới từ 0 -> (n – 2) và nút cha lớn hơn 2 nút con. Lặp đi lặp lại việc xây dựng và hoán vị nút gốc với nút cuối trong heap, ta sẽ được mảng đã sắp xếp.
1
2
3
4
5
6
7
8
9
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
| // Ta xem i là nút chavoid MaxHeapify(int a[], int n, int i){ int left = 2*(i + 1) - 1; int right = 2*(i + 1); int max; // Tìm nút cha lớn nhất if (left < n && a[left] > a[i]) max = left; else max = i; if (right < n && a[right] > a[max]) max = right; if (i != max) { swap(a[i], a[max]); MaxHeapify(a, n, max); // Đệ quy với nút cha lần này là max }}void BuildHeap(int a[], int n){ // Xây dựng heap chỉ lặp nửa so với dãy mảng // Do ta cần xây dựng cây nhị phân nên cần phải đi từ nhánh về gốc // Vì vậy mảng cần phải duyệt từ giữa (nút con) về đầu (nút gốc) for (int i = n / 2 - 1; i >= 0; i--) { Heapify(a, n, i); }}void HeapSort(int a[], int n){ BuildHeap(a, n); // Lúc này a[0] là phần tử lớn nhất for (int i = n - 1; i > 0; i--) { swap(a[0], a[i]); Heapify(a, i, 0); }} |
Tương tự Merge sort, Heap sort có độ phức tạp của thuật toán O(n*log(n)). Vì vậy nên việc cài đặt và sử dụng Heap sort tương đối khó, và cần phải hiểu về cây nhị phân mới có thể sử dụng tốt.
6. Quicksort
Quicksort (còn được gọi là Sắp xếp nhanh) là 1 dạng thuật toán Divide and Conquer giống như Merge sort. Theo ý kiến cá nhân của mình, thì Quicksort được xem là thuật toán sắp xếp nhanh nhất (vậy nên nó mới có chữ “quick” chứ :v).
Quicksort chọn 1 phần tử trong mảng là chốt (pivot), thường ở vị trí giữa cho dễ tính (ta có thể chọn ở bất kì đâu, nhưng để tránh rơi vào vòng lặp vô tận thì cứ chọn ở giữa đi 😀 ). Ta đưa những phần tử nhỏ hơn pivot về danh sách thứ 1, và những phần tử lớn hơn pivot về danh sách thứ 2. Cứ như vậy, ta dùng đệ quy ở 2 phần danh sách con đến khi nào chỉ còn 1 phần tử.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| void QuickSort(int a[], int left, int right){ int i = left, j = right; int pivot = a[(left + right) / 2]; // Lấy pivot là phần tử giữa do { // Tìm vị trí i, j cần hoán vị while (a[i] < pivot && i < right) i++; while (a[j] > pivot && j > left) j--; if (i <= j) { swap(a[i], a[j]); i++; j--; } } while (i <= j); // Khi đó pivot sẽ chốt vị trí trong mảng // Ta cần gọi đệ hàm đến 2 mảng con bên trái pivot và bên phải pivot if (left < j) QuickSort(a, left, j); if (i < right) QuickSort(a, i, right);} |
Quicksort cũng tương tự như Merge sort, cũng có độ phức tạp thuật toán O(n*log(n)). Tuy nhiên, việc cài đặt Quicksort ngắn gọn hơn hẳn so với Merge sort hay Heap sort, và mình cũng rất hay sử dụng Quicksort.
nghe câu chữ thì đã thấy thằng Quick Sort có vẻ là nhanh rồi (Quick là nhanh mà :v), và thực tế, thì Quick Sort cũng là đáp án được nhiều người lựa chọn nhất khi được hỏi câu hỏi trên.
Nhưng thực tế, thì lại không phải vậy, phần lớn mọi người đã sai khi lựa chọn Quick Sort là câu trả lời của mình. Vậy đáp án là Tim Sort ư? hay Insertion Sort nhỉ
Cùng nhìn vào bảng thống kê độ phức tạp trung bình của các thuật toán sắp xếp
Nhìn vào bảng trên thì rõ ràng Quick Sort có độ phức tạp trung bình là O(n log(n)), ơ chẳng phải dựa vào kết quả này thì Quick Sort là nhanh nhất còn gì nữa?
Chậm lại 1 chút, chúng ta hãy thử đặt câu hỏi ngược lại ở đây xem sao nhé: "Nếu QuickSort là nhanh nhất thì tại sao lại còn phải đẻ ra ti tỉ các loại thuật toán sắp xếp khác làm cái lề gì nhỉ?"
Nhưng thực tế, thì lại không phải vậy, phần lớn mọi người đã sai khi lựa chọn Quick Sort là câu trả lời của mình. Vậy đáp án là Tim Sort ư? hay Insertion Sort nhỉ
Cùng nhìn vào bảng thống kê độ phức tạp trung bình của các thuật toán sắp xếp
Nhìn vào bảng trên thì rõ ràng Quick Sort có độ phức tạp trung bình là O(n log(n)), ơ chẳng phải dựa vào kết quả này thì Quick Sort là nhanh nhất còn gì nữa?
Chậm lại 1 chút, chúng ta hãy thử đặt câu hỏi ngược lại ở đây xem sao nhé: "Nếu QuickSort là nhanh nhất thì tại sao lại còn phải đẻ ra ti tỉ các loại thuật toán sắp xếp khác làm cái lề gì nhỉ?"
Tiếp theo, chúng ta sẽ xem tốc độ sắp xếp của các thuật toán dựa theo dữ liệu đầu vào, dữ liệu ở đây có các case từ dữ liệu Random đến Nearly Sorted hay cả việc Reversed Dữ liệu
Nhìn vào thống kê phía trên, có thể thấy với mỗi kiểu dữ liệu khác nhau thì lại có 1 kiểu sắp xếp chiếm ưu thế riêng, ví dụ với dữ liệu Nearly Sorted thì Insertion Sort là nhanh nhất nhưng khi với những kiểu dữ liệu phức tạp hơn thì Insertion Sort lại không phải là nhanh nhất.
Như vậy, từ những thống kê trên chúng ta đã dần dần hình dung ra đáp án cho câu hỏi "Thuật toán sắp xếp nào là nhanh nhất" rồi nhỉ
Nhìn vào thống kê phía trên, có thể thấy với mỗi kiểu dữ liệu khác nhau thì lại có 1 kiểu sắp xếp chiếm ưu thế riêng, ví dụ với dữ liệu Nearly Sorted thì Insertion Sort là nhanh nhất nhưng khi với những kiểu dữ liệu phức tạp hơn thì Insertion Sort lại không phải là nhanh nhất.
Như vậy, từ những thống kê trên chúng ta đã dần dần hình dung ra đáp án cho câu hỏi "Thuật toán sắp xếp nào là nhanh nhất" rồi nhỉ
Vậy câu trả lời đúng là gì?
=> "Không có 1 bất kỳ thuật toán sắp xếp nào cụ thể cả, nó còn phụ thuộc vào nhiều yếu tố"
Và "phụ thuộc vào nhiều yếu tố" cũng là lý do mà có rất nhiều loại thuật toán sắp xếp khác nhau ra đời. Chúng ta nhìn vào 1 vài ví dụ cụ thể dưới đây để thấy những yếu tố nào sẽ ảnh hưởng việc lựa chọn thuật toán
Và "phụ thuộc vào nhiều yếu tố" cũng là lý do mà có rất nhiều loại thuật toán sắp xếp khác nhau ra đời. Chúng ta nhìn vào 1 vài ví dụ cụ thể dưới đây để thấy những yếu tố nào sẽ ảnh hưởng việc lựa chọn thuật toán
- Quick Sort sẽ là tốt nhất nếu ...
- Không lo lắng về các case đầu vào kể cả trường hợp xấu nhất (trật tự nói chung là ngẫu nhiên)
- Không quan tâm đến dung lượng bộ nhớ, bộ nhớ là hoàn toàn lý tưởng và phù hợp ở đây
- Nếu dữ liệu đã được sắp xếp sẵn, thì nên chọn Insertion Sort hoặc Shell Sort sẽ tốt hơn.
- Nếu chúng ta thực sự phải loại bỏ case xấu nhất, có thể sử dụng Heap (hoặc ít nhất là Quick3) với độ phức tạp NlogN
- Tim Sort sẽ có độ phức tạp thấp hơn Quick Sort ở cả Best Case lẫn Worse Case, Tim Sort là sự kết hợp của Merge Sort và Insertion Sort. Python sử dụng thuật toán sắp xếp này là mặc định của họ
- Trong trường hợp, dữ liệu rất ít phần tử (10-20 phần tử), lựa chọn Selection Sort sẽ nhanh hơn Quick SortTóm lại 1 lần nữa , về lý thuyết thì Quick Sort thật sự là thuật toán sắp xếp nhanh nhất trong phần lớn các trường hợp. Tuy nhiên, trên thực tế, việc lựa chọn thuật toán sắp xếp dựa vào nhiều yếu tố như dữ liệu đầu vào số lượng như thế nào, có sắp xếp sẵn hay không, dung lượng bộ nhớ ra sao, tốc độ xử lý CPU...
Thuật toán và bài học cuộc sống
Mình vẫn thường hay nói đùa rằng: "Code không bao giờ lừa dối chúng ta cả". Và thực sự thì khi Code mình cũng chiêm nghiệm ra nhiều bài học cuộc sống cho chính mình luôn. Ở đây, từ một câu hỏi thuật toán sắp xếp vô cùng đơn giản nhưng chúng ta có thể rút ra được rất nhiều bài học thực tế:
- Hãy học cách đặt lại câu hỏi cho vấn để đang được hỏi, để từ đó phân tích tìm ra câu trả lời chính xác nhất. Đôi khi làm dự án thực tế, khách hàng sẽ đưa ra những yêu cầu mơ hồ, thay vì cắp đầu vào tìm giải pháp, hay code thì chúng ta hãy hỏi rõ khách hàng, làm rõ vấn đề đó trước đã
- Trong cuộc sống, không có gì là hoàn hảo cả hãy nhìn đặt vấn đề gặp phải dưới nhiều góc nhìn khác nhau, để cân nhắc và lựa chọn giải pháp cho hợp lý
Nhận xét
Đăng nhận xét