In the last article, we pushed off from the so-called stupid sorting and, through simple metamorphoses, got the well-known bubble sorting . Transforming the latter, we came to a whole heap of exchange methods of ordering arrays. One of which, by the way, on structures up to several thousand elements, even works faster than quick sorting .

Today we will again take stupid sort as the basis and make another small but significant change to it. As a result, we obtain a completely different evolutionary series of sorting algorithms.

image: evolution

Silly sort

Too lazy to watch the first series , I recall that it is a stupid sort. We go around the array in order and, having met two unsorted neighbors, we swap them. Then we return to the start and "our song is good, start over." If in this sorting, instead of returning, we simply go further, then we get a “bubble”, which, as it turned out, can also be improved to infinity O ( n log n ).

Now we will do otherwise. Having exchanged two elements, we changed the order in the array, and we need to somehow find out if the new location comes into dissonance with those elements that we checked earlier. We will not jump to the beginning of the array, we will not go forward, but take a step back. If there is also no sorting now, then we will establish a strict order of precedence and take another step back. And so we will retreat until we reach the sorted part of the array. After that, you can move on again. Well, congratulations to those who did not know about this method. You just met a method whose name is ...

Dwarf Sort

image: Dutch garden gnome

Although the Dwarf has known this method for many centuries, the human race has learned about it recently. Already 55 years ago, mankind used merge sorting , 40 years passed when quick sorting became known , and after 35 years pyramidal sorting was developed - and now, only in 2000, this ingenious, almost childish technique was examined by Dick Grun :

Dwarf sorting is based on the technique used by the usual Dutch garden gnome (Dutch tuinkabouter). This is the method by which a garden gnome sorts a line of flower pots. Essentially, he looks at the next and previous garden pots: if they are in the correct order, he steps forward one pot, otherwise he swaps them and steps back one pot. Boundary conditions: if there is no previous pot, he steps forward; if there is no next pot, he is done.

Of course, people proposed a method for improvement, which conservative midgets did not think of. If you remember the place where an unsorted misunderstanding occurred and make several corrective iterations back, then after putting things in order in the rear, you can immediately jump to where you left off and follow the array further. It’s a little faster, although this temporal complexity doesn’t improve in principle, it remains O ( n ² ) as it was. But on the other hand, this leads us not only to a new sorting method, but even to a whole new sorting class. And the name of this group of algorithms is “ Insertion Sorts ”.

Simple insertion sorting

Here the segments of the array are progressively processed, starting from the first element and then expanding the subarray, we insert the next unsorted element into its place.

To insert, a buffer region of memory is used, in which an element is stored that has not yet been in its place (the so-called key element ). In a subarray, starting from the right edge, elements are scanned and compared with the key. If more than the key, then the next element is shifted one position to the right, freeing up space for subsequent elements. If as a result of this enumeration an element is found that is less than or equal to the key, then it means that you can insert the key element into the current free cell. The same optimized “gnome”, but only for exchange, a buffer is used.





The time complexity of this sort is O ( n ² ), but this is not the main thing. Insertion sorting seems to be the most efficient option for nearly sorted arrays. This fact is used in some complex sorting algorithms. I remember that I once spoke about FlashSort , where, using probability distribution , an almost sorted array is quickly created, which is then sorted by sorting by inserts. Insertion sorting is used in the final part of JSort , where by constructing an incomplete heap, the array is quickly almost sorted. Timsortstarts sorting the array by finding almost ordered segments in it, they are also sorted by the insert method, and then combined by a modified merge sort .

As you can see, although sorting by inserts by itself is slow, its scope is very wide.

Well, since so many letters are written about insertion sort , the story will not be complete, if not a few kind words about the algorithm called ...

Shell Sort

About sorting Shell already has an article on Habré , so I will be very brief.

The day before yesterday I already wrote how a very quick “comb” can be made from a very slow “bubble”. To do this, you first need to compare not the neighbors, but the elements between which an impressive distance is enough. This allows at the initial stage to throw small values ​​closer to the beginning of the array, large ones closer to the end. Then reducing the gap, already induce local orders in the array.

Shell sort uses the same strategy. Sort by inserting a subgroup of elements, but only in the subgroup they do not go in a row, but are evenly selected with some delta by index. By methodically reducing the distance between the elements of these disconnected subsets, we sort already much faster.



The time complexity of the “shell” is a rather complicated issue. The fact is that there is still no strict formula by which the optimal numerical series of varying distances between elements in subgroups is constructed. The sequence is built empirically, on the basis of numerous tests with different input data and the last best refinement for the aforementioned “deltas” was determined in 2001:

1, 4, 10, 23, 57, 132, 301, 701.

Shell invented the sorting, oddly enough , Donald Shell in 1959. In 2014, the author, by the way, turns 90 years old, still lives and lives, has recently married for the third time. So, invent algorithms, keep your brains in good shape - and you will survive 3 wives full-fledged long-term creative activity is provided to you.

References

Sorting algorithms in Wikipedia
Sorting Algorithm on Wikipedia
Bubble Sort and all-all-all
and about the sort again, choose the best algorithm
implementations sorts on Rosetta