×

Cài đặt thuật toán Gnome Sort trong lập trình

Avatar of admin
admin 0 Views

Khi làm việc với các thuật toán sắp xếp, chúng ta thường nghĩ ngay tới những cái tên như Quick Sort, Merge Sort hay Bubble Sort. Tuy nhiên, bên cạnh những thuật toán phổ biến này còn có một số thuật toán khác cũng rất hữu ích và dễ hiểu như Gnome Sort. Cùng khám phá cách cài đặt thuật toán Gnome Sort trong lập trình nhé!

Giới thiệu về Gnome Sort

Gnome Sort là một thuật toán sắp xếp đơn giản, hoạt động dựa trên nguyên lý giống như phương pháp sắp xếp bài thủ công của con người. Thuật toán này có tên gọi khác là Stupid Sort, vì tính chất khá tương đồng với thuật toán Bubble Sort nhưng hoạt động theo cách trực quan hơn, như việc gnome (người tí hon) chỉnh sửa các vật thể để chúng về đúng thứ tự.

Nguyên lý hoạt động

  1. Bắt đầu từ đầu mảng.
  2. So sánh phần tử hiện tại với phần tử ngay trước nó:
    • Nếu chúng theo đúng thứ tự, tiếp tục xét phần tử kế tiếp.
    • Nếu sai thứ tự, hoán đổi hai phần tử và lùi lại một vị trí để tiếp tục so sánh.
  3. Lặp lại quá trình trên cho đến khi mảng được sắp xếp.

Thuật toán kết thúc khi chỉ còn lại đúng thứ tự từ đầu đến cuối mảng.

Mã giả

function gnomeSort(a):
    pos = 0
    while pos < length(a):
        if pos == 0 or a[pos] >= a[pos-1]:
            pos = pos + 1
        else:
            swap a[pos] and a[pos-1]
            pos = pos - 1

Cài đặt Gnome Sort bằng Python

def gnome_sort(arr):
    pos = 0
    n = len(arr)
    
    while pos < n:
        if pos == 0 or arr[pos] >= arr[pos - 1]:
            pos += 1
        else:
            arr[pos], arr[pos - 1] = arr[pos - 1], arr[pos]
            pos -= 1
    
    return arr

# Ví dụ sử dụng
arr = [34, 2, 78, 1, 56, 99]
print("Mảng trước khi sắp xếp:", arr)
sorted_arr = gnome_sort(arr)
print("Mảng sau khi sắp xếp:", sorted_arr)

Cài đặt Gnome Sort bằng C++

#include <iostream>
#include <vector>
using namespace std;

void gnomeSort(vector<int>& arr) {
    int pos = 0;
    int n = arr.size();
    
    while (pos < n) {
        if (pos == 0 || arr[pos] >= arr[pos - 1]) {
            pos++;
        } else {
            swap(arr[pos], arr[pos - 1]);
            pos--;
        }
    }
}

int main() {
    vector<int> arr = {34, 2, 78, 1, 56, 99};
    cout << "Mảng trước khi sắp xếp: ";
    for (int num : arr)
        cout << num << " ";
    cout << endl;
    
    gnomeSort(arr);
    
    cout << "Mảng sau khi sắp xếp: ";
    for (int num : arr)
        cout << num << " ";
    cout << endl;
    return 0;
}

Ưu điểm và nhược điểm

Ưu điểm:

  • Dễ hiểu và dễ cài đặt.
  • Phù hợp cho các mảng nhỏ và các tình huống khi đơn giản là yếu tố cần ưu tiên.

Nhược điểm:

  • Hiệu suất kém với các mảng lớn do độ phức tạp thời gian của thuật toán này là O(n^2).
  • Ít khi được dùng trong thực tế cho các ứng dụng yêu cầu sắp xếp hiệu quả.

Kết luận

Gnome Sort tuy không mạnh mẽ như Quick Sort hay Merge Sort, nhưng với tính đơn giản và trực quan, nó là một lựa chọn tốt để bắt đầu tìm hiểu về các thuật toán sắp xếp. Hy vọng rằng qua bài viết này, bạn đã có cái nhìn rõ hơn về cách cài đặt và sử dụng thuật toán này trong lập trình.

Comments

Bài viết liên quan