Example 61: Quicksort
Learn how to implement quicksort.
We'll cover the following...
Problem
Quicksort is a popular sorting method. The name comes from the fact that, in general, Quicksort can sort a list of data elements significantly faster than any other common sorting algorithms. This algorithm is based on the fact that it is faster and easier to sort two small arrays than one larger array. Thus, the basic strategy of Quicksort is to divide and conquer.
Write a program to sort an array in ascending order using the Quicksort algorithm.
Example
If you were given a large stack of papers bearing the students’ names to sort them by name, you might use the following approach:
- Pick a splitting value, say L, which is known as a pivot element.
- Divide the stack of papers into two piles such that names starting from the alphabet A upto L lie in one place and those from M upto Z in another.
❗Note: It is not mandatory that the two piles contain the same number of papers. ...
- Then, take the first pile and sub-divide it into two piles such that the names starting from the alphabet A–F lie in one place and G–L in another. The