Dwarf sort

Dwarven sorting was first proposed on October 2, 2000 by Hamid Sarbazi-Azad. He called it "Stupid sorting, the simplest sorting algorithm with only one cycle ...". Indeed, this method is stupid or not, but is involved in it, in no way in most sorts - two or more cycles, but only one. Later, the Dutch scientist Dick Grun, in the pages of one of his books, gave the following analogy for the dwarf sort.

Dutch Garden Gnome (Du .: tuinkabouter). Here is a garden of flower pots. He and the previous one; If you are a potter, you may want to take a pot backwards. Boundary conditions: if there are no steps, he steps forwards; if there is no pot next to him, he is done.

Transfer:

Dwarven sorting is based on a technique used by an ordinary Dutch garden gnome. This is how a garden gnome sorts a number of flower pots. Essentially, he looks at two adjacent flower pots; if they are in the correct order, he moves forward one pot, otherwise he swaps them and returns to one pot back. Boundary conditions: if there is not a single pot behind - he steps forward, and if there is no next pot, then he has finished.

So described the main idea of ​​the algorithm of the dwarf sort Dick Grun. Replace the gnome and pots with more formal objects, such as a pointer (the number of the current element) and elements of the array, and consider the principle of the algorithm once again. First, the pointer is placed on the 2nd element of the array (in C ++ it has the number 1, and in Pascal the number 2). Then, two neighboring elements A [i] and A [i-1] are compared, that is, the first element (i-1) and the second (i) are compared. If they are in their positions, then move the pointer to the position i + 1 and continue the comparison from the new position; otherwise, we change elements in places, and, since at some point it may turn out that elements in the left subarray are not in their places, we move the pointer one position to the left, making the following comparison with the new position. So the algorithm continues to run until the entire array is ordered. Here we should highlight two important points. First, the ordering process ends, then when the condition i

Let's go over to the code itself. Dick Grun posted the following listing on his website:

The code given by Gruno allows you to organize the array, but it can still be slightly improved. Optimization will require some editing, in particular, the addition of one auxiliary variable, which will eliminate unnecessary comparisons. The following shows the listings of programs that sort the elements of an array in ascending order.

C ++ program code:

Pascal program code:

It seems a bit unusual, the fact that the sorting algorithm uses just one cycle. Plus, in practice, dwarf sorting is not inferior to the speed of sorting inserts, as can be seen from the table of three cases of these sortings.