Gnome location
Gnomesort is a very simple and stable sorting algorithm .
principle
Imagine a garden gnome standing in front of n flower pots, which may have different sizes. The flower pots are arranged in a row from left to right. The garden gnome stands on the far left and wants to sort the flower pots in ascending order from left to right.
To do this, he compares the two flower pots in front of which he is currently standing. If he finds that they are in the correct order, he takes a step to the right. If, on the other hand, he finds that the order is incorrect, he swaps the two flower pots and takes a step to the left. If he cannot go any further to the left (for example, if the first comparison showed that the first and second flower pots were in the wrong order), he takes a step to the right. He repeats this over and over again. It's done when it arrives at the flower pot on the far right. Since there is no further flower pot to the right of it, a comparison can no longer be made.
Gnomesort was first described as "Stupid Sort" in 2000 by Hamid Sarbazi-Azad and later referred to as Gnomesort by Dick Grune.
comparison
- Gnomesort performs the same swap operations as Insertionsort, but compares some elements several times.
- More precisely, the difference is that Insertionsort is optimized to the effect that it saves the last upper list index (usually hidden in the form of a for loop ) and can therefore continue directly there after the successful bubbling down ; Gnomesort, on the other hand, carries out a series of new (actually unnecessary) comparisons to return to the last index above.
- In addition, Insertionort actually only carries out more cost-effective shifts instead of swaps.
- These two missing optimizations make Gnomesort one of the easiest sorting algorithms to program and are therefore its particular strength when runtime is not important.
- Compared to Bubblesort , the bubbles rise very slowly, but also descend.
- This means that Gnomesort is often faster than Bubblesort, but for example in the worst case of a list sorted backwards, Bubblesort has fewer comparisons than Gnomesort.
Runtime analysis
The algorithm has a quadratic and therefore poor worst-case runtime compared to many other sorting algorithms . In computer science, pressing it means Landau symbol by from. In the best case, this algorithm has a runtime of . Since the algorithm is an in-place process , it needs negligible constant additional memory.
See also
literature
- Hamid Sarbazi-Azad: Stupid Sort: A new sorting algorithm . In: Department of Computing Science Newsletter, University of Glasgow . tape 599 , no. 4 , October 2, 2000.