Quick Sort

We have already discussed the Bubble Sort Algorithm and Merge Sort Algorithm, and in this post, we are going to discuss ALGORITHM OF QUICK SORT.

Quick Sort Algorithm is also a divide and conquer Algorithm, but it is considered to be better than Merge Sort Algorithm in practical cases. 

Why Quick Sort is better than Merge Sort Algorithm..??

The reason behind it is that there is always a scope of improvement in quick Sort.

Quick Sort works by selecting a ‘pivot’ element from the dataset and partitioning the other elements into two sub-dataset, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively. 

In Quick Sort, you always have the freedom to choose pivot element and you can always choose it according to the datasets.

We have already discussed the Divide and Conquer approach in Merge Sort Algorithm. Please go through it.

What is a pivot element?

The pivot element is the boss of all the elements. All other elements are arranged according to the pivot element.

Let’s take an example,

algorithm of quick sort

Let’s consider the first element as a pivot element and we want to arrange the other elements accordingly.

We will arrange other elements such that all elements smaller than pivot will come to the left side of the pivot and all elements greater than pivot will come to the right side of the pivot.

algorithm of quick sort

Now as you can see we have arranged the elements according to our pivot element.

NOTE that the above array is not a sorted array, the elements on the left side of the pivot element are smaller than it, and elements on the right side are greater. That’s it.

This is the use of the pivot element in the Quicksort Algorithm. You always have the right to choose a pivot element. Some other ways of selecting pivot element are – 

(i) It can be the first element of the array. (As discussed above)
(ii) It can be the last element of the array.
(iii) It can be the middle element of the array.
(iv) It can be chosen randomly. (Randomised Quick Sort)

Now the question arises, How to arrange elements according to pivot elements?

The implementation is very much simple, let us consider that we choose the first element as the pivot element.

Let’s see the code first,

int find_pivot(int arr[], int low, int high)
{
    int pivot = arr[low];
    
    int p_index = low+1;
    for(int i = low+1; i <= high; i++)
    {
        if(arr[i] <= pivot) 
        {
            swap(arr[i], arr[p_index]);
            p_index++;
        }
    }
    swap(arr[p_index-1], arr[low]);
    return p_index-1;
}

Let us consider the same example to understand the code,

algorithm of quick sort

(i) For this example, low = 0 & high = 6. Also pivot element is the first element of the array.

Now we use a pointer variable to keep track (p_index). Initially p_index = 1.

(ii) Now we will run a loop and we will check whether any element in the array is smaller than it, if we find such an element we will swap it with the element present at p_index and then we increment the p_index.

(iii) We will follow these steps until we iterate through the array. Lastly, we will swap the elements of (p_index – 1) and the pivot element.

Let us visualize it what we have discussed above,

algorithm of quick sort
algorithm of quick sort

The arrow indicates the p_index. Initially p_index = low + 1.

Since 1 < 4, we swap arr[i] and arr[p_index], in this case, both are same so no swapping takes place, and then we increment p_index.

Again in 4th step, since 3 < 4, we swap arr[i] (3) and arr[p_index] (7) and then again we increment the p_index.

We follow these steps till we iterate all the elements of the array, at last, we swap arr[p_index-1] and pivot element so that element lesser than pivot element comes to its left side and element greater than it comes to the right side.

I hope this explanation and pictorial diagram make your concept clear.

Partition Algorithm


As we know Quick Sort is a divide and conquer algorithm, here also we have to divide the datasets into individual datasets as we did in Merge Sort Algorithm.

But here we will not divide the datasets into two equal halves instead we will divide it according to pivot element.

The approach is very simple, we will find p_index from the above algorithm and then we will divide the datasets into two halves accordingly.

Let’s see the code for clarification,

void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        int p_index = find_pivot(arr, low, high);

        quickSort(arr, low, p_index - 1);
        quickSort(arr, p_index + 1, high);
    }
}

This algorithm looks similar to the merge Sort first_step algorithm. Yes, both algorithms are similar because both algorithms divide the dataset into two halves.

But there is a difference, in merge sort we were dividing the array into two equal halves but here we are dividing it w.r.t pivot element.

Another difference is that here we are not merging datasets as we are doing in the case of merge sort.

Quick sort is an in-place Algorithm which means this Algorithm doesn’t require any extra space.

Let us understand this Algorithm by taking an example,

algorithm of quick sort

Now we will update this array according to pivot element, here pivot element is 6.

algorithm of quick sort

This is how recursion takes place, initially we find the pivot element of the original array and update the array accordingly.

Then we call recursion to the left part as well as the right part of the pivot index, we again find the pivot element for that sub-array and accordingly we move on.

At last, we finally get a sorted array. I hope Quick Sort is clear to you.

Analysis of Quick Sort Algorithm


Quick Sort Algorithm depends on the pivot element and it also involves the process of partitioning, so for an unsorted array, the average time complexity is O(n log(n)).

Best Case Time Complexity: O(n*log n)
Average Case Time Complexity: O(n*log n)
Worst Case Time Complexity: O(n^2)


Worst case of Quick Sort is O(n^2)

Let us consider this above array,

The given array is already sorted in ascending order and we want to apply quick Sort in this above array.

I know you might be thinking that why we are sorting this array since it is already sorted?

Sometimes, in real-world problem datasets are not in your control. So there is a chance you can get a sorted array.

So it’s better we should design Algorithms considering worst cases.

Now for the above array, pivot will be 1. But after partitioning, left subarray will be empty and right subarray will have remaining (n-1) elements.

Again for the right subarray, pivot will be its leftmost element, and again its left subarray will be empty and right subarray will have (n-2) elements.

This process will go on and thus time complexity would be –

T(n) = n + (n-1) + (n-2) + … + 3 + 2 + 1
= ((n) * (n+1) / 2)
= O(n^2)

Hence worst case has O(n^2) time complexity.

However worst case Complexity can be solved by selecting a suitable pivot element. This is the advantage that Quick Sort gives us, we can always avoid worst-case time complexity by picking up the appropriate pivot element.

Complete Quick Sort in C/C++

#include<bits/stdc++.h>
using namespace std;

int find_pivot(int arr[], int low, int high)
{
    int pivot = arr[low];
    
    int p_index = low+1;
    for(int i = low+1; i <= high; i++)
    {
        if(arr[i] <= pivot) 
        {
            swap(arr[i], arr[p_index]);
            p_index++;
        }
    }
    swap(arr[p_index-1], arr[low]);
    return p_index-1;
}

void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        int p_index = find_pivot(arr, low, high);

        quickSort(arr, low, p_index - 1);
        quickSort(arr, p_index + 1, high);
    }
}

int main()
{
	int n;
	scanf("%d",&n);

	int arr[n];
	
	for(int i=0;i<n;i++) {
		scanf("%d",&arr[i]);
	}
	
        quickSort(arr,0,n-1);
	
        for(int i=0;i<n;i++){
		printf("%d ",arr[i]);
	}
	printf("\n");
	return 0;
}

Randomized Quick Sort Algorithm

As we have observed that choosing a specific pivot element may take O(n^2) time complexity for some cases.

Randomized Quick Sort is the best solution for avoiding such cases.

Randomized Quick Sort generates a random pivot element which reduces the possibility of O(n^2) time complexity to almost 0%.

How to generate random numbers ..?

For this we will use random generator function, Let’s see its code.

int main()
{
	srand(time(NULL));
	printf("%d\n", rand()%100);

	return 0;
}

Here, the rand() function is used to generate random numbers and srand() function sets the starting point for producing a series of pseudo-random integers.

We use time(NULL) as seed value because time varies every millisecond which increases our probability of generating different random numbers.

The above code will generate random numbers in the range [0, 99].

Now we will use this random generator to generate random pivot indexes.

Let’s see the code of randomized Quicksort in C/C++,

#include<bits/stdc++.h>
using namespace std;

int random_index(int low, int high)
{
    srand(time(NULL));
    int index = low + (rand() % (high - low + 1));
    
    return index;
}

int find_pivot(int arr[], int low, int high)
{
    int index = random_index(low, high);
    
    swap(arr[index], arr[low]);
    
    int pivot = arr[low];
    
    int p_index = low+1;
    for(int i = low+1; i <= high; i++)
    {
        if(arr[i] <= pivot) 
        {
            swap(arr[i], arr[p_index]);
            p_index++;
        }
    }
    swap(arr[p_index-1], arr[low]);
    return p_index-1;
}

void quickSort(int arr[], int low, int high)
{
    if (low < high)
    {
        int p_index = find_pivot(arr, low, high);

        quickSort(arr, low, p_index - 1);
        quickSort(arr, p_index + 1, high);
    }
}

int main()
{
    int n;
    scanf("%d",&n);

    int arr[n];
    
    for(int i=0;i<n;i++) {
        scanf("%d",&arr[i]);
    }
    
        quickSort(arr,0,n-1);
    
        for(int i=0;i<n;i++){
        printf("%d ",arr[i]);
    }
    printf("\n");
    return 0;
}

Here we are generating random index in the range (low, high) and we are swapping that index with arr[low], so in general, we are always generating random arr[low].

In this way, we can get rid of quadratic worst-case time complexity. For randomized Quick Sort worst-case complexity changes to O(n*log n).

I hope both Quick Sort and Randomised Quick Sort is clear to you all.

That’s all folks…!!!

Tagged :

Merge Sort Algorithm

We have already discussed the Bubble Sort Algorithm, and in this post, we are going to discuss another sorting algorithm MERGE SORT ALGORITHM.

As the name says this sorting algorithm might be related to merging some datasets.

And yes you guessed it right, Merge Sort Algorithm is a divide and conquer Algorithm, where we first break the datasets into some sub-datasets and then do some stuff on it and lastly we merge the sub-datasets.

Since this process involves merging the datasets, this Algorithm is called the Merge Sort Algorithm.

Divide and Conquer

In computer Science, Divide and Conquer is a very powerful technique to solve real-life problems.

Divide and Conquer include three steps :

(i) Dividing the problem into subproblems.
(ii) Solving the subproblems.
(iii) Merging the solution of the subproblems to solve the actual problem.

Let us consider a real-life example, suppose you are only a warrior left in the battleground, and on another side, there are five other warriors who are your enemies.

Now how will you defeat them ??

It is impossible for you to defeat all five warriors in one go, instead, you can plan to beat them individually, so you decided to tackle one enemy at a time, and this way you defeat all the five enemies. This is the concept of divide and conquer.

Divide the problem into subproblems so that instead of tackling the whole problem in one go, tackle the subproblems.

Applications of Divide and Conquer are Binary Search, Merge Sort, Problems of Tree Data Structures, etc.

Divide and conquer Algorithm uses recursion to conquer a problem, click here to know more about recursion.

Merge Sort

Hope Divide and Conquer Algorithm is clear to you.

Let us understand it more clearly by using an example,

We will discuss the Merge Sort Algorithm to understand Divide and Conquer Algo.

We already know what sorting is. So now let us consider an array to understand merge sort.


1st Step of the Algorithm

Divide the array into two halves.

merge sort algorithm

We will keep it dividing until we get datasets of single element.

merge sort algorithm

This is the first step of Merge Sort, dividing the array dataset individually.

Now let us discuss the code for implementing the first step of Merge Sort.

void merge_sort_First_step(int arr[], int l, int r) 
{ 
    if (l < r) 
    { 
         int m = l + (r-l)/2; 
        
         merge_sort_First_step(arr, l, m); 
         merge_sort_First_step(arr, m+1, r); 
    } 
}

In the above code, we first find the middle element of the array, initially l=0 and r = n-1, and after that, we recursively divide the left subarray and then the right subarray with the same process until (l<r).

This recursion will divide the array into individual subarrays.


2nd Step of The Algorithm

Now let us move to our next step, currently, we have just individual elements of the array.

We will merge the individual datasets but instead of merging directly, we will merge it such that the elements of the merged dataset are sorted.

Let us understand it by the same example,

merge sort algorithm
merge sort algorithm

In this step we are actually conquering the datasets, at the same time we are merging the datasets as well.

This is the main logic of 2nd step of Merge Sort, as you can see after merging 4 and 1 we are getting a merged dataset with (1,4) as an element.

But the Question arises, how to merge two datasets to form a sorted dataset?

If you observe carefully, we are actually merging two sorted sub-datasets to form a sorted dataset.

Yes, you heard it right, we are actually merging two sorted sub-datasets to form a sorted dataset.

All unsorted dataset containing only a single element is also a sorted dataset.

In fact, this is a very famous interview Question, how to merge two sorted datasets into a sorted dataset.
Let us discuss this first.

Merging two sorted arrays into a sorted array

merge sort algorithm

Given two sorted arrays of size m and n respectively, we have to merge it to form a new sorted array of size (m+n).

Please try this problem by yourself, it is highly recommended to try it once.


Now let us discussed the solution of the above problem, the logic is very simple, we will run a while loop maintaining three variables (i, j, k) simultaneously.

Let’s see the code first,

void mergeSortedArrays(int x[], int y[], int n, int m, int z[]) 
{ 
       int i = 0, j = 0, k = 0; 
  
       while(i < n && j < m) 
       {  
             if (x[i] < y[j]) { 
                    z[k] = x[i];
                    i++;
             } 
             else {
                  z[k] = y[j];
                  j++;
             }
             k++; 
       } 
  
       while(i < n) {
              z[k] = x[i];
              k++; i++;
        } 
        while(j < m) {
              z[k] = y[j];
              k++; i++;
        } 
} 

Here we are maintaining three variables i, j, k simultaneously.

The idea is that since both arrays are sorted, we will compare the first element of the first array with the first element of the second array and we will accordingly fill the smaller element to the z[] array.

We will continue his process until we traverse either of the two arrays completely.

Let us understand it more clearly with an example,

merge sort algorithm

This is how we will fill the z[ ] array . Hope this diagram makes your concept clear.

Merging Step in Merge sort Algorithm

Now again come back to our main topic, we will merge the sub-arrays in the same fashion that we discussed.

Let us discuss the code of the 2nd step of the Merge Sort Algorithm.

void merge(int arr[], int l, int m, int r)
{
    int left_size = m-l+1;
    int right_size = r-m;
     
    int *left = new int[left_size];
    int *right = new int[right_size];
     
     for(int i = l; i <= m; i++) {
         left[i-l] = arr[i];
     }
     
     for(int i = m+1; i <= r; i++) {
         right[i-m-1] = arr[i];
     }
     
     int i = 0;
     int j = 0;
     int k = l;
     
     while(i < left_size && j < right_size)
     {
         if(left[i] < right[j]) {
             arr[k] = left[i];
             i++;
         }
         else {
             arr[k] = right[j];
             j++;
         }
         k++;
     }
     
     while(i < left_size)
     {
         arr[k] = left[i];
         i++; k++;
     }
}

I know code is a bit lengthy but don’t worry we will discuss each and every step very clearly.

Now take an example of merging two subarrays from the same example which we discussed earlier.

merge sort algorithm
merging array

We will discuss the dash – marked dataset, we will discuss how we will merge it in this algorithm.

Step 1: For the dash marked area l = 4 , m = 5 and r = 6.
Step 2: Create two temporary arrays of size (m-l+1) and (r-m) respectively.


We created these two arrays for the reference so that with the help of it we can update our original array.

Step 3: Fill the temporary arrays with the value accordingly.
Step 4: Merge the two arrays and update the original array in the same manner that we discussed earlier.

That’s it. Hope I can able you to understand the 2nd step of the Merge Sort.

NOTE that here we have the original array with us initially and we also have a range of index within which we have to convert the dataset to sorted dataset.

So we will first create two sub-dataset and fill it data accordingly and then merge both of them to update the original array.


We follow the same way for all the sub-dataset and at last, we get our sorted array. This is the Masterstroke Logic of Merge Sort Algorithm.

Analysis of Merge Sort Algorithm

Dividing the dataset to sub-datasets of two and then merging it again takes O(n*log(n)) complexity.

Best Case Time Complexity: O(n*log n)
Average Case Time Complexity: O(n*log n)
Worst Case Time Complexity: O(n*log n)

Even if it a sorted array, merge sort will follow these steps to find whether the array is sorted or not, so Best, Average, and Worst case complexities are the same.

Complete Merge – Sort code in C/C++

#include<bits/stdc++.h>
using namespace std;

void merge(int arr[], int l, int m, int r)
{
    int left_size = m-l+1;
    int right_size = r-m;
     
    int *left = new int[left_size];
    int *right = new int[right_size];
     
     for(int i = l; i <= m; i++) {
         left[i-l] = arr[i];
     }
     
     for(int i = m+1; i <= r; i++) {
         right[i-m-1] = arr[i];
     }
     
     int i = 0;
     int j = 0;
     int k = l;
     
     while(i < left_size && j < right_size)
     {
         if(left[i] < right[j]) {
             arr[k] = left[i];
             i++;
         }
         else {
             arr[k] = right[j];
             j++;
         }
         k++;
     }
     
     while(i < left_size)
     {
         arr[k] = left[i];
         i++; k++;
     }
}
void merge_sort_First_step(int arr[], int l, int r) 
{ 
    if (l < r) 
    { 
         int m = l + (r-l)/2; 
        
         merge_sort_First_step(arr, l, m); 
         merge_sort_First_step(arr, m+1, r); 
         merge(arr,l,m,r);
    } 
}

int main()
{
	int n;
	scanf("%d",&n);

	int arr[n];
	
	for(int i=0;i<n;i++) {
		scanf("%d",&arr[i]);
	}
	
        merge_sort_First_step(arr,0,n-1);
	
        for(int i=0;i<n;i++){
		printf("%d ",arr[i]);
	}
	printf("\n");
	return 0;
}

Hope Merge Sort is clear to you. Merge Sort is one of the best Sorting Algorithm along with Quick Sort. Merge Sort is used widely.

That’s all folks..!!![Wikipedia Reference]

Tagged :

Bubble Sorting

In this post, we are going to discuss an important Sorting Algorithm, Bubble Sorting, and program of bubble sort in c/c++.

What is sorting?
Sorting in a way of representing a data set in either ascending or descending order.

Data sets can be an array, linked-list, tree, etc.

Why is sorting required?
In our real life, a sorted dataset makes our life easier. It makes the dataset a lot easier to read.[Learh 0-1 Knapsack problem]

It makes it easier to implement in search algorithms in order to find or retrieve an item from the entire dataset.

Applications of Sorting are Binary Search, Binary Search Tree, Priority Queues, etc.

Technical Definition

Bubble Sort is a technique to sort a data-set. Bubble Sort is also called a Sinking sort.

Why is it called “Bubble Sort” ?

The concept of Bubble Sort or Sinking Sort is something like after each step the heavier or lighter object bubbles on the top of the data-set.

Practically, this Algorithm compares every element with its adjacent elements and swaps it accordingly.

Now let us discuss what actually the Algorithm is and then after we discuss the program of bubble sort in c/c++.

Example

Let us consider an example of an array,

bubble sort algorithm

Let us first observe something,

bubble sort algorithm

If we observe carefully, we are following a pattern in the above representation.

Observing pattern of Bubble sort

Yes you guessed it right, we are comparing two adjacent array elements at a time, and if the first element is greater than the second element, we are simply swapping it.

We are following this pattern until we reach the last index.[Read Greedy algorithms]

Now I want you guys to observe one thing in the above pictorial representation.

What output did we get after following the pattern ?

If we observe carefully, we got the largest element of the array at the last position and it is obvious because we are comparing two adjacent elements at a time from starting index to the last index and at every step, we are pushing the greater element to the right side.

So ultimately after all the iteration, we will obviously get the greatest element of the array on the rightmost index.

Yes, this is the main logic of Bubble Sorting.

We compare two adjacent elements at one go and push the greater element on the right side and ultimately we get the greatest element of the array.

Let us write some code to implement the above Logic.

Raw Code:

void Bubble_Sort(int *arr, int n) {
      for(int i = 0; i < n-1; i++)
      {
            if(arr[i] > arr[i+1]) {
                   swap(arr[i], arr[i+1]);
            }
      }
}

I hope the code is very clear to you all. I represented the same logic which we discussed earlier.

Now tell me one thing, did we get a sorted array after performing the above algorithm?

No, our array is still unsorted but this algorithm guarantees that after performing it, we will always get the greatest element at the end.

bubble sort algorithm

There are 7 elements in the array initially, of which we get the greatest element in one overall iteration from the beginning index to the end index.

Now let us consider, we will again perform the same algorithm on the remaining 6 elements excluding the last element.

What do we expect?


Yes, you guessed it right, at last, we will get our 2nd last element of the array.

Now let me ask you a Question,

Can we get a sorted array, if we perform the same algorithm repeatedly for the rest of the elements?

Yes we will get a sorted array at the end and this is obvious because for each iteration, we will get the greatest element of the remaining elements.

Let us make it simpler by taking the same example,

Now we will perform the same Algorithm again on the above array.

bubble sort

We get the second largest element at 2nd last index after performing the above algorithm for one more time.

NOTE that this time we performed the above algorithm on the remaining six elements excluding the last one.

Similarly, if we perform the algorithm, again and again, we will finally get a sorted array and this is the masterstroke logic of Bubble Sorting.

Now let us see the program of bubble sort in C/C++.

Complete program of bubble sort in C/C++

void Bubble_Sort(int *arr, int n) {
      for(int i = 0; i < n; i++) 
      {
            for(int j = 0; j < n-i-1; j++) {
                   if(arr[i] > arr[i+1]) {
                          swap(arr[i], arr[i+1]);
                   }
            }
      }
}

This is the complete Bubble Sort code and hopes it is clear to you. I have represented the same logic with the help of the code.[Learn about prefix sum]

Analysis of Bubble Sort

The above Algorithm takes two nested loops, so the overall time Complexity of the Algorithm will be O(n^2).

Can we improve this time Complexity..?

Yes, we can improve the complexity, now let us consider that a sorted array is given to us and we have to perform a bubble sort to it.

bubble sort

From the above Algorithm, although we will not perform any swapping still our code will run for (n * n) times which will unnecessarily increase the overall complexity of the code.

So how to improve it..??

NOTE that worst-case complexity will always remain O(n^2), but we can improve best-case complexity.


Optimized Bubble Sort Algorithm

Now we will discuss how can we improve the complexity of the best case.

The idea is that if we don’t perform any swapping at any stage we will simply jump out of the main for a loop because no swapping means our array is already sorted.

Let us understand by the above example,

optimized bubble sort

We didn’t perform any swapping in the above iteration which ensures that our array is already sorted.

This small observation can improve our code.

Now let us see the optimized code, program of bubble sort in C/C++.

Program of optimized bubble sort in C/C++

void Bubble_Sort(int *arr, int n) {
      for(int i = 0; i < n; i++) 
      {
            bool flag = false;
            for(int j = 0; j < n-i-1; j++) {
                   if(arr[i] > arr[i+1]) {
                          swap(arr[i], arr[i+1]);
                          flag = true;
                   }
            }
            if(flag == false) break;
      }
}

We have declared a flag variable that will keep track of whether any swapping is taking place or not. If no swapping took place, it will simply break the loop and come out of it.

Time Complexity: O(n) Best Case
Time Complexity: O(n^2) Average and worst Case

NOTE Bubble Sorting is an in-place and stable Algorithm. In-place means that we don’t need any extra space to perform it and stable means if two equal elements occur, the relative order will be maintained.

Hope Bubble Sort is clear to you, usually, bubble Sort is not used because of its complexity. There are many sorting algorithms that are more efficient than Bubble Sorting and we will discuss all of it later.

That’s all folks..!!! [Wikipedia]

Tagged : /