C++ Program for Gnome Sort?

Here we will see how the gnome sort works. This is another sorting algorithm. In this approach if the list is already sorted it will take O(n) time. So best case time complexity is O(n). But average case and worst case complexity is O(n^2). Now let us see the algorithm to get the idea about this sorting technique.

Algorithm

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

Example

 Live Demo

#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] << " ";    } }

Output

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