Gnome Sort Program with Explanation and Code

2025-11-19 gnome sort stupid sort garden sort simple sorting algorithm python gnome sort c gnome sort javascript gnome sort php gnome sort csharp gnome sort beginner sorting algorithm

Gnome Sort is a simple comparison-based sorting algorithm that swaps adjacent elements and moves backward when necessary. This page provides a clear explanation and working code in Python, C, JavaScript, PHP, and C#.

Program Explanation

What is Gnome Sort?

Gnome Sort (also known as Stupid Sort or Garden Sort) is a simple sorting algorithm based on swapping adjacent elements, very similar to Bubble Sort. The key idea is that the algorithm moves backward whenever elements are in the wrong order and moves forward when they are correct. It mimics the behavior of a gnome arranging flower pots: if two adjacent pots are in the wrong order, the gnome swaps them and steps back; otherwise, it moves forward.

Steps to Solve

  1. Start at index 0 of the array.
  2. If at the beginning of the array, move one step forward.
  3. If the current pair of elements is in the right order, move forward.
  4. If the current pair is out of order, swap them and move one step backward.
  5. Repeat until the pointer reaches the end of the array.
  6. The array is sorted when no more swaps are required while moving forward.

Key Points

  • Simple and intuitive algorithm.
  • Similar to Bubble Sort but moves both backward and forward.
  • Works well for small datasets.
  • Time complexity: O(n²) worst-case.
  • Stable and in-place sorting algorithm.
  • No extra space required.

Program Code


def gnome_sort(arr):
    i = 0
    n = len(arr)

    while i < n:
        if i == 0 or arr[i] >= arr[i - 1]:
            i += 1
        else:
            arr[i], arr[i - 1] = arr[i - 1], arr[i]
            i -= 1

arr = list(map(int, input("Enter numbers: ").split()))
gnome_sort(arr)
print("Sorted array:", arr)
      

#include <stdio.h>

void gnomeSort(int arr[], int n) {
    int index = 0;

    while (index < n) {
        if (index == 0 || arr[index] >= arr[index - 1]) {
            index++;
        } else {
            int temp = arr[index];
            arr[index] = arr[index - 1];
            arr[index - 1] = temp;
            index--;
        }
    }
}

int main() {
    int n;
    printf("Enter number of elements: ");
    scanf("%d", &n);

    int arr[n];
    printf("Enter elements: ");
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    gnomeSort(arr, n);

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

    return 0;
}
      

function gnomeSort(arr) {
  let i = 0;

  while (i < arr.length) {
    if (i === 0 || arr[i] >= arr[i - 1]) {
      i++;
    } else {
      [arr[i], arr[i - 1]] = [arr[i - 1], arr[i]];
      i--;
    }
  }
}

let arr = prompt("Enter numbers:").split(" ").map(Number);
gnomeSort(arr);
console.log("Sorted array:", arr);
      

using System;

class Program {

    static void GnomeSort(int[] arr) {
        int i = 0;

        while (i < arr.Length) {
            if (i == 0 || arr[i] >= arr[i - 1]) {
                i++;
            } else {
                int temp = arr[i];
                arr[i] = arr[i - 1];
                arr[i - 1] = temp;
                i--;
            }
        }
    }

    static void Main() {
        Console.Write("Enter numbers: ");
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

        GnomeSort(arr);

        Console.Write("Sorted array: ");
        foreach (int x in arr)
            Console.Write(x + " ");
    }
}
      

<?php

function gnomeSort(&$arr) {
    $i = 0;
    $n = count($arr);

    while ($i < $n) {
        if ($i == 0 || $arr[$i] >= $arr[$i - 1]) {
            $i++;
        } else {
            $temp = $arr[$i];
            $arr[$i] = $arr[$i - 1];
            $arr[$i - 1] = $temp;
            $i--;
        }
    }
}

$arr = array_map('intval', explode(" ", readline("Enter numbers: ")));
gnomeSort($arr);

echo "Sorted array: " . implode(" ", $arr);

?>
1