Gnomesort

Gnomesort is a very simple and stable sorting algorithm.

Principle

Imagine a garden gnome ( garden gnome ), which comes before n flower pots, may have different sizes. The pots are placed in a left extending to the right row. On the far left is the garden gnome and want to sort the flower pots from left to right according to their size in ascending order.

To this end, he compares the two flower pots, it is facing straight. If he finds that they are in the correct order, so he takes a step to the right. If, however, he finds that the order is not right, so he swaps the two flower pots and makes a step to the left. If he can not go further to the left ( for example, if the first comparison led to the conclusion that the first and second flower pot in the wrong order were ), he takes a step to the right. This he repeated. Finished he is when he arrives at the rightmost flower pot. Since the right of it is no other flower pot more, no comparison can take place.

Another approach to explain this sorting algorithm is to refer to the comparison with bubblesort. This one looks Gnomesort only as a variant of bubblesort, which if successful exchange of elements the exchange direction or comparison direction changes, which can rise the bubbles quickly if necessary. However, the incorporation of a termination condition to ensure a faster exit in an assembled sorted array is not necessary for most implementations.

Was Gnomesort first as " Stupid Sort" described by Hamid Sarbazi - Azad and later referred to by Dick Grune as Gnomesort in 2000.

Runtime Analysis

The algorithm has a square and therefore in comparison to many other sorting algorithms poor worst-case running time. In computer science, one expresses this by Landau symbol by. In the best case, this algorithm has a running time of. Since the algorithm is an in -place method, he needs constant negligible additional memory.