Home » C/C++ Data Structure programs

# 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 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:**

**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

**Gnome Sorting Implementation:**

#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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions