C++-এ গনোম সর্ট (Gnome Sort)

এখানে আমরা দেখব গনোম সর্ট কীভাবে কাজ করে। এটি আরেকটি সর্টিং অ্যালগরিদম। এই পদ্ধতিতে যদি লিস্ট ইতিমধ্যে সর্টেড থাকে তবে এটি O(n) সময় নেয়। তাই বেস্ট কেস টাইম কমপ্লেক্সিটি O(n)। কিন্তু অয়ারেজ কেস এবং ওয়ার্স্ট কেস কমপ্লেক্সিটি O(n²)। এখন এই সর্টিং টেকনিক সম্পর্কে আইডিয়া পাওয়ার জন্য অ্যালগরিদম দেখি।

অ্যালগরিদম

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]){ // যদি এলিমেন্ট পূর্বেরটির চেয়ে বড় হয়
            index++;
        } else {
            swap(arr[index], arr[index - 1]);
            index--;
        }
    }
}
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