In the last article, we pushed away from the so-called stupid sort, and through simple metamorphoses, we got everyone a well-known bubble sort . Transforming the latter 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 the stupid sort as a 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

')

Stupid sorting

Who is too lazy to watch the first series , I remind you what a silly sort is. 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, just go on, then we get a “bubble”, which, as it turned out, can also be improved to infinity O ( n log n ).



Now we will act differently. Having exchanged two elements, we changed the order in the array, and we need to somehow find out whether the new arrangement enters into discord with those elements that we checked earlier. We will not jump into the beginning of the array, we will not go forward, but take a step back. If there is now also not sorted, then we set 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 have just met a method whose name is ...

Dwarf sort

image: dutch garden gnome



Although the gnomes have known this method for many centuries, the human race has learned about it quite recently. Already 55 years since humanity used merge sorting , 40 years have passed since fast sorting became known, already 35 years later, as a pyramid sorting was developed - and only in 2000, this unsophisticated, practically childish technique was investigated by Dick Grun :

Dwarf sorting is based on a technique used by the usual Dutch garden gnome (niderl. 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 walks forward one pot, otherwise he swaps them and walks back one pot. Boundary conditions: if there is no previous pot, he strides forward; if there is no next pot, he is finished.

Of course, people offered a way to improve, which the conservative Lilliputians did not think of. If you memorize the place in which you encountered an unsorted misunderstanding and did a few corrective iterations back, then after restoring order in the rear, you can jump right to where you left off and follow the array further.







So a little faster, although in principle this temporary complexity does not improve, it both was and remains O ( n ² ). But this brings 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 ”.

Sort by simple inserts

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



For insertion, a buffer area of ​​memory is used in which an element is stored that has not yet appeared in its place (the so-called key element ). In the sub-array, starting from the right edge, the elements are viewed and compared with the key. If more key, then the next element is shifted one position to the right, making room for subsequent elements. If as a result of this search, an element less than or equal to the key is found, then the key element can be inserted into the current free cell.







The same optimized "gnome", but only for the exchange buffer is used.



The time complexity of this sorting is O ( n ² ), but this is not the main thing. Sorting inserts, apparently - the most effective option for almost sorted arrays. This fact is used in some complex sorting algorithms. I remember that I once talked about FlashSort , where, using a probability distribution , an almost sorted array is quickly created, which is then reordered by sorting inserts. Insertion sorting is used in the final part of JSort , where by building an incomplete heap, the array is almost sorted operatively. Timsort begins to sort the array by finding almost ordered segments in it, they are also sorted by the insertion method, and then combined by the modified merge sort .



As you please, although the sorting by inserts 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, which is called ...

Shell sort

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



The day before yesterday already wrote how a very fast “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 there is a rather impressive distance. This allows at the initial stage, small values ​​to throw closer to the beginning of the array, large - closer to the end. Then, reducing the gap, we will already impose local orders in the array.



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







The time complexity of the "shell" - a rather complicated question. The fact is that so far there is no strict formula by which the optimal numerical series of varying distances between elements in subgroups is built. The sequence is built empirically, based on numerous tests with various inputs, and the last best refinement for the above-mentioned “deltas” was determined in 2001:



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



Sorting Shell invented, oddly enough, Donald Shell in 1959. In 2014, the author, by the way, turns 90 years old, lives and lives to this day, recently got married for the third time. So, invent algorithms, keep your brains in good shape - and outlive the 3 wives of a full-fledged many years of creative activity you provided.

Links

Wikipedia sorting algorithms

Sorting Algorithm on Wikipedia

Bubble sort and all-all-all

And again about sorting: choose the best algorithm

Implementing sortings on Rosette