Gnome Sort là một thuật toán sắp xếp dựa trên kiểu sắp xếp hoán vị (Bubble Sort). Nó được gọi là Gnome Sort vì giống như gnome trong truyền thuyết, nó chạy qua mảng và so sánh các phần tử liền kề và hoán vị chúng nếu cần. Nó tiếp tục chạy qua mảng cho đến khi tất cả các phần tử đều được sắp xếp theo thứ tự tăng dần hoặc giảm dần.
Các bài viết liên quan:
Độ phức tạp thời gian của Gnome Sort là O(n^2) như Bubble Sort, nhưng nó có một số tính năng tốt hơn trong một số trường hợp nhất định.
Ưu điểm của Gnome Sort
- Đơn giản: Gnome Sort là một thuật toán rất đơn giản và dễ hiểu vì nó chỉ yêu cầu so sánh và hoán vị hai phần tử liền kề nếu cần.
- Không cần bộ nhớ phụ: Gnome Sort không cần bộ nhớ phụ, chỉ cần một vòng lặp để thực hiện sắp xếp.
- Tốt trong trường hợp dữ liệu đầu vào đã được sắp xếp hoặc gần được sắp xếp: Gnome Sort hoạt động tốt hơn trong trường hợp dữ liệu đầu vào đã được sắp xếp hoặc gần được sắp xếp, vì nó chỉ cần di chuyển các phần tử cần thiết thay vì hoán vị tất cả các phần tử trong mảng.
- Tốt trong một số trường hợp đặc biệt: Gnome Sort có thể hoạt động tốt hơn trong một số trường hợp đặc biệt, như khi sử dụng trên một hệ thống giới hạn bộ nhớ.
Ví dụ Gnome Sort trong c++
#include <iostream>
using namespace std;
void gnomeSort(int arr[], int n) {
int index = 0;
while (index < n) {
if (index == 0)
index++;
if (arr[index] >= arr[index - 1])
index++;
else {
swap(arr[index], arr[index - 1]);
index--;
}
}
}
int main() {
int arr[] = { 34, 2, 10, -9 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Array before sorting: \n";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
gnomeSort(arr, n);
cout << "\nArray after sorting: \n";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}Giải thích đoạn code trên
Đoạn code trên là một ví dụ về thuật toán Gnome Sort trong C++.
gnomeSort là hàm chính sắp xếp mảng bằng thuật toán Gnome Sort. Trong hàm này, có một biến index để lưu vị trí hiện tại của mảng.
Trong vòng lặp while, nếu index = 0, index sẽ tăng lên 1. Nếu phần tử tại vị trí index lớn hơn hoặc bằng phần tử tại vị trí index - 1, index cũng sẽ tăng lên 1. Nếu không, hai phần tử sẽ được hoán vị bằng hàm swap và index sẽ giảm xuống 1.
Cuối cùng, mảng đã được sắp xếp và được in ra màn hình.
Độ phức tạp thuật toán Gnome Sort
Độ phức tạp thuật toán Gnome Sort là O(n^2), trong đó n là số lượng phần tử trong mảng.
Độ phức tạp này được xác định bằng việc tính số lần lặp của vòng while, trong đó mỗi lần lặp có thể di chuyển phần tử tới vị trí đúng của nó.
Tuy nhiên, Gnome Sort chỉ phù hợp với mảng có số lượng phần tử nhỏ vì hiệu suất tốt hơn của các thuật toán sắp xếp khác với mảng lớn.
