# What is Gnome Sort

**Gnome sort**is a simple sorting algorithm that works by repeatedly comparing adjacent elements in a list and swapping them if they are in the wrong order.

The algorithm works like this: starting from the beginning of the list, it compares the first two elements and swaps them if necessary. It then moves on to compare the second and third elements, and so on, until it reaches the end of the list.

If at any point during this process, two adjacent elements are swapped, the algorithm goes back one step and compares the previous element with the current one again. This step is called a "gnome" step, hence the name "gnome sort".

The algorithm continues in this way until the entire list is sorted. While gnome sort is not the most efficient sorting algorithm, it is easy to implement and works well for small or partially sorted lists.

## Who invented it?

The inventor of Gnome sort is unknown. The algorithm is believed to have been discovered by Dr. Hamid Sarbazi-Azad, a computer science professor at the University of Tehran in Iran, in the early 1990s. However, there are also claims that the algorithm was invented by a group of programmers in the 1980s who called it "Stupid sort". The algorithm gained its current name in the early 2000s, when a computer science professor named Dick Grune used the term "gnome sort" in a lecture on sorting algorithms. Since then, the term has been widely used to refer to this sorting algorithm.

## Pseudocode

```
gnomeSort(array):
i = 0
while i < length(array):
if i == 0 or array[i] >= array[i-1]:
i = i + 1
else:
swap array[i] and array[i-1]
i = i - 1
```

The gnomeSort function takes an array of elements as input and sorts it in ascending order using the Gnome sort algorithm.

The algorithm uses a while loop to iterate over the array. At each step, it compares the current element with the previous one and swaps them if they are in the wrong order.

If a swap is made, the algorithm goes back one step and checks the new pair of elements again. If no swap is made, the algorithm moves on to the next pair of elements.

The loop continues until the entire array is sorted, at which point the function returns the sorted array.

The algorithm uses a while loop to iterate over the array. At each step, it compares the current element with the previous one and swaps them if they are in the wrong order.

If a swap is made, the algorithm goes back one step and checks the new pair of elements again. If no swap is made, the algorithm moves on to the next pair of elements.

The loop continues until the entire array is sorted, at which point the function returns the sorted array.

## Sample Code

```
// C++ code snippet
void gnomeSort(int arr[], int n) {
int i = 0;
while (i < n) {
if (i == 0 || arr[i] >= arr[i-1]) {
i++;
} else {
swap(arr[i], arr[i-1]);
i--;
}
}
}
int main() {
int arr[] = { 5, 2, 9, 3, 1, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << "Before sorting: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
gnomeSort(arr, n);
cout << "\nAfter sorting: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
```

```
# Python code snippet
def gnomeSort(arr):
i = 0
while i < len(arr):
if i == 0 or arr[i] >= arr[i-1]:
i += 1
else:
arr[i], arr[i-1] = arr[i-1], arr[i]
i -= 1
# Example usage
arr = [5, 2, 9, 3, 1, 6]
print("Before sorting:", arr)
gnomeSort(arr)
print("After sorting:", arr)
```

```
public class GnomeSort {
public 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--;
}
}
}
public static void main(String[] args) {
int[] arr = { 5, 2, 9, 3, 1, 6 };
System.out.print("Before sorting: ");
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
gnomeSort(arr);
System.out.print("After sorting: ");
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println();
}
}
```

## Time and Space Complexity

The time complexity of Gnome sort algorithm is O(n^2), where "n" is the number of elements in the array.

In the best case, when the array is already sorted, the time complexity reduces to O(n) as the algorithm makes just one pass over the array.

In the worst case, when the array is in reverse order, the algorithm will make n-1 passes over the array, each pass checking and potentially swapping each element with its predecessor. This results in the time complexity of O(n^2).

The space complexity of the Gnome sort algorithm is O(1) since it does not require any additional space to perform the sorting. The algorithm performs all the operations in place by swapping elements within the input array.

In the best case, when the array is already sorted, the time complexity reduces to O(n) as the algorithm makes just one pass over the array.

In the worst case, when the array is in reverse order, the algorithm will make n-1 passes over the array, each pass checking and potentially swapping each element with its predecessor. This results in the time complexity of O(n^2).

The space complexity of the Gnome sort algorithm is O(1) since it does not require any additional space to perform the sorting. The algorithm performs all the operations in place by swapping elements within the input array.

## Advantages

- Simple implementation: The Gnome sort algorithm is easy to implement and understand, which makes it a good choice for educational purposes or small datasets.
- Efficient for partially sorted data: Gnome sort performs well on data that is partially sorted or nearly sorted, since it only requires a few swaps to put the remaining unsorted elements in their correct position.
- Space efficient: Gnome sort is an in-place sorting algorithm, which means it does not require additional memory to sort the input array.

## Disadvantages

- Poor performance on large datasets: Gnome sort has a time complexity of O(n^2), which makes it inefficient for large datasets. Other sorting algorithms like Merge sort, Quick sort, or Heap sort have a better time complexity of O(n log n).
- Slow for unsorted data: In the worst case, when the input data is completely unsorted, Gnome sort has to make many passes over the input array to sort it, leading to a large number of comparisons and swaps. This results in a slow sorting time.
- Not stable: Gnome sort is not a stable sorting algorithm, which means that it does not preserve the relative order of equal elements. If you have an array of objects that need to be sorted by multiple keys, you cannot rely on Gnome sort to keep them sorted in a specific order.