Quick sort is a big improvement over bubble sort. This sorting technique was developed by British computer scientist Tony Hoare. The algorithm works in three main steps:
- Select a pivot
- Partition the list so that elements on the left of the pivot are less than the value of the pivot and the ones on the right are greater
- Repeat steps 1 and 2 on the left and right parts separately
Since recursion is required for quick sort, we will begin this section by giving an example of recursion. Later, we will see how the partitioning in the quick sort algorithm works, and in the end, we will put the recursion techniques to use in the final part.
Recursion is a really useful tool for algorithm designers. It allows you to solve large problems by solving a smaller occurrence of the same problem. Recursive functions usually have a common structure with the following components:
- One or more stopping conditions: Under certain conditions, it would stop the function...