Sorting algorithms¶

In programming, there is often a need to sort data - if only to be able to search for the object of interest using binary search algorithm. How much more difficult it would be if the encyclopedic entries were not sorted alphabetically?

In this section, we will look at some of the most popular sorting algorithms: bubble sort, insertion sort, merge sort, and quick sort.

Bubble sort¶

The bubble sorting algorithm is considered to be the easiest sorting algorithm to understand. Due to the necessity to use two loops (one of which are nested) in the implementation code, the complexity of the algorithm is O(n^2). It is not the fastest algorithm. The advantage is the constant memory complexity - while running, all operations are performed in place, there is no need to create temporary lists, so memory complexity is not a problem here.

Here's what bubble sort is all about.

We start with a list of random numbers of natural numbers. After executing the algorithm, we would like to get the elements sorted in ascending order: 6-10-23-29-31.

The first two numbers are placed under the magnifying glass and compared with each other. If the one on the left is smaller than the one on the right - it stays in its place (after all, we want the smallest number to be the leftmost, and the largest to the right). In the opposite case, it would be necessary to change places of the numbers considered.

Since the number 10 is less than 29, no swapping in the previous step took place. The algorithm now assumes another comparison: the second and the third element in the order.

This time the series is violated because the greater number is on the left. The algorithm recognizes this and correct it.

The numbers 29 and 23 are swapped.

The bubble algorithm goes on and selects the next two numbers to compare. In this case, everything is in the right place, so nothing changes.

Last look at this iteration: numbers 31 and 6.

The order is not correct so the numbers hit the crosshairs.

The algorithm assumes placing the number 31 as the last one, and the number 6 next to the left.

After going from start to finish, the list is still not completely sorted. The only thing you can be sure is that the largest number in the set will end up in the rightmost position and will not need to be considered anymore (it has already reached where it should be after the final sort).

Comparisons and substitutions start over from the top of the list. With each successive iteration, the next largest numbers are found, and sorting continues until no element replacement occurs for the first time in the iteration.

Insertion sort¶

Insertion sort is like the way you put cards in your hand. The computational complexity of this algorithm, as in the case of the bubble algorithm, is O(n^2), and the memory complexity is O(1).

The operation of the algorithm is presented in the pictures below.

The algorithm begins with accepting a list of unsorted elements as an input. Time to put them in the right order.

At the start, the first two numbers in the list are considered.

The smaller one lands in first position. In the example below, it is ten that was already under the appropriate index.

The algorithm continues its work, starting to compare the next elements.

29 is greater than 23 - so there should be a substitution.

The number 23 lands to the left of the number 29. Meanwhile, the numbers 10 and 23 were compared, but this time no swap was necessary. We do exactly the same with the newly drawn card: we browse from right to left for the first card that is weaker (smaller) and place the new one on its right side.

Successive numbers are analyzed. According to the algorithm, the number 6 should now be compared with every number in the previous positions, and the number six should land at the top of the list.

Insertion sort continues to the end of the array, placing the appropriate number between the smaller and larger each time.

Merge sort¶

Merge sort is a fairly fast, but quite unusual algorithm that involves splitting an array until you get a sublist with one item. The principle of divide and conquer emerges here - sometimes more advanced tasks become easier when properly divided into smaller ones. (Clean the room. Too tough task? OK, then clean the desk first. Then the shelf. Make the bed. Then put things on the cupboard. Sounds simpler?)

The computational complexity of this algorithm is O(n*log n). Unfortunately, the memory pays for speed, because the algorithm creates a temporary list.

Imagine creating one sorted list of numbers from two smaller, also sorted lists. The simplest solution would be to create a new list with a length that is the sum of the remaining lengths. Then you only need to look at the first elements of the tables, select the smallest one, remove it from the list, which it was included in so far and put it in the newly created one. Subsequent comparison will fill a new list - and it will be sorted.

How do I sort a list of unordered numbers in a similar way? If the table is one - it should be divided into two. The first condition is met - we have two sublists. The second condition (ranks should be sorted) most likely will not be met. According to the principle of dividing the problem into its smallest parts, you should divide these two lists until you get a total of several (or more) single-element lists. Since they have one item, they are sorted! Then we pair the lists and compare the first elements (the first and the last ones - they are one-element). And so on until all sublists are combined into one output.

The above algorithm is shown in the pictures below.

The input list is split into two.

The received lists are divided into successive, smaller ones.

Final splitting leads to 8 single-item lists.

Now the first list items are compared.

The smaller number lands on the left and the numbers merge into a two-item (further sorted) list.

Two four-element lists are created from two-element lists (the first elements are selected, the smaller one lands on the first position of the list intended for storing four elements, then the current first elements are compared, etc.).

Finally, the two lists combine into a complete output fully sorted array.

Quick sort¶

The quick sort algorithm divides the unsorted list into two - one contains smaller elements, the other larger than the element that was previously selected as a determinant (so-called pivot). Here, recursion turns out to be reliable. Sorting works by separating the lists against pivot and finally concatenating them into one. The computational complexity is O(n*log n).

Selecting pivot - This is usually the middle item, but it can be a random number from the list.

The indexes are low (rightmost) and high (leftmost). The index low is traversed the list from left to right looking for an element larger than that indicated by pivot.

The number 29 is greater than 27 indicated by pivot. Since there should only be smaller numbers to the left of it, there must be a substitution. The algorithm remembers the low position and now looks for a number less than 27 with the high pointer.

When a number is found that is smaller than the one indicated by pivot (here: 15), the places of numbers under the indices low and high are swapped.

The low index starts walking further to the right edge of the list looking for a number greater than that of pivot.

When the indices meet, the only item that can be swapped with the one the indices show here is the one in the pivot.

After conversion, on the left side of pivot there are numbers smaller than it, and on the right - bigger.

Recursively, the same actions should be performed for the created sublists (indicated by braces in the picture).