Chào mừng bạn đến với bài viết này! Chúng ta đã quen thuộc với các thuật toán sắp xếp như Bubble sort, Quick sort, Heap sort, Counting sort và nhiều thuật toán khác. Tuy nhiên, có một số giải thuật sắp xếp ít "quen thuộc" hơn mà có thể bạn chưa biết đến. Hãy cùng khám phá những giải thuật này có gì đặc biệt nhé!
Sắp xếp chèn: Thuật toán đơn giản nhưng hiệu quả
1. Ví dụ về sắp xếp chèn
Hãy tưởng tượng bạn đang chơi một trò chơi với các lá bài từ 1 đến 10. Mỗi khi bạn bốc một lá bài, bạn cần sắp xếp chúng trên tay theo thứ tự tăng dần từ trái qua phải. Quá trình sắp xếp này giống với thuật toán "sắp xếp chèn". Đầu tiên, bạn sẽ có một lá bài đầu tiên đã được sắp xếp. Tiếp theo, mỗi lá bài mới sẽ được so sánh với các lá bài trước đó và được chèn vào vị trí thích hợp trong dãy đã sắp xếp. Thuật toán này diễn ra cho đến khi bạn có một dãy bài đã được sắp xếp đúng thứ tự.
2. Cài đặt thuật toán
Để cài đặt thuật toán sắp xếp chèn bằng ngôn ngữ C++, bạn có thể sử dụng mã sau:
void Insertion_sort(int a[], int n) {
int index, new_number;
for (int i = 1; i < n; i++){
index = i;
new_number = a[i];
while (index > 0 && a[index - 1] > new_number){
a[index] = a[index - 1];
index--;
}
a[index] = new_number;
}
}3. Đặc điểm và ưu điểm của sắp xếp chèn
Thuật toán sắp xếp chèn có một số đặc điểm và ưu điểm đáng chú ý:
- Thực hiện thao tác đơn giản và dễ hiểu.
- Hiệu quả với các số liệu nhỏ.
- Hiệu quả hơn các thuật toán sắp xếp khác có độ phức tạp thời gian O(n^2).
- Phù hợp với các số liệu đã được sắp xếp sẵn.
- Tính ổn định, không làm thay đổi thứ tự các phần tử gốc.
- Sử dụng một cách phương pháp, dễ nhớ và sử dụng.
Tuy nhiên, thuật toán sắp xếp chèn không phù hợp với các số liệu lớn do độ phức tạp thời gian trung bình là O(n^2). Thay vào đó, nó có thể được áp dụng trong các tình huống cụ thể, chẳng hạn như sắp xếp một số phần tử nhỏ trong một dãy lớn. Thêm vào đó, một số thư viện ngôn ngữ như STL-C++ cũng sử dụng sắp xếp chèn cho các số liệu nhỏ.
Sắp xếp chọn: Thuật toán đơn giản và không ổn định
1. Ví dụ về sắp xếp chọn
Thuật toán sắp xếp chọn cũng là một giải thuật đơn giản. Bạn có hai dãy con đã được sắp xếp theo thứ tự tăng dần. Nhiệm vụ của bạn là hợp nhất hai dãy con này để tạo thành một dãy lớn hơn cũng theo thứ tự tăng dần. Ví dụ, từ hai dãy con [2, 4, 6] và [1, 3, 4], bạn sẽ có được dãy kết quả là [1, 2, 3, 4, 4, 6].
2. Cài đặt thuật toán
Để cài đặt thuật toán sắp xếp chọn bằng ngôn ngữ C++, bạn có thể sử dụng mã sau:
void Selection_sort(int a[], int n){
int min_index;
for (int i = 0; i < n - 1; i++){
min_index = i;
for (int j = i + 1; j < n; j++){
if (a[min_index] > a[j]){
min_index = j;
}
}
if (i != min_index){
int temp = a[i];
a[i] = a[min_index];
a[min_index] = temp;
}
}
}3. Đặc điểm và ưu điểm của sắp xếp chọn
Sắp xếp chọn có các đặc điểm và ưu điểm sau:
- Ý tưởng đơn giản nhưng thực hiện phức tạp hơn sắp xếp chèn.
- Độ phức tạp thời gian là O(n^2), tương tự như sắp xếp chèn.
- Không ổn định, có thể thay đổi thứ tự các phần tử với giá trị giống nhau.
- Tuy nhiên, sắp xếp chọn vẫn có thể áp dụng linh hoạt trong các tình huống cụ thể và có thể kết hợp với các thao tác tìm kiếm để đạt hiệu quả tối ưu.
Sắp xếp trộn: Thuật toán đa phương pháp
1. Mô tả về sắp xếp trộn
Thuật toán sắp xếp trộn sử dụng ý tưởng "chia để trị" đối với một dãy cho trước. Ý tưởng chia để trị là việc chia một sự việc thành nhiều sự việc có quy mô nhỏ hơn nhưng vẫn giữ nguyên tính chất và mục đích ban đầu, sau đó thực hiện các thao tác tương tự trên các sự việc nhỏ hơn.
Thuật toán sắp xếp trộn được thực hiện thông qua ba bước chính:
- Chia dãy ban đầu thành các dãy con nhỏ hơn.
- Sắp xếp các dãy con theo thứ tự.
- Gộp các dãy con lại thành dãy đã sắp xếp.
2. Cài đặt thuật toán
Để cài đặt thuật toán sắp xếp trộn bằng ngôn ngữ C++, bạn có thể sử dụng mã sau:
void Merge(int arr[], int l, int m, int r){
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++){
L[i] = arr[l + i];
}
for (j = 0; j < n2; j++){
R[j] = arr[m + 1 + j];
}
i = 0; j = 0; k = l;
while (i < n1 && j < n2){
if (L[i] <= R[j]){
arr[k] = L[i];
i++;
}
else{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1){
arr[k] = L[i];
i++;
k++;
}
while (j < n2){
arr[k] = R[j];
j++;
k++;
}
}
void Merge_sort(int a[], int l, int r){
if (l < r){
int m = l + (r - l) / 2;
Merge_sort(a, l, m);
Merge_sort(a, m + 1, r);
Merge(a, l, m, r);
}
}
void Print_array(int a[], int n){
for (int i = 0; i < n; i++){
cout << a[i] << " ";
}
}3. Đặc điểm và ưu điểm của sắp xếp trộn
Thuật toán sắp xếp trộn có các đặc điểm và ưu điểm sau:
- Giai đoạn chia thành các dãy con chỉ mất thời gian tìm vị trí trung gian để chia dãy làm hai, vì vậy độ phức tạp thời gian là O(1).
- Giai đoạn sắp xếp các dãy con và gộp các dãy con lại tốn O(n.log(n)) phần tử.
- Không phải là thuật toán sắp xếp tại chỗ.
- Có thể kết hợp với các thao tác tìm kiếm để đạt hiệu quả tối ưu.
Tổng kết
Như vậy, đó là một số thuật toán sắp xếp ít người biết. Mỗi thuật toán có ý tưởng, ưu, nhược điểm riêng của nó. Chúng ta cần hiểu về bản chất và tư duy của thuật toán, không nên sử dụng một cách cố định mà phải phân tích tình huống cụ thể và kết hợp các thuật toán phù hợp. Việc tìm ra hướng đi tối ưu và học hỏi những điều quý giá mới là mục tiêu của chúng ta. Hãy sáng tạo và phát triển các thuật toán sắp xếp để tạo ra những giải pháp độc đáo và tối ưu!
Tài liệu tham khảo:
©️ Tác giả: Lê Ngọc Hoa từ Viblo
