15.1. Quicksort

So, we are now ready to look at another algorithm called Quick sort. So, quick sort was invented by a computer scientist called Tony Hoare in the early 1960’s; that is about 50 years ago. And Tony Hoare is a very well-known computer scientist and he has impact one Turing about which is one of the highest achievements awarded for academic computer scientist.

Quicksort is a sorting algorithm developed by Tony Hoare in the 1960s. It's recognized for its efficiency in sorting, especially in scenarios where space is limited. Unlike some other algorithms, it does not require additional storage which can save resources during computation.

Think of Quicksort like organizing a messy bookshelf. Instead of moving all the books at once, you pick one book (the pivot) and arrange the others based on their size relative to that book.

So, what is the purpose of quick sort? Well, the purpose of quick sort is to overcome some of the shortcomings that we saw in the merge sort. So, one of the things that we saw in the merge sort is that because of the merge operation, we need extra storage and so, this makes merge sort a little expensive.

The main goal of Quicksort is to address the issues found in merge sort, specifically the need for extra storage during the merging process which can be costly in terms of memory. Quicksort operates by sorting in place, using only a small, constant amount of additional storage space.

Imagine a classroom where students are arranged by height. Merge sort would require additional space to create a new line of students while they are being sorted, whereas Quicksort will have the students sort themselves in their original line.

So, of course, there must be a catch and the catch is how do we find the median? Right at the beginning of our discussion, we said that one of the reasons that we want to sort is to do statistical things like find the median. So, if we have sorted the array, then the median value is the middle value, but of course, our goal now is to sort the array. So, we cannot assume that we have the median, because we have already seen that sorting is an easy way to find the median. So, it is a kind of the chicken and egg problem, we cannot use the median to sort.

Finding a true median from an unsorted list can be problematic since sorting is often required to locate the median value. In Quicksort, instead of searching for the actual median, we can select any value from the array as a 'pivot' to segment the array into two parts: values less than the pivot and values greater than the pivot.

Considering a company potluck where the goal is to group dishes into healthy and unhealthy options, instead of needing to know the healthiest option (the median), you can simply choose any dish as a reference and start separating.

So, this is quick sort, choose a pivot element. So, for example, you may just pick up the very first value in the array as implemented. Partition this array into the lower and upper part. So, the lower part is those which are less than the pivot, the upper part is that which is greater than the pivot.

In Quicksort, the initial step is to select a pivot element. The algorithm then partitions the array into two segments: one segment contains elements smaller than the pivot (lower part), and another contains elements larger than the pivot (upper part). This helps in organizing the unsorted values effectively without needing additional storage.

Think of organizing a stack of envelopes by size. You might pick the smallest envelope as a reference and then sort all larger envelopes to one side and leave the smaller ones on the other side.

So, now I do this recursive thing, I sort this and I sort this and now remember this no need to merge, because everything on the left is already smaller than everything on the right. So, I can just go ahead and assume the array is sorted.

After partitioning the array around the pivot, the next step is to apply recursive sorting to both partitions. Because the elements are already organized relative to the pivot, there's no need for a merging process like in merge sort.

It's akin to sorting books into two separate sections based on whether they are fiction or non-fiction—once separated, each section can be sorted independently without needing to merge them back together.

There are two ways to partition. So, we will look at one in detail and show some code for it and then we will look at another through an example and you will have to write the code by yourself, if you are interested.

There are different strategies for partitioning the array within the Quicksort algorithm. One common strategy involves using two pointers that help in identifying the smaller and greater elements relative to the pivot. By swapping elements as necessary, the array can be efficiently partitioned.

Imagine you are at a party and you want to separate guests who prefer different styles of music. You could have two friends (pointers) check each guest's preference and manage the arrangement accordingly, ensuring everyone enjoys their evening.

--