gnome Sort Algorithm
The gnome sort algorithm, also known as the "stupid sort" or "pathological sort," is a simple comparison-based sorting algorithm that was first proposed by Dr. Hamid Sarbazi-Azad in 2000. The algorithm is conceptually similar to the insertion sort, as it iteratively compares adjacent pairs and swaps them if they are in the wrong order. However, gnome sort uses a more intuitive approach that mimics the way a gnome would sort a line of flower pots by repeatedly swapping a misplaced pot with its neighbor until the entire line is sorted.
The name "gnome sort" is derived from the algorithm's garden gnome metaphor, which describes how the sorting process works. Imagine a garden gnome who is tasked with sorting a line of flower pots by size. The gnome starts at the beginning of the line and compares the height of the current pot with the height of the next pot. If the pots are in the correct order, the gnome moves forward; otherwise, the gnome swaps the pots and moves backward to compare the swapped pot with the previous one. The gnome continues this process, moving back and forth along the line until all the pots are sorted. Despite its simplicity and ease of implementation, gnome sort has a worst-case time complexity of O(n^2), making it inefficient for large data sets. However, it can perform well on partially ordered data and serves as a useful teaching tool for understanding the basics of sorting algorithms.
/*
* Gnome sort is a sort algorithm that moving an element to its proper place is accomplished by a series of swap
* more information: https://en.wikipedia.org/wiki/Gnome_sort
*
*/
function gnomeSort (items) {
if (items.length <= 1) {
return
}
let i = 1
while (i < items.length) {
if (items[i - 1] <= items[i]) {
i++
} else {
[items[i], items[i - 1]] = [items[i - 1], items[i]]
i = Math.max(1, i - 1)
}
}
}
// Implementation of gnomeSort
var ar = [5, 6, 7, 8, 1, 2, 12, 14]
// Array before Sort
console.log(ar)
gnomeSort(ar)
// Array after sort
console.log(ar)
