C program to implement Gnome sorting algorithm

Gnome Sorting Algorithm: Here, we are going to learn about the gnome sorting algorithm, how it works, and C language implementation of the gnome sort.
Submitted by Sneha Dujaniya, on June 19, 2020

Gnome sort is a very simple, unstable, and in-place sorting algorithm.

An unstable sorting algorithm is the one where two keys having equal values do not appear in the same order in the sorted output array as they are present in the input unsorted array.
An in-place sorting algorithm has various definitions but a more used one is – An in-place sorting algorithm does not need extra space and uses the constant memory for manipulation of the input in-place. Although, it may require some extra constant space allowed for variables.

Gnome sorting

Gnome sort is similar to the insertion sort algorithm as it works with one item at a time but the only difference is that in Gnome sort, we only swap the adjacent values much like in a Bubble sort.

The sorting algorithm is inspired by a Garden Gnome sorting his flower pots.

He looks at the pot next to him and the previous one. If they are in the right order, he moves one step forward, otherwise, he swaps them and moves one step backward.
If there is no previous pot (at the start of the line), he moves one step forwards. And if there is no pot beside him (at the end of the line), the work is complete.

Algorithm

At array index = 0, move one step backward or if array index = n-1, finish.
If the element at the current position is bigger than the previous one, move one step to the right.
Else swap the elements and move one step to the left.
Repeat steps 2 - 3 till you reach the end of the line.

Pseudo code

1.  Gnome_sort(arr):
2.  pos <- 0
3.  while pos < length(arr):
4.      if pos == 0 or arr[pos] >= arr[pos-1]:
5.          pos <- pos + 1
6.      else
7.          swap arr[pos] and arr[pos-1]
8.          pos <- pos – 1
9.      end if
10. end while

Example with explanation

Input Array: 5 3 2 4

Array	Position	Condition in effect	Action to take
5 3 2 4	0	pos == 0	pos ++
5 3 2 4	1	arr[pos] < arr[pos-1]	Swap, pos--
3 5 2 4	0	pos == 0	pos++
3 5 2 4	1	arr[pos] >= arr[pos-1]	pos++
3 5 2 4	2	arr[pos] < arr[pos-1]	Swap, pos--
3 2 5 4	1	arr[pos] < arr[pos-1]	Swap, pos--
2 3 5 4	0	pos == 0	pos ++
2 3 5 4	1	arr[pos] >= arr[pos-1]	pos ++
2 3 5 4	2	arr[pos] >= arr[pos-1]	pos ++
2 3 5 4	3	arr[pos] < arr[pos-1]	Swap, pos--
2 3 4 5	2	arr[pos] >= arr[pos-1]	pos ++
2 3 4 5	3	arr[pos] >= arr[pos-1]	pos ++
2 3 4 5	4	Length(arr) is reached	Finish

Time complexity

The time complexity of Gnome sort algorithm is

As there is only one loop present in the code, it might seem that the complexity is O(N) but that is not the case because the pos variable gets incremented and decremented both in the program.

Worst case: O(N^2)
Average Case: Ɵ(N^2)
Best case: Ω(N), when the list is already almost sorted
Space Complexity: Ɵ(1) constant

C program to implement Gnome sorting algorithm

#include <stdio.h>

void swap(int* x, int* y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

void gnome_sort(int arr[], int n)
{
    int pos = 0;

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

int main()
{
    int arr[] = { 12, 8, 5, 10, 13, 9 };
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("\nInput Array:\n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
        
    gnome_sort(arr, n);

    printf("\nSorted Array:\n");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}

Output

Input Array:
12 8 5 10 13 9
Sorted Array:
5 8 9 10 12 13