Chương trình C++ cho thuật toán Gnome Sort

Gnome Sort (Sắp xếp gnome) là thuật toán sắp xếp đơn giản, tương tự Insertion Sort nhưng chỉ dùng một vòng lặp. Nếu danh sách đã sắp xếp, chỉ O(n) - trường hợp tốt nhất. Trung bình và xấu nhất O(n²).

Ý tưởng

Gnome (người lùn) đi dọc mảng: nếu phần tử hiện tại ≥ phần tử trước → tiến lên; ngược lại → hoán đổi và lùi lại một bước. Giống như người trồng hoa sắp xếp chậu hoa.

Thuật toán

gnomeSort(arr, n):
    index = 0
    while index < n:
        if index == 0: index++
        else if arr[index] >= arr[index-1]: index++
        else: swap(arr[index], arr[index-1]); index--
    end
end

Code ví dụ

#include <iostream>
#include <algorithm> // cho swap
using namespace std;

void gnomeSort(int arr[], int n) {
    int index = 0;
    while (index < n) {
        if (index == 0) {
            index++;
        } else if (arr[index] >= arr[index-1]) {
            index++;
        } else {
            swap(arr[index], arr[index-1]);
            index--;
        }
    }
}

int main() {
    int data[] = {54, 74, 98, 154, 98, 32, 20, 13, 35, 40};
    int n = sizeof(data)/sizeof(data[0]);
    
    cout << "Day truoc: ";
    for(int x : data) cout << x << " ";
    
    gnomeSort(data, n);
    
    cout << "\nDay sau:  ";
    for(int x : data) cout << x << " ";
    return 0;
}

Kết quả

Day truoc: 54 74 98 154 98 32 20 13 35 40
Day sau:  13 20 32 35 40 54 74 98 98 154

Độ phức tạp

• Tốt nhất: O(n) - mảng đã sắp xếp.
• Trung bình: O(n²).
• Xấu nhất: O(n²) - mảng sắp xếp ngược.
• Không gian: O(1).
• Ổn định: Có.

So sánh với Insertion Sort

Gnome Sort tương đương Insertion Sort nhưng không dùng lặp lồng. Insertion Sort dùng key + dịch chuyển, Gnome Sort dùng swap + lùi lại. Insertion Sort thường nhanh hơn do ít swap hơn.