জিনোম সাজানোর জন্য সি++ প্রোগ্রাম?

এখানে আমরা দেখব কিভাবে জিনোম সর্ট কাজ করে। এটি আরেকটি সাজানোর অ্যালগরিদম। এই পদ্ধতিতে তালিকাটি ইতিমধ্যে সাজানো থাকলে এটি O(n) সময় নেবে। তাই সেরা ক্ষেত্রে সময় জটিলতা হল O(n)। কিন্তু গড় কেস এবং সবচেয়ে খারাপ কেস জটিলতা হল 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 the element is greater than previous one
         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