Understanding Quick-Sort.

So, let’s begin the story of QUICK-SORT, if you are new to programming, then this is a good article for you. But we are not jumping to QUICK-SORT right away, first, we will solve few simple problems and then keep updating these problems and end up creating a solution for QUICK-SORT.

Problem 1) Write a program Segregate 0s and 1s in an Array.

It’s like segregating dividing Apple(🍎) and Oranges(🍊) from a basket, right. So what we do is take another basket and for every fruit (i.e. 🍎 and 🍊) if we encounter a 🍊 , we put that into the second basket.
Problem solved, right?
This is a very common problem and can be solved in many ways. Like what if can’t use another Array (🧺).

So we can align them in a line ( 🍎,🍊,🍎,🍎,🍎,🍊,🍊,🍊,🍊,🍎) and for every fruit, if we find an 🍊 we replace it with first 🍎 we find next.
Now let’s see the code for this algorithm.

Here, 🍎=0 and 🍊=1, and i and j are two pointers traversing the the array.
for each item in array
   swap(item at i, item at j) 
   if (item is 0){
      j++;
   }
   i++;

What just happened?

In the pseudo-code“if (item is 0)" is what we call a segregation condition. This condition is really important as let’s just say if we have both 🍏 and 🍎 in a set of fruits(🍏 ,🍎 ,🍊). So now we have run the same algorithm for the apples (by color) after first segregation (which was the type of fruits) so that we can have all 3 types of fruits divided in their baskets.

Now, what if, this is a big if, you have a bucket which has vegetables and fruits all mixed up. And someone asks you to divide them. How do you approach this problem? What you can do is take one fruit at a time, like an apple 🍎, and move it into its own basket, doing that just time-consuming, searching through the lot and finding all apples, then oranges, and then carrots. That's just Selection Sort.

Want to read this story later? Save it in Journal.

We do something else, we divide the lot first into vegetables and fruits(segregation condition#1). Then divide fruits into Apple Family Fruits and Tangerine family fruits(segregation condition#2). After that, we can divide apple family fruits by color (segregation condition#3). And Tangerine family fruits by size(segregation condition#4). You will end up sorting your lot way faster than usual. Moving on to our second problem…

Problem 2) Write a program Segregate numbers smaller and larger than a value k.

This problem is pretty straightforward, we just have to change our segregation condition which we defined above. Now it is intArray[i] > k

Here, and i and j are two pointers traversing the number array and k is the pivot element.
for each item in the array
   i++;
   swap(item at i, item at j) 
   if item is less than pivot, j++

“item is less than pivot” this condition puts smaller element first.

What just happened?

Let’s understand this by example. Suppose if we have an input array

[2, 3, 7, 8, 1, 5, 6, 9, 0,10,4]. 

By looking at this array we know the mid element is 5 ( = pivot). So we divide this array into 2 parts using ‘5’ as a pivot element. One will have numbers smaller than 5 and the other will have numbers larger than 5. So after putting this in our above function we will get

[[2, 3, 1, 5, 0,4], [6, 9, 7, 10, 8]].

But what if we want the first array to divide even more. Again by just looking at the first array, that mid element is ‘2’ (or 3). So we put [2, 3, 1, 5, 0,4] in our segregation method and get [[2, 1, 0], [5, 3, 4]] as output. Now you can see where am I am going with this. Again putting [2, 1, 0] in our segregation method with mid element 1 we get [[0,1],[2]]. So what we got is a sorted array of three elements. Keep doing this for every set we get at every iteration and we will end up sorting the array.

Still, we got one problem, we always chose mid element as our pivot element to divide the array. But our quick sort method, which we are about to write, doesn’t have this information. So for simplicity, we choose the first element of every partition as our pivot element and “HOPE for the BEST 🤞”.

We will use this segregation method, which we defined in the above code block, Quick Sort which is why it is important to learn first. As we know Quick Sort is a divide and conquer algorithm. And we have just discussed the dividing part. Now let’s conquer it, updating our problem to

Problem 3) Write a sorting algorithm that keeps on dividing an array till it gets sorted.

What just happened?

So we chose the first element as our pivot element. (i.e. line number 9). Then we divided the array into elements that are smaller than our pivot element and larger than the pivot. After that put the pivot at the position where all the elements on the left side are smaller than and all the elements greater than the pivot that is on the right side. Why we did it? Well, the answer is the pivot is now in its correct position if the array was already sorted. All elements smaller than the pivot are on its left, and larger on its right. In a sorted array, it is true for every element. Now, what we do is the same process for the left half and the right half so we called the same function again with the new input parameter.

This choosing and moving the pivot element to its correct position is called QUICK-SELECT.

Time Complexity:

So in the best-case scenario i.e., we encounter a pre-order traversal of a binary search tree and this algorithm will work in (n log n).
That is for every element in an array of n elements, we have to do only N(1+1/2+1/4+1/8+…) operations, where i is in 1 to n inclusive, to sort the i-th element when traversing the array.
In an average case scenario, we can get somewhat O(n log n) complexity same as the best-case.
Worst case it can go up to O(n²) that is when the array is already sorted; sorted in reverse; nearly sorted, one out of order element; all values the same; all the same except first (or last) is higher (or lower).

Problem 4) Problem of the pivot element.

Choosing the pivot element is really important as it decides your running complexity of this algorithm.
We can choose the first, last, or middle element.
We can also choose the mean of the array.
We can also choose the average of min and max items.

These are all as per our choice if you have some prior information about the array you are about to receive. You can suggest more ways in the comment.

Some programming problems to solve after reading this.

1. Nth max element in an array. Use the Quick-Select method.
2. Implement Quick Sort, without Recursion.
3. Instead of partitioning the array into two parts what if we divide the array into three parts. Which is a more effective solution, first or second.
4. Who are Hoare and Lomuto?
5. Implement a Binary Search Tree using Quick Sort Algorithm.

Why so much repetition though? Well, repetition is one of the great method to store any information in our minds for a longer period of time.

📝 Save this story in Journal.