Quick sort

Hello. Today we continue the series of articles that I wrote specifically for the launch of the course “Algorithms and Data Structures” from OTUS. By link you can find out in detail about the course, as well as watch the recording of the Demo lesson on the topic for free: “Three algorithms for finding a pattern in the text”…

Introduction

Sorting an array is one of the first serious problems studied in the classic course “Algorithms and Data Structures” of the computer science discipline. In this regard, the tasks of writing sorting and the corresponding questions are often encountered in interviews as an intern or junior developer.

Formulation of the problem

Traditionally, it is worth starting the presentation of solutions to the problem with its statement. Usually the sorting task involves ordering some array of integers in ascending order. But in fact, this is somewhat oversimplification. The algorithms described in this section can be used to order an array of any objects between which an ordering relationship is established (that is, for any two elements we can say: the first is greater than the second, the second is greater than the first, or they are equal). You can sort both in ascending and descending order. We’ll use the standard simplification.

Last time we talked about a slightly more complex sort – insertion sort. Today we will focus on a much more complex algorithm – quick sort (also called Hoare sort).

Algorithm Description

The quick sorting algorithm is recursive, therefore, for simplicity, the procedure will take as input the boundaries of an array segment from l inclusive to r not inclusive. It is clear that in order to sort the entire array, 0 should be passed as the l parameter, and n as r, where, by tradition, n denotes the length of the array.

The quicksort algorithm is based on the partition procedure. Partition selects some element of the array and rearranges the elements of the array in such a way that the array is split into 2 parts: the left side contains elements that are less than this element, and the right side contains elements that are greater than or equal to this element. Such a separating element is called pivot…

Partiion implementation:
partition(l, r): pivot = a[random(l ... r - 1)] m = l for i = l ... r - 1: if a[i] < pivot: swap(a[i], a[m]) m++ return m

The pivot in our case is chosen randomly. This algorithm is called randomized… In fact, the pivot can be selected in a variety of ways: either take a random element, or take the first / last element of the uchchka, or choose it in some “smart” way. The choice of pivot is very important for the final complexity of the sorting algorithm, but more on that later. The complexity of the partition procedure is O (n), where n = r – l is the length of the section.

Now we use partition to implement sorting:

Partiion implementation:
sort(l, r): if r - l = 1: return m = partition(l, r) sort(l, m) sort(m, r)

An extreme case – an array of one element has the property of being ordered. If the array is long, then we use partition and call the procedure recursively on the two halves of the array.

If you run the written sorting using the example of the array 1 2 2, you will notice that it will never end. Why did it happen?

When writing partition, we made an assumption – all elements of the array must be unique. Otherwise, the return value of m will be l and the recursion will never end, because sort (l, m) will call sort (l, l) and sort (l, m). To solve this problem, you need to divide the array not into 2 parts ( = pivot), but into 3 parts ( pivot) and call recursive sorting for the 1st and 3rd parts.

Analysis

I propose to analyze this algorithm.

The time complexity of the algorithm is expressed through it by the formula: T (n) = n + T (a * n) + T ((1 – a) * n). Thus, when we call the sorting of an array of n elements, it takes about n operations to execute the partition and to execute itself 2 times with the parameters a * n and (1 – a) * n, because the pivot divided the element into fractions.

In the best case, a = 1/2, that is, the pivot divides the area into two equal parts each time. In this case: T (n) = n + 2 * T (n / 2) = n + 2 * (n / 2 + 2 * T (n / 4)) = n + n + 4 * T (n / 4 ) = n + n + 4 * (n / 4 + 2 * T (n / 8)) = n + n + n + 8 * T (n / 8) =…. Total will be log (n) terms, because the terms appear until the argument decreases to 1. As a result, T (n) = O (n * log (n)).

In the worst case, a = 1 / n, that is, the pivot cuts off exactly one element. The first part of the array contains 1 element, and the second contains n – 1. That is: T (n) = n + T (1) + T (n – 1) = n + O (1) + T (n – 1) = n + O (1) + (n – 1 + O (1) + T (n – 2)) = O (n ^ 2). The square appears due to the fact that it appears in the formula for the sum of an arithmetic progression that appears in the process of scribbling the formula.

On average, ideally, the mathematical expectation of various options should be considered. It can be shown that if the pivot divides the array in a ratio of 1: 9, then the resulting asymptotics will still be O (n * log (n)).

Sorting is called fast, because the constant that is hidden under the O sign turns out to be quite small in practice, which led to widespread use of the algorithm in practice.