โปรแกรม C++ สำหรับ Gnome Sort

ที่นี่เราจะดูว่า Gnome Sort ทำงานอย่างไร นี่คืออัลกอริทึมการเรียงอีกตัวหนึ่ง ในแนวทางนี้ ถ้ารายการเรียงแล้ว จะใช้เวลา O(n) ดังนั้น best case time complexity คือ O(n) แต่ average case และ worst case complexity คือ O(n^2) ตอนนี้มาดูอัลกอริทึมเพื่อเข้าใจเทคนิคการเรียงนี้

อัลกอริทึม

gnomeSort(arr, n)

begin
    index := 0
    while index < n, do
        if index is 0, then
            index := index + 1
        end if
        if arr[index] >= arr[index - 1], then
            index := index + 1
        else
            exchange arr[index] and arr[index - 1]
            index := index - 1
        end if
    done
end

ตัวอย่าง

#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]) { // if element is greater than previous one
            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 << "Sorted Sequence ";
    gnomeSort(data, n);
    for(int i = 0; i < n; i++) {
        cout << data[i] << " ";
    }
}

ผลลัพธ์

Sorted Sequence 13 20 32 35 40 54 74 98 98 154