How does this implementation of the quicksort algorithm work

Sorting by splitting / quicksort

A sorting game

Anton, Britta, Carlo, ... want to line up according to size. First of all, they are all measured precisely.

The game now plays like this:

One person (e.g. the first in line) is selected as the comparison person. In this example it is Anton.

All others place themselves to the left or right of the comparison person, depending on whether they are smaller or greater than the comparison person.

Anton remains in his position now. He no longer takes part in further game rounds. The same game is now carried out in the left and right areas: One person (e.g. the first in line) is again selected as a comparison person.

And so on ...

Task 1

Play through the sorting game yourself. When does the game end? What extreme cases can occur during the game? Does the sorting game still work?

The basic idea

A list of comparable elements is given. An element of the list (e.g. the first element) is selected. The remaining list is then divided into two sub-lists according to this element: the list of the elements of the remaining list that are smaller than the selected element and the list of the elements of the remaining list that are not smaller (i.e. greater than or equal to) the selected element. This process is continued completely analogously with the partial lists.

25 17 32 56 25 19 8 66 29 6 20 29 ^ 17 19 8 6 20 | 25 | 32 56 25 66 29 29 ^ | | ^ | | 8 6 | 17 | 19 20 | | 25 29 29 | 32 | 56 66 ^ | | ^ | | ^ | | ^ | | | | | | 6 | 8|| ||19 | 20 | ||25 | 29 29 | ||56 | 66 | || | | | || | ^ | || | | || | | | || ||29 | 29 | || |

The following figure should clarify the basic idea of ​​the sorting process once again:

exercise 2

Carry out the sorting procedure on the following example. Record the individual steps as shown above.

35 28 41 7 14 50 33 21 21 60 18 12 ^

Sequence modeling with several lists

The sorting method explained above will now be described with an algorithm.

This sorting process can be described informally as follows:

Task 3

Implement the algorithm.

Process modeling with a list

Quicksort can also be implemented by swapping elements in the outgoing list:

The implementation is a little more difficult here:

Task 4

Test this implementation. Also test them with the output statements that are commented out in the function definition above. Explain the values ​​given.