Quick sort

When choosing a sorting algorithm for practical purposes, the programmer is likely to focus on a method called “Quick sorting” (also “qsort” from the English quick sort). It was developed in 1960 by English scientist Charles Hoar, who was then engaged in machine translation at Moscow State University. The algorithm, according to the principle of operation, is included in the class of exchange sorts (sorting by mixing, bubble sorting, etc.), being distinguished by a high speed of work.

A distinctive feature of quick sorting is the operation of dividing an array into two parts relative to the reference element. For example, if the sequence is to be ordered in ascending order, then all elements whose values ​​are less than the value of the support element will be placed in the left part, and the elements whose values ​​are greater than or equal to the reference element will be placed in the right part. Regardless of which element is selected as the reference, the array will be sorted, but still the situation is considered to be the most successful when there is approximately an equal number of elements on both sides of the reference element. If the length of any of the resulting parts of the partition exceeds one element, then for it you need to recursively perform the ordering, that is, re-run the algorithm on each of the segments.

Thus, the quick sort algorithm includes two main steps:

• partition of the array relative to the reference element;
• recursive sorting of each part of the array.

Array partitioning

Once again about the supporting element. His choice does not affect the result, and therefore can fall on an arbitrary element. However, as noted above, the highest efficiency of the algorithm is achieved by choosing a support element that divides the sequence into equal or approximately equal parts. But, as a rule, due to lack of information, it is not possible to determine such an element for certain, therefore, it is often necessary to choose a supporting element at random.

The following four paragraphs describe the near-program process of partitioning an array (sorting ascending):

1. the variables first and last are entered to denote the initial and final elements of the sequence, as well as the reference element mid;
2. formula (first + last) / 2 calculates the value of the middle element, and entered into the variable mid;
3. the values ​​of the elements are checked alternately for their correspondence to the position in which they are located, that is, the elements of the left and right parts are compared with the support element, and if it turns out that some elements Mas [i] (to the left of the reference) and Mas [j] (to the right of the reference) are not in their positions, they change places.
4. Step 3 continues to be performed until all elements fall into place with respect to the reference element (this in no way means that the array will be sorted at the end of the exchanges).

After splitting the sequence, you should check the condition for the need to continue further sorting of its parts, but this stage will be discussed later, and now we will split the array using an example.

Source array:

This array (let's call it Mas) consists of 8 elements: Mas [1..8]. The initial value of first is 1, and last is 8. The completed part is painted blue.

As a reference, we take an element with a value of 5 and an index of 4. We calculated it by the formula (first + last) / 2, discarding the fractional part. Now mid = 5.

Further, the first element of the left side is compared with mid: 3 less than 5, therefore it remains in its place, and first increases by 1. In the same way, the element with index 2 and value 7 is checked. Since the value of the second element exceeds the value of mid, it is remembered , and first remains equal to 2. It is the turn of a similar verification of the right side.

The right side is checked from the end. The values ​​of the first two elements (they have indices 7 and 8) are greater than the value of the support element, but for the third this is not true, since 1 <5. The element is remembered, the check of the right part is suspended for a while. Now last is 6.

The next step is a permutation. As we remember, first = 2, and last = 6, therefore, elements requiring castling are Mas [2] and Mas [6].

In the same way, we continue checking the remaining parts of the array until the condition first

At this stage of the partition is complete: the array is divided into two parts relative to the support element. It remains to make a recursive ordering of its parts.

Recursive ordering

If there is more than one element in any of the parts resulting from the partitioning of an array, then this part should be recursively ordered, that is, perform the partitioning operation described above. To check the condition "number of elements> 1", you need to act approximately as follows:

There is an array Mas [L..R], where L and R are indices of the extreme elements of this array. At the end of the split, the first and last pointers were approximately in the middle of the sequence, thus forming two segments: left from L to last and right from first to R. It is easy to verify such segments for a given condition.

Implements quick sort algorithm:

C ++ program code:

Pascal program code:

It is worth noting that quick sorting may be ineffective on arrays consisting of a small number of elements, so when working with them it is more reasonable to abandon this method. In general, the algorithm is unstable, and the use of recursion in incorrectly compiled code can lead to stack overflow. But, despite these and some other disadvantages, quick sorting is still one of the most efficient and frequently used methods.