Merge Sort is the perfect example of the Divide and Conquer algorithm design. Given an array, it divides the array into two halves, sorts these two halves recursively, and then, it merges the two smaller sorted arrays into a larger sorted array.
Amongst popular sorting algorithms, Merge Sort stands out for a reason. Do you know why?

Its time complexity is impressive!
In this blog, you will gain a thorough understanding of Merge Sort and try out fun activities to get hands-on with this amazing problem-solving algorithm.
Without further ado, let’s dive in and learn all about Merge Sort!

Merge Sort’s Divide and Conquer Algorithm Design

Divide and conquer is a popular algorithm design technique where a huge or cumbersome problem is broken down into simpler, solvable subproblems. The solutions of the subproblems are combined to solve the original problem.
Let us see how this logic is applied in Merge Sort!
You would have come across Merge Sort examples in the following way:

Although this is the big picture, it does not clearly define how the recursive calls occur.

Take a look at the pseudocode:

Mergesort (A[0..n-1])
//Input: An array A[0..n-1]
//Output: Array A[0..n-1] sorted in increasing order

//If the array contains just one element, or if it is empty, it is already sorted
If n < 2
	return
else
    //copy first half of the array A to an array B
    copy A[0..floor(n/2) - 1] to B[0..floor(n/2) - 1] 
    //copy second half of the array A to an array C
    copy A[floor(n/2)..n - 1] to C[0..floor(n/2) - 1]
    //recursively divide array B until base case is reached 
    Mergesort(B[0..floor(n/2) - 1)
    //recursively divide array C until base case is reached
    Mergesort(C[0..floor(n/2) - 1)
    //Merge sorted arrays B and C back into A 
    Merge (B,C,A)

In Merge Sort, you must keep splitting the array until you reach the base case. That is, until you have only one item. One item is considered to be a sorted array.
An empty array also falls under the base case. It is sorted.

Recursion

Merge Sort has a recursive function that splits the array recursively until the base case is reached.

Merge subroutine

It also has a merge subroutine that compares each element in two arrays, at every level of division, sorts, and then merges them.
Notice the operation ‘floor’ in the pseudocode. This is to make sure that Merge Sort works for an odd number of input sizes as well. (Ex: floor(5.4) = 5)

Tracing the flow of Merge Sort

Implementation of Merge Sort in Python

def merge_sort(array, l_index, r_index):
#recursive function
if l_index < r_index:
    mid = (l_index + r_index)//2
    merge_sort(array, l_index, mid)
    merge_sort(array, mid + 1, r_index)
    merge(array, l_index, r_index, mid)
#merge subroutine

def merge(array, l_index, r_index, mid):
#Merge Sort needs auxiliary space for merging. L_half and r_half are two arrays that #are used to store elements after each comparison made during sorting
l_half = array[l_index:mid + 1]
r_half = array[mid+1:r_index+1]
l_half_index = 0
r_half_index = 0
sorted_index = l_index

#compare sorted left and right subarrays and merge them
while l_half_index < len(l_half) and r_half_index < len(r_half):
    if l_half[l_half_index] <= 1 r_half[r_half_index]: array[sorted_index]="l_half[l_half_index]" l_half_index="l_half_index" + else: r_half_index="r_half_index" sorted_index="sorted_index" #there could be elements still left after each comparison has been made for i in range(l_half_index,len(l_half)): range(r_half_index,len(r_half)): merge_sort(array, 0, len(array) -1) print(array) < code>

Input

array = [33,1,60,14,16,1,800]

Output

[1, 1, 14, 16, 33, 60, 800]

Test your understanding

Q1 Given the following list of numbers, [80, 1, 40, 22, 10, 11, 70, 13, 2, 13, 10, 65, 13, 15, 16, 7] which answer illustrates the list to be sorted, after three recursive calls to merge_sort?

1. [2, 13, 10, 65, 13, 15, 16, 7]
2. [80,1]
3. [80, 1, 40, 22]
4. [80]

Q2 Given the following list of numbers, [80, 1, 40, 22, 10, 11, 70, 13, 2, 13, 10, 65, 13, 15, 16, 7] which answer illustrates the first two lists to be merged?

1. [80, 1] and [40, 22]
2. [1, 10, 11, 13, 22, 40, 80] and [2, 7, 10, 13, 13, 15, 16, 65]
3. [80] and [1]
4. [2] and [7]

Q3 What would be the first left split of the array [8, 1, 5, 10, 11, 2, 6] according to the pseudocode we saw earlier?

1. [8, 1, 5]
2. [8, 1, 5, 10]

Time Complexity Analysis of Merge Sort

How does Merge Sort have Θ(n*logn) time complexity?

Firstly, Merge Sort makes n - 1 comparisons during sorting. For example, consider two arrays

[1, 3] and [2, 4]

Compare 1 with 2. 1 < 2, hence 1 is added into the array.

Compare 3 with 2. 2 < 3, hence 2 is added into the array.

Compare 3 with 4. 3 < 4, hence 3 is added into the array.

4 is the only element left, it is added into the array.

Now, you  have n - 1 comparisons.

Consider an input of size n = 8

The figure above demonstrates that for an input size of 8, three levels of division are needed. Thus the number of levels of division is log2(8) = 3
Writing log as a function of n, we get log2(n).
For n = 2k if you keep dividing further, at each level, you can generalize the above calculations as ∑ 2k[n/2k-1] with lower bound as k = 0 and upper bound as log(n) - 1
It results in Θ(n*logn)
Worst case: Assume for the sake of simplicity, that n is a power of 2. Let C(n) be the number of key comparisons made. The equation below defines the amount of work that needs to be done to divide and merge the arrays.
C(n) = 2C(n/2) + Cmerge (n)
C(n/2) is the number of comparisons at each left and right split.
C(1) = 0 (For just one element no comparisons are made)
Cmerge (n) represents the number of comparisons made while merging.
At each step, exactly one comparison is made, after which, the total number of elements in the two arrays still needed to be compared is reduced by one.
In the worst case, neither of the two arrays becomes empty, before the other one contains just one element.
Hence, for the worst case, Cmerge (n) is n - 1
An example of an array that would be the worst case scenario for Merge Sort is [1, 9, 5, 13, 3, 11, 7, 15]..
Cworst(n) = 2Cworst(n/2) + n - 1
Using master’s theorem, you can conclude that
Cworst(n) = nlog2n + n - 1
Best case: In the best case scenario, the array is already sorted, but we still have to split and recombine it back.

Time complexity curve plot using Python

The merge_sort function that we wrote previously, is used to plot the curve for random input.
Python’s random module is used to generate random numbers as input.
Time module is used to measure how much time was taken for merge_sort to finish execution. Here we plot a graph of Input size against Time taken.

import time
from random import randint

arr1 = [randint(0,1000) for i in range(10000)]
times=[]

for x in range(0,10000,100):
    start_time = time.time()
    arr2 = (arr1[:x])
    merge_sort(list2,0, len(arr2)-1)
    elapsed_time = time.time() - start_time
    times.append(elapsed_time)
    elapsed_time
x=[i for i in range(0,10000,100)]

import matplotlib.pyplot as plt
%matplotlib inline
plt.xlabel("No. of elements")
plt.ylabel("Time required")
plt.plot(x,times)

Selection Sort’s time complexity clearly appears to be quadratic. For larger values of input size, Merge Sort’s time complexity curve can be enhanced.

Take a deeper look at Merge Sort

Analysis of sorting algorithms needs three things to be considered. They are time complexity, space complexity, and stability.

Time complexity
Merge Sort has an efficient time complexity of Θ(n*logn). But, quicksort is still faster, as long as a random pivot is chosen.

Space complexity
Merge Sort, like other sorting algorithms, does not work in-place.
An in-place algorithm is a sorting algorithm in which the sorted items occupy the same storage as the original ones.
But Merge Sort makes copies of the left and right half of the given array. It requires a linear amount of extra storage space, Θ(n).

Stability
Merge Sort is a stable algorithm. An algorithm is said to be stable when it keeps elements with equal values in the same relative order in the output as they were originally, in the input.

The efficiency of Merge Sort, apart from it having a great time complexity, is that you don't need to read all the data in memory at once. Because of the divide-and-conquer nature of the algorithm, it can be easily parallelized.

Applications of Merge Sort

Sorting linked lists

You have seen merge sort being implemented using arrays. However, in practice merge sort works better with linked lists. This is because you don’t have to store elements linearly in linked lists.

Items to a linked list can be inserted in the middle in Θ(1) extra space and Θ(1) time. Hence, merge sort is more efficient when linked lists are used.

Counting inversions in an array

Inversion counting is about checking how far, or close an array is from being sorted.

E- commerce websites have a section - "You might like.”

To display the options under this, they maintain an array for all the user accounts.

Merge sort helps to check the least number of inversions count with your array of choices. Based on this, they will recommend to you about what other users bought or liked.

External Sorting

In practice, enormous amounts of data is processed. Sorting such huge amounts of data needs additional, external memory. Usually an external hard drive is used, when data does not fit in memory. When implementing External Sorting, merge sort plays a crucial role.

Test your understanding

Q4 Merge Sort requires an auxiliary space of

1. Θ(1)
2. Θ(n)

Q5 The input size of the array to be sorted with Merge Sort is 9. How many levels of division does Merge Sort do?

Q6 Say you have two sorted lists of size m and n. The number of comparisons in the worst case by the Merge Sort algorithm will be

1. m x n
2. m + n
3. m + n - 1

Try it yourself

1. Apply Merge Sort to sort the list L, E, A, R, N, B, Y, D, O, I, N, G in alphabetical order
2. Implement Merge Sort using linked lists
3. Use python’s pygorithm module to learn more about all sorting algorithms.

Master Insertion Sort Before Your Next Big Interview

Learn the details of insertion sort and how you can use it effectively to sort your dataset

Crio BlogHarshita Bansal

Before you begin..

Try giving a shot at common MAANG Sorting Algorithms Interview Questions before reading the blog.

After you read the blog..

Answer more advanced questions to be absolutely interview-ready. Check out the quiz at the end. Read this blog to get a perfect score in that quiz :)

The arrangement of data in a specific order (ascending or descending) is termed sorting in data structures. Sorting data makes it easier to search through a given data sample, efficiently and quickly.

Why are Sorting Algorithms Important?

Since sorting can often help reduce the algorithmic complexity of a problem, it finds significant uses in computer science.
A quick Google search reveals that there are over 40 different sorting algorithms used in the computing world today. Crazy right?
Well, you will be flabbergasted when you realize just how useful sorting algorithms are in real life. Some of the best examples of real-world implementation of the same are:
- Bubble sorting is used in programming TV to sort channels based on audience viewing time!
- Databases use external merge sort to sort sets of data that are too large to be loaded entirely into memory!
- Sports scores are quickly organized by quick sort algorithm in real-time!!

How well do you know your sorting algorithms? Take this quiz to find out >>

Types of Sorting in Data Structures

Want to brush up your sorting algorithms before an interview? Answer these questions before you go >>

• Comparison-based sorting: In comparison-based sorting techniques, a comparator is defined to compare elements or items of a data sample. This comparator defines the ordering of elements. Examples are: Bubble Sort, Merge Sort.
• Counting-based sorting: There's no comparison involved between elements in these types of sorting algorithms but rather work on calculated assumptions during execution. Examples are : Counting Sort, Radix Sort.
• In-Place vs Not-in-Place Sorting: In-place sorting techniques in data structures modify the ordering of array elements within the original array. On the other hand, Not-in-Place sorting techniques use an auxiliary data structure to sort the original array. Examples of In place sorting techniques are: Bubble Sort, Selection Sort. Some examples of Not in Place sorting algorithms are: Merge Sort, Quick Sort.

Everything You Need To Know About Merge Sort

Learn the fundamentals of Merge Sort with an example. Sharpen your understanding with fun quizzes and activities.

Crio BlogAbheetha Pradhan

The Complete Quick Sort Guide

Learn the fundamentals of Quick Sort with an example. Sharpen your understanding with fun quizzes and activities

Crio BlogAbheetha Pradhan

This article will enable your problem solving skills with the Top 10 Sorting Algorithms used in the computing world today including bubble sort and merge sort algorithms.

You will also be diving deep into the working of various sorting techniques with intuitive examples covering time and space complexities in best and worst-case scenarios.

Time Complexity Simplified with Easy Examples

Find out what is time complexity. Understand how to analyze time complexities with simple examples.

Crio BlogSandipan Das

Finally, we'll wrap up with a broad-spectrum analysis as to which algorithm stands out in terms of time and space complexities.

Sorting Algorithms in Java vs C++

Java is the most popular language of choice when it comes to implementing algorithms and working with data structures in the software industry.

Level up your foundational programming skills in Java and practice the most relevant Data Structure questions in Crio's Backend Developer Program. Check out the full syllabus here >>

Although this blog focuses heavily on C++ based implementations, don't fret because as long as your logical understanding of these algorithms is strong, the only thing holding you back is basic syntactic differences between Java and C++.

Want to build your foundations of Java concepts? Check out these free immersive activities on Crio's learning platform >>

So without further ado, let's dive right in.

Need guidance with problem-solving and data structures? Go through Crio's Data Structures Track and unlock what it takes to tackle unseen problems with ease.  

Top 10 Sorting Algorithms You Need To Know

1. Bubble Sort

The basic idea of bubble sorting is that it repeatedly swaps adjacent elements if they are not in the desired order. YES, it is as simple as that.
If a given array of elements has to be sorted in ascending order, bubble sorting will start by comparing the first element of the array with the second element and immediately swap them if it turns out to be greater than the second element, and then move on to compare the second and third element, and so on.

Understanding Bubble Sort algorithm with a simple example

Let's try to understand the intuitive approach behind bubble sort with an example:

Now that you've understood the intuitive idea behind bubble sort, it's time to take a look at its standard C++ implementation.

Implementation in C++

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

void Bubble_Sort(int vec[], int n){
	int i, j;
	for (i = 0; i < n-1; i++)
	for (j = 0; j < n-i-1; j++)
		if (vec[j] > vec[j+1])
			swap(vec[j], vec[j+1]);
}
int main(){
	int vec[] = {5, 3, 4, 2, 1};
	int n = sizeof(vec)/sizeof(vec[0]);
	Bubble_Sort(vec, n);
	cout<<"Sorted array: \n";
	for (int i = 0; i < n; i++)
		cout << vec[i] << " ";
	cout << endl;
}

Time Complexity:

• Worst Case: O(n^2)
• Average Case: O(n*logn)
• Best case: O(n*logn)

Auxiliary Space Complexity: O(1)

Also read: Time Complexity Simplified with Easy Examples

Use Cases

• It is used to introduce the concept of a sorting algorithm to Computer Science students.
• In computer graphics, bubble sorting is quite popular when it comes to detecting a very small error (like swap of just two elements) in almost-sorted arrays.

Try it yourself

Q. Given an array of n input integers, return the sum of maximum and minimum elements of the array. [Constraint: Use Bubble Sorting]

Input:

• n -> Size of array (n>1)
• 'n' array elements below

Output: A single line representing the required sum

P.S: Don't forget to drop a comment below if you face issues with this problem.

2. Selection Sort

Selection sort is a sorting algorithm in which the given array is divided into two subarrays, the sorted left section, and the unsorted right section.
Initially, the sorted portion is empty and the unsorted part is the entire list. In each iteration, we fetch the minimum element from the unsorted list and push it to the end of the sorted list thus building our sorted array.
Still a bit fuzzy? Take a look at this awesome example below.

Understanding Selection Sort algorithm with an example

Let's try to understand the intuitive idea behind selection sort with a simple example:

Seems easy right? Because it is.

Now go ahead and take a look at its basic C++-based implementation.

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

void Selection_Sort(int vec[], int n){
	int i, j, pos;
	for (i = 0; i < n-1; i++){
		pos = i;
		for (j = i+1; j < n; j++)
		if (vec[j] < vec[pos])
			pos = j;
		swap(vec[pos], vec[i]);
	}
}

int main(){
	int vec[] = {25, 22, 27, 15, 19};
	int n = sizeof(vec)/sizeof(vec[0]);
	Selection_Sort(vec, n);
	cout << "Sorted array: \n";
	for (int i=0; i < n; i++)
		cout << vec[i] << " ";
	cout << endl;
	return 0;
}

Time Complexity:

• Worst Case: O(n*n)
• Average Case: O(n*logn)
• Best case: O(n*logn)

Auxiliary Space Complexity: O(1)

Also read: Time Complexity Simplified with Easy Examples

Use Cases

• It is used when the size of a list is small. (Time complexity of selection sort is O(N^2) which makes it inefficient for a large list.)
• It is also used when memory space is limited because it makes the minimum possible number of swaps during sorting.

Try it yourself

Q. Given an array of n input integers, return the absolute difference between the maximum and minimum elements of the array. [Constraint: Use Selection Sorting]

Input:

• n -> Size of array (n>1)
• 'n' array elements below

Output: A single line representing the required difference

Build 5 mini-projects and master essential data structures and algorithms you need to crack your next big tech interview.

3. Insertion Sort

Insertion sort is a sorting algorithm in which the given array is divided into a sorted and an unsorted section. In each iteration, the element to be inserted has to find its optimal position in the sorted subsequence and is then inserted while shifting the remaining elements to the right.

Master Insertion Sort Before Your Next Big Interview

Learn the details of insertion sort and how you can use it effectively to sort your dataset

Crio BlogHarshita Bansal

Understanding Insertion Sort algorithm with an example

Here's an example to help you understand insertion sort better:

Now that you've understood how insertion sorting actually works, take a look at its standard C++ implementation.

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

void Insertion_Sort(int vec[], int n){
	int i, x, j;
	for (i = 1; i < n; i++){
		x = vec[i];
		j = i - 1;
		while (j >= 0 && vec[j] > x){
			vec[j + 1] = vec[j];
			j = j - 1;
		}
		vec[j + 1] = x;
	}
}

int main(){
	int vec[] = { 25, 22, 27, 15, 19 };
	int n = sizeof(vec) / sizeof(vec[0]);
	Insertion_Sort(vec, n);
	for (int i = 0; i < n; i++)
		cout << vec[i] << " ";
	return 0;
}

Time Complexity:

• Worst Case: O(n*n)
• Average Case: O(n*logn)
• Best case: O(n*logn)

Auxiliary Space Complexity: O(1)

Use Cases

• This algorithm is stable and is quite fast when the list is nearly sorted.
• It is very efficient when it comes to sorting very small lists (example say 30 elements.)

Try it yourself

Q. Given a list of numbers with an odd number of elements, find the median? [Constraint: Use Insertion Sort]

Input:

• n -> Size of array (n>0)
• 'n' array elements below

Output: A single line representing the required median.

P.S: Don't forget to share your approach with us in the comments below!

4. Quick Sort

Quick Sort is a divide and conquer algorithm. The intuitive idea behind quick sort is it picks an element as the pivot from a given array of elements and then partitions the array around the pivot element. Subsequently, it calls itself recursively and partitions the two subarrays thereafter.

Understanding Quick Sort algorithm with a visualization

The logical steps involved in Quick Sort algorithm are as follows:

• Pivot selection: Picks an element as the pivot (here, we choose the last element as the pivot)
• Partitioning: The array is partitioned in a fashion such that all elements less than the pivot are in the left subarray while all elements strictly greater than the pivot element are stored in the right subarray.
• Recursive call to Quicksort: Quicksort function is invoked again for the two subarrays created above and steps are repeated.

Comments have been included in the implementation below to help you understand the Quick Sort algorithm better.

#include <bits/stdc++.h>
using namespace std;
 
int partition (int vec[], int lt, int rt){
	int pivot = vec[rt]; // pivot
	int i = (lt - 1);
	for (int j = lt; j <= rt - 1; j++){
		if (vec[j] < pivot){
			i++; swap(vec[i], vec[j]);
		}
	}
	swap(vec[i + 1], vec[rt]);
	return (i + 1);
}
 
/* vec[] --> array to be sorted,
lt --> Starting index,
rt --> Ending index*/
void Quick_Sort(int vec[], int lt, int rt){
	if (lt < rt){
		/* mid is partitioning index, vec[p] is now
		at right place */
		int mid = partition(vec, lt, rt);
		// Separately sort elements before
		// partition and after partition
		Quick_Sort(vec, lt, mid - 1);
		Quick_Sort(vec, mid + 1, rt);
	}
}
 
int main(){
	int vec[] = {14, 21, 5, 2, 3, 19};
	int n = sizeof(vec) / sizeof(vec[0]);
	Quick_Sort(vec, 0, n - 1);
	cout << "Sorted array: ";
	for (int i = 0; i < n; i++)
		cout << vec[i] << " ";
	return 0;
}

Time Complexity:

• Worst Case: O(n*n)
• Average Case: O(n*logn)
• Best case: O(n*logn)

Auxiliary Space Complexity: O(1)

Use Cases

• Quick Sort is probably more effective for datasets that fit in memory.
• Quick Sort is appropriate for arrays since is an in-place sorting algorithm (i.e. it doesn’t require any extra storage)

Try it yourself

Q. Given a list of numbers with an odd/even number of elements, find the median? [Constraint: Use Quick Sort]

Input:

• n -> Size of array (n>0)
• 'n' array elements below

Output: A single line representing the required median.

P.S: Need a hint? Drop a comment below.

5. Merge Sort

Merge Sort is a divide-and-conquer algorithm. In each iteration, merge sort divides the input array into two equal subarrays, calls itself recursively for the two subarrays, and finally merges the two sorted halves.

Everything You Need To Know About Merge Sort

Learn the fundamentals of Merge Sort with an example. Sharpen your understanding with fun quizzes and activities.

Crio BlogAbheetha Pradhan

Understanding Merge Sort algorithm with a visualization

Now that you're familiar with the intuition behind merge sort, let's take a look at its implementation.

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

void merge(long vec[], long lt, long m, long rt){
    long n1 = m - lt + 1;
    long n2 = rt - m;
    long L[n1], R[n2];
    for (long i = 0; i < n1; i++)
        L[i] = vec[lt + i];
    for (long j = 0; j < n2; j++) R[j] = vec[m+1+j];
    long i = 0, j = 0;
    long k = lt;
    while (i < n1 and j < n2) {
        if (L[i] <= R[j]) {
            vec[k] = L[i]; i++;
        }
        else {
            vec[k] = R[j]; j++;
        }
        k++;
    }
    while (i < n1) {
        vec[k] = L[i]; i++; k++;
    }
    while (j < n2) {
        vec[k] = R[j]; j++; k++;
    }
}

void Merge_Sort(long vec[],long lt,long rt){
    if(lt>=rt) return;
    long m =lt+ (rt-lt)/2;
    Merge_Sort(vec,lt,m);
    Merge_Sort(vec,m+1,rt);
    merge(vec,lt,m,rt);
}

void printArray(long A[], long size){
    for (long i = 0; i < size; i++)
        cout << A[i] << " ";
}
int main(){
    long arr[] = {16, 19, 14, 20, 12, 13};
    long arr_size = sizeof(arr) / sizeof(arr[0]);
    cout << "Unsorted array is: ";
    printArray(arr, arr_size);
    Merge_Sort(arr, 0, arr_size - 1);
    cout << "\nSorted array is: ";
    printArray(arr, arr_size);
    return 0;
}

Time Complexity:

• Worst Case: O(n*logn)
• Average Case: O(n*logn)
• Best case: O(n*logn)

Auxiliary Space Complexity: O(n)

Use Cases

• Merge sort is quite fast in the case of linked lists.
• It is widely used for external sorting where random access can be quite expensive compared to sequential access.

Try it yourself

Q. Find the intersection of two unsorted arrays [Constraint/Hint: Use Merge Sort]

Input:

• n -> Size of array (n>1)
• 'n' array elements below

Output: An array representing the intersection of the two unsorted arrays.

Master Arrays, Linked lists, Stacks/Queues, Trees, and Graphs and build your career (with job guarantee) in Back End or Full Stack development. Here's how.

6. Counting Sort

Counting Sort is an interesting sorting technique primarily because it focuses on the frequency of unique elements between a specific range (something along the lines of hashing).
It works by counting the number of elements having distinct key values and then building a sorted array after calculating the position of each unique element in the unsorted sequence.
It stands apart from the algorithms listed above because it literally involves zero comparisons between the input data elements!

Understanding Counting Sort algorithm with an example

Now go ahead and quickly take a look at its implementation in C++

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

void print(long *vec, long n) {
   for(long i = 1; i<=n; i++)
      cout << vec[i] << " ";
   cout << "\n";
}

long getMax(long vec[], long n) {
   long max = vec[1];
   for(long i = 2; i<=n; i++) {
      if(vec[i] > max)
         max = vec[i];
   }
   return max;
}
void countSort(long *vec, long n) {
   long output[n+1];
   long max = getMax(vec, n);
   long count[max+1];
   for(long i = 0; i<=max; i++)
      count[i] = 0;
   for(long i = 1; i <=n; i++)
      count[vec[i]]++;
   for(long i = 1; i<=max; i++)
      count[i] += count[i-1];
   for(long i = n; i>=1; i--) {
      output[count[vec[i]]] = vec[i];
      count[vec[i]] -= 1;
   }
   for(long i = 1; i<=n; i++) {
      vec[i] = output[i];
   }
}
int main() {
   long n;
   cout << "Enter the size of array: ";
   cin >> n;
   long arr[n+1];
   cout << "Enter elements:" << endl;
   for(long i = 1; i<=n; i++)
      cin >> arr[i];
   cout << "Unsorted array: ";
   print(arr, n);
   countSort(arr, n);
   cout << "Sorted array: ";
   print(arr, n);
}

Time Complexity:

• Worst Case: O(n+k), where n is the size of input array and k is the count of unique elements in the array

Auxiliary Space Complexity: O(n+k)

Use Cases

• Counting sort is quite efficient when it comes to sorting countable objects (such as bounded integers).
• It is also used when sorting is to be achieved in linear complexity.

Try it yourself

Q. Given an array of n input integers, return the absolute difference between the maximum and minimum elements of the array in linear time complexity.

Input:

• n -> Size of array (n>1)
• 'n' array elements below

Output: A single line representing the required difference.

P.S: Don't forget to share your approach with us in the comments below.

Stop scrolling..

You're done with over 50% of the blog. Want to test your knowledge on how well you've understood sorting algorithms so far? Take these quizzes to know where you stand.

7. Radix Sort

As you saw earlier, counting sort stands apart because it's not a comparison-based sorting algorithm like Merge Sort or Bubble Sort, thereby reducing its time complexity to linear time.
BUT, counting sort fails if the input array ranges from 1 to n^2 in which case its time complexity increases to O(n^2).
The basic idea behind radix sorting is to extend the functionality of counting sort to get a better time-complexity when input array elements range from 1 till n^2.

Understanding Radix Sort with an example

Algorithm:

For each digit i where i varies from the least significant digit to the most significant digit of a number, sort input array using count sort algorithm according to the ith digit. Remember we use count sort because it is a stable sorting algorithm.

Example:

Thus we observe that radix sort utilizes counting sort as its subroutine throughout its execution. Now take a look at its C++ implementation.

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

long getMax(long vec[], long n){
    long maxval = vec[0];
    for (long i = 1; i < n; i++)
        if (vec[i] > maxval)
            maxval = vec[i];
    return maxval;
}

void Count_Sort(long vec[], long n, long x){
    long res[n];
    long i, count[10] = {0};
    for (i = 0; i < n; i++)
        count[(vec[i] / x) % 10]++;
    for (i = 1; i < 10; i++)
        count[i] += count[i - 1];
    for (i = n - 1; i >= 0; i--) {
        res[count[(vec[i] / x) % 10] - 1] = vec[i];
        count[(vec[i] / x) % 10]--;
    }
    for (i = 0; i < n; i++)
        vec[i] = res[i];
}

void Radix_Sort(long vec[], long n){
    long m = getMax(vec, n);
    for (long x = 1; m / x > 0; x *= 10)
        Count_Sort(vec, n, x);
}

int main(){
    long vec[] = { 53, 89, 150, 36, 633, 233 };
    long n = sizeof(vec) / sizeof(vec[0]);
    Radix_Sort(vec, n);
    for(long i = 0; i < n; i++)
      cout << vec[i] << " ";
    return 0;
}

Time Complexity: O(d(n+b)), where b represents the base of array element (eg- 10 represents decimal)

Auxiliary Space Complexity: O(n+d), where d is the maximum number of digits in an array element.

Use Cases

• Radix sorting finds applications in parallel computing.
• It is also used in the DC3 algorithm (Kärkkäinen-Sanders-Burkhardt) while making a suffix array.

Try it yourself:

Q. Given two sorted arrays(arr1[] and arr2[]) of size M and N of distinct elements. Given a value Sum. The problem is to count all pairs from both arrays whose sum is equal to Sum.

Note: The pair has an element from each array. [Constraint: Use Radix Sort]

Input:

• n -> Size of array (n>1)
• 'n' array elements below

Output: A single line representing the required number of pairs

P.S: Don't forget to share your approach with us in the comments below.

8. Bucket Sort

Bucket Sort is a comparison-based sorting technique that operates on array elements by dividing them into multiple buckets recursively and then sorting these buckets individually using a separate sorting algorithm altogether. Finally, the sorted buckets are re-combined to produce the sorted array.

Understanding Bucket Sort algorithm with pseudocode

We can probe further into the working of bucket sort by assuming that we've already created an array of multiple 'buckets' (lists). Elements are now inserted from the unsorted array into these "buckets" based on their properties. These buckets are finally sorted separately using the insertion sort algorithm as explained earlier.

Pseudocode:

Begin
   for i = 0 to size-1
      insert array[i] into the bucket indexed (size * array[i])
   done
   for i = 0 to size-1
      sort bucket[i] using insertion sort
   done
   for i = 0 to size-1
      Combine items of bucket[i] and insert in array in sorted order
   done
End

Well if you're still unsure about the bucket sort algorithm, go back and review the pseudocode one more time.

.

.

Done? All right. Now take a quick look at its implementation below.

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

void Bucket_Sort(float arr[], int n){
	vector<float> bucket[n];
	for (int i = 0; i < n; i++) {
		int bi = n * arr[i];
		bucket[bi].pb(arr[i]);
	}
	for (int i = 0; i < n; i++)
		sort(bucket[i].begin(), bucket[i].end());
	int pos = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < bucket[i].size(); j++)
			arr[pos++] = bucket[i][j];
}

int main(){
	float arr[]= { 0.474, 0.582, 0.452, 0.6194, 0.553, 0.9414 };
	int n = sizeof(arr) / sizeof(arr[0]);
	Bucket_Sort(arr, n);
	cout << "Sorted array is \n";
	for (int i = 0; i < n; i++)
		cout << arr[i] << " ";
	return 0;
}

Time Complexity:

• Worst Case: O(n*n)
• Average Case: O(n + k)
• Best case: O(n + k)

Auxiliary Space Complexity: O(k), worst case

Use Cases

• Bucket sorting is used when input is uniformly distributed over a range.
• It is also used for floating point values.

Try it yourself

Q. You are given two arrays, A and B, of equal size N. The task is to find the minimum value of A[0] * B[0] + A[1] * B[1] +…+ A[N-1] * B[N-1], where shuffling of elements of arrays A and B is allowed. [Constraint: Use Bucket Sort]

Input:

• n -> Size of array (n>1)
• 'n' array elements representing the first array
• 'n' array elements representing the second array

Output: A single line representing the required sum

P.S: Need help? Drop a comment below.

9. Comb Sort

Comb sort is quite interesting. In fact, it is an improvement over the bubble sort algorithm. If you've observed earlier, bubble sort compares adjacent elements for every iteration.
But for comb sort, the items are compared and swapped by a large gap value. The gap value shrinks by a factor of 1.3 for each iteration until the gap value reaches 1, at which point it stops execution.
This shrink factor has been empirically calculated to be 1.3 (after testing Comb Sort algorithm on over 2, 00, 000 random arrays) [Source: Wiki]

Understanding Comb Sort algorithm with a simple example

Pretty simple right? Well, let's have a look at it's C++ implementation:

#include<bits/stdc++.h>
using namespace std;
void Comb_Sort(long *vec, long size) {
   long gap = size;
   bool f = true;
   while(gap != 1 || f == true) {
      gap = (gap)/1.3;
      if(gap<1) gap = 1;
      f = false;
      for(long i = 0; i< size - gap; i++) {
         if(vec[i] > vec[i+gap]) {
            swap(vec[i], vec[i+gap]);
            f = true;
         }
      }
   }
}
int main() {
   long arr[10]={ 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
   cout << "Array before Sorting: ";
   for(long i = 0; i < 10; i++)
      cout << arr[i] << " ";
   cout << endl;
   Comb_Sort(arr, 10);
   cout << "Array after Sorting: ";
   for(long i = 0; i < 10; i++)
      cout << arr[i] << " ";
   cout << endl;
}

Time Complexity:

• Worst Case: O(n^2)
• Average Case: O(n^2/2^p), where p is a number of increment
• Best case: O(n*logn)

Auxiliary Space Complexity: O(1)

Use Cases

• Comb Sort eliminates small values at the end of the list by using larger gaps.
• It is a significant improvement over Bubble Sort.

Try it yourself

Q. Given an array, find the most frequent element in it. If there are multiple elements that appear maximum number of times, print any one of them. [Constraint: Use Comb Sort]

Input:

• n -> Size of array (n>0)
• 'n' array elements below

Output: A single line representing the element with maximum frequency.

P.S: Did you enjoy this sorting technique? Share your opinions below.

10. Shell Sort

Shell sort algorithm is an improvement over the insertion sort algorithm wherein we resort to diminishing partitions to sort our data.
In each pass, we reduce the gap size to half of its previous value for each pass throughout the array. Thus for each iteration, the array elements are compared by the calculated gap value and swapped (if necessary).

Understanding Shell Sort algorithm with pseudocode

Start
   for gap = N / 2, where gap > 0 and gap updates to gap / 2:
      for i= gap to N – 1:
         for j = j-gap to 0, decrease by gap value:
            if arr[j+gap] >= arr[j]
               break
            else
               swap arr[j+gap] with arr[j]
         done
      done
   done
End

The idea of shell sort is that it permits the exchange of elements located far from each other. In Shell Sort, we make the array N-sorted for a large value of N.
We then keep reducing the value of N until it becomes 1. An array is said to be N-sorted if all subarrays of every N’th element are sorted.
Here, gap size= floor(N/2) for each iteration
Finally, take a look at it's C++ implementation:

#include<bits/stdc++.h>
using namespace std;
int Shell_Sort(int vec[], int n){
	for (int gap = n/2; gap > 0; gap /= 2){
		for (int i = gap; i < n; i ++ ){
			int x = vec[i];
			int j;
			for (j=i; j>=gap && vec[j-gap]>x;j-=gap)
				vec[j] = vec[j - gap];
			vec[j] = x;
		}
	}
	return 0;
}

int main(){
	int vec[] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
	int n = sizeof(vec)/sizeof(vec[0]), i;
	cout << "Unsorted array: \n";
	for (int i=0; i<n; i++) cout << vec[i] << " ";
	Shell_Sort(vec, n);
	cout << "\nSorted array: \n";
	for (int i=0; i<n; i++) cout << vec[i] << " ";
	return 0;
}

Time Complexity:

• Worst Case: Depends on gap size
• Average Case: Depends on gap size
• Best case: O(n*logn)

Auxiliary Space Complexity: O(1)

Use Cases

• Insertion sort does not perform well when the close elements are far apart. Shell sort helps reduce the distance between close elements.
• It is also used when recursion exceeds a limit. The bzip2 compressor compresses it.

Try it yourself

Q. Given an unsorted array of integers. Write a program to remove duplicates from the unsorted array. [Constraint: Use Shell Sort]

Input:

• n -> Size of array (n>1)
• 'n' array elements below

Output: A single line representing the modified array.

Now that you've explored the Top 10 sorting algorithms, all that's left is to answer a few basic questions (just 3 in fact). This will hardly take a minute.

Q1. Which is the best sorting algorithm?

If you've observed, the time complexity of Quicksort is O(n logn) in the best and average case scenarios and O(n^2) in the worst case.
But since it has the upper hand in the average cases for most inputs, Quicksort is generally considered the “fastest” sorting algorithm.
At the end of the day though, the best sorting algorithm comes down to the nature of your input data (and who you ask).

Q2. What is the easiest sorting algorithm?

Bubble sort is widely recognized as the simplest sorting algorithm out there. Its basic idea is to scan through an entire array and compare adjacent elements and swap them (if necessary) until the list is sorted. Pretty simple right?

Q3. Which sorting algorithm would you prefer for nearly sorted lists?

When it comes to sorting nearly sorted data, insertion sort is the clear winner particularly because it's time complexity reduces to O(n) from a whopping O(n^2) on such a sample.

Master Insertion Sort Before Your Next Big Interview

Learn the details of insertion sort and how you can use it effectively to sort your dataset

Crio BlogHarshita Bansal

On the other hand, merge sort or quick sort algorithms do not adapt well to nearly sorted data.

Well, that's about it. At the end of the day, it's up to you to decide which sorting technique suits you the best. And yes, don't forget to try out the practice problems served alongside with each sorting technique.

How comfortable are you with sorting now?

Before you go for your next interview, be sure to know the answers to these commonly asked Sorting Algorithms questions. If you read this blog thoroughly, you're all set to get a perfect score. Ready to take the quiz?

Go beyond video-based certification courses and online bootcamps. Build the confidence you need to take on Data Structures and Algorithm questions in your next big interview and land your dream job as a Backend Developer or Full Stack Developer - Guaranteed! Find out how.

Additional resources

Don't miss these free learning resources that are an absolute essential for all developers:

1. 100+ Essential Linux commands You Must Know. Download PDF >>
2. Useful VScode shortcuts To Become A Ninja Programmer. Download PDF >>
3. Git commands Cheat Sheet. Download Cheat Sheet >>
4. 20+ Interesting Tech Projects with Step-By-Step Instructions. Download Projects >>

Found this article interesting? Show your love by upvoting this article.
We would also love to know the sorting technique that got you excited the most - let us know in the comments below.
Also, if you enjoyed reading this article, don't forget to share it with your friends!

Want to switch jobs, but insufficient Data Structures and Algorithms prep is getting in the way?

Looking for a comprehensive study plan to sharpen your DS/Algo skills? Don't feel confident about approaching unseen problems in coding interviews?

The Crio DevSprint Applied Data Structures and Algorithms program is the right fit for you. We have the most rigorous learning plan packed into an efficient 8-week schedule (details).

Topics you will master

During the course of the 8-week schedule, you will master concepts and frequently occurring problem patterns in the following topics (details):

• Foundational topics: Arrays and Strings, Linked Lists, Stacks, Hashes, Heaps, Recursion, Backtracking, Trees and Graphs, and more.
• Advanced topics: Dynamic Programming, Greedy Algorithms, Segment Trees, Tries, Spanning Tree, and more.

What you will get

1. Crio’s effective problem-solving methodology

• Don't waste your time solving hundreds of problems. When it comes to preparing for PS/DSA interviews, quality beats quantity. Our effective approach significantly improves your chances of solving unseen problems in an interview setting..

2. Targeted practice => Confidence

• You will solve 150+ problems using our recommended approach.

3. Curated concept-wise problem sets

• Explore and analyse key problem patterns with a high hit-rate in coding interviews.

4. A clear weekly plan + disciplined orchestration

• We will hold you accountable to your weekly targets. Get frequent reminders about what is due and when.

5. 16 timed mock assessments

• Two mock assessments every week.
• Measure your progress through these mocks that mimic screening tests.

6. Live mentoring sessions + daily mentoring hours

• Live sessions to discuss concepts in detail and address your questions.
• Daily mentoring hours with TAs who are joining top-tech companies like Google and Amazon.
• Watch weekly live mock interview sessions and get familiar with an interview setting.

7. Meaningful help and interventions

• Every problem ships with multiple hints to unblock yourself when stuck.
• Hints give you just enough help to move forward without giving you the whole solution - enabling you to try to solve the problem on your own.
• Solution editorials are also included to cover complexity analysis and alternative approaches.

8. A vibrant community of driven peers

• Interact with peers and work with them towards a common goal. Help each other and enhance your knowledge.

9. (Premium) Mock interviews

• Purchase mock interviews conducted by developers in Google, Amazon, Microsoft and other top-tech companies.
• Get detailed feedback on your strengths and areas of improvement.
• Targeted action items to help improve your interview performance.

Get the Crio Advantage and achieve predictable success in your next coding interview!

Note: we are currently not accepting applications for our Applied Data Structures and Algorithms track. Feel free to browse the details of the track in this post and email us at ping@criodo.com to get notified of upcoming batches.

Sorting is one of the most important problems that is studied in computer science. It is necessary for any application to run smoothly.

10 Best Sorting Algorithms - Explained with Simple Examples

Find out which is the best sorting algorithm. Understand how to use the different types of sorting algorithms with simple examples.

Crio BlogSandipan Das

Say you just started a clothing website, and you need to add a filter that sorts the clothes according to their price.

You definitely need code that will sort these clothes in a particular order.
There are some inbuilt sorting functions in most programming languages, that will easily help you do this.

But in the 1950s, computer scientists had just begun to invent sorting algorithms.
Hoare invented Quick Sort in 1961. Before you start reading about Quick Sort, think about how you would create a sorting algorithm. Doing this will make you appreciate how well thought out Quick Sort is.

Sorting particular items would mean arranging them in a particular order. For the items to be orderable, each item must be comparable with every other item. So the basic operation you’d need to perform to sort a list of items would be comparisons. Now the question is, how would you perform these comparisons. Comparing each and every item in a list with every other item is tedious.

For example, you can sort the letters of a word in alphabetical order. But you can’t sort a list of different colors, unless some sorting criteria is specified.
But a list can have identical elements, it can be empty, it can have just one element, or all the elements can be identical. Most sorting algorithms take care of all of these cases.

Quick Sort offers a solution of its own for sorting a list of items in an efficient way.

In this blog, you will learn two variants of Quick Sort

• Quick Sort with the first element in the array as the pivot
• Quick Sort with a random pivot

What is Quick Sort

Quick Sort is a Divide and Conquer algorithm.

Divide and conquer is a problem-solving technique where a problem is divided recursively into smaller instances. The solutions of these instances are then combined, which gives the solution for the original problem itself.

Quick Sort will rearrange the elements in a given array that needs to be sorted, such that it achieves a partition. An element ‘s’ is placed in this position of partition in the array, such that all the elements to the left of s are smaller than s and all the elements to the right of s are larger than s.

The element ‘s’ will be in its final position in the array once a partition has been found. Quick Sort will now proceed to recursively sort the left and right subarrays.

Check out this other Divide and Conquer algorithm in detail:

Everything You Need To Know About Merge Sort

Learn the fundamentals of Merge Sort with an example. Sharpen your understanding with fun quizzes and activities.

Crio BlogAbheetha Pradhan

Algorithm Design for Quick Sort with the first element as the pivot

Pseudocode

QuickSort(A[l..r])
//Input:A subarray A[l..r] of A[0..n-1], where l and r are left most and 
//right most indices of the subarray of A
//Output: Subarray A[l..r] sorted in non decreasing order

If l < r

	s = Partition(A[l..r]) 
    
   	 //s is split position returned by partition subroutine
	//Apply Quick Sort to array elements to the left of the partition s
    QuickSort(A,l,s-1)
    
	//Apply Quick Sort to array elements to the right of the partition s
    QuickSort(A,s+1,r) 

You can see that there are two subroutines, Partition and Quick Sort. First, you need to find a pivot(s).

What is Pivot in sorting

It is an element that needs to be placed at a position at which the array can be partitioned such that all elements to the left of the pivot are at most equal to the pivot, and all elements to the right of the pivot are greater than the pivot.

Partition will find a position or index ‘s’ where the pivot can be placed and returns this. The array now has now been split, based on this partition. The split index is then passed to QuickSort, a recursive function, which will sort the left subarray first, and then proceed to sort the right subarray, using the same idea.

Understand this better with the illustration below:

In this algorithm, you will take the first element as the pivot, and use Partition to find a split position for it. But wait, what about sorting? Partition implements this as well. Let's look at how Partition works now.

Partition(A[l..r])
//Partitions a subarray by using its first element as pivot.
//Input: A subarray A[l..r] of A[0..n-1] defined by its left and right
//indices l and r, l < r
//Output: A partition of A[l..r], with the split position returned as the //function’s value

//Assign the first element as pivot
p = A [ l ]
i = l; j = r + 1
repeat
//Traverse  left to right with i , until you find an element greater than or //equal to p
repeat i = i + 1 until A[i] >= p
//Traverse right to left with j , until you find an element lesser than or //equal to p
repeat j = j - 1 until A[j] <= p swap(a[ i ], a[ j ]) repeat the above steps until crosses>= j

swap(A[ i ],  A[ j ] ) //Undo the last swap when i >  j
swap(A[ l ],  A[ j ] )
return j

i: Starts from the leftmost index of the array. Scans left to right, comparing each element to pivot. Skips over elements that are lesser than the pivot. So, keep incrementing i, until you find a value greater than or equal to the pivot.

j: Starts from the rightmost index of the array. Scans right to left, comparing each element to the pivot. Skips over elements that are greater than the pivot. So keep decrementing j, until you find a value lesser than or equal to the pivot.

Now think about what has been accomplished, if you can't increment i anymore, and decrement j anymore. They’ve halted. Where have they halted?

There are three scenarios that might occur:

• i has not crossed j,  i < j
• i has crossed j,  i > j
• i and j are at the same position,   i = j

Case 1: i < j

If i < j, and they’ve halted, it must mean that i has found an element that must be placed to the right of the pivot, and j has found an element that must be placed to the left of the pivot.

So swap them and resume the scans. Keep in mind that you have not found the position where you need to place the pivot yet.

Case 2: i > j

In this case, you must pay attention to what value j has. In the last swap, you would have swapped two elements, the element at j, will be greater than the one at i.

What you must do now is undo this swap. Brainstorm why you need to do this.
If you don’t undo this swap, an element greater than the pivot will lie to the left of the pivot, and an element lesser than the pivot to its right.

Once you undo this swap, you will have an element at j that is smaller than the pivot. Now swap A [ l ](which is the pivot) and A [ j ].

Case 3: i = j

Finally, if the scanning indices have stopped pointing to the same indices, the value they are pointing to must be equal to ‘s’, the index of partition. The pivot is placed here.

Therefore, the array is partitioned with split position i = j = s .

In the next section, you will visualize Quick Sort with an example, and learn about how Quick Sort uses recursion.

Visualizing Quick Sort with an example

Using the algorithm you just learned for Partition, trace Partition for an array = [5, 3, 1, 9, 8]

Your trace of the array should look like the figure below. The highlighted elements are the pivots.

Here is a link to help you visualize Quick Sort

VisuAlgo - Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix)

Sorting is a very classic problem of reordering items (that can be compared, e.g. integers, floating-point numbers, strings, etc) of an array (or a list) in a certain order (increasing, non-decreasing, decreasing, non-increasing, lexicographical, etc).There are many different sorting algorithms, eac…

Sorting (Bubble, Selection, Insertion, Merge, Quick, Counting, Radix)

(select Quick Sort at the top)

Tree of recursive calls

Quick Sort will first recursively be called on the left half of the tree, then it will work on the right half.

Here you can see that all the nodes in the last level do not satisfy the condition  

l<r . So, no action is performed.

Implementation of Quick Sort in Python

# The main function that implements QuickSort
def quicksort(array, l, r):
if (l < r):
# s is partitioning index
#pivot will be placed in array[s]
s = partition(array,l , r)
# Sort elements before partition
# and after partition
quicksort(array,l, s - 1)
quicksort(array, s + 1, r)

#Partition function that sorts subarrays and returns partitioning index
def partition(array, l, r):
# Initializing pivot's index to start
i = l
pivot = array[l]
j = r+1
while(i=r or array[i]>=pivot):
break
while True:
j = j - 1
if(j<=l or array[j]<="pivot):" break array[i], array[j]="array[j]," array[i] #swap elements at i and j #undo last swap when> j
array[l], array[j] = array[j], array[l]  #swap pivot and element at j
    
return j #return partition index
    
if __name__ == "__main__":
array = [9,8,7,6,5]
quicksort(array, 0, len(array) - 1)
print(f'Sorted array: {array}')
    
    

Output: Sorted array: [5, 6, 7, 8, 9]

Implementation of Quick Sort using random pivot

Randomized Quick Sort will make use of a random pivot that is selected randomly from the array, instead of choosing the first element as the pivot. This helps to avoid the worst case scenario of Quick Sort.

In this code, you will randomly select a pivot, and you will swap it with the first element.

import random
def randomized_partition(array, l, r):
i = l
pivot = random.randrange(l,r)
# Swap positions of randomly chosen pivot and the first element in the array
array[l], array[pivot] = array[pivot], array[l]

j = r+1
while(i=r or array[i]>=array[l]):
break

while True:
j = j - 1
if(j<=l or array[j]<="array[l]):" break array[i], array[j]="array[j]," array[i] array[l], array[l] return j def randomized_quicksort(array, l, r): if (l < s="randomized_partition(array,l" , r) randomized_quicksort(array,l, - 1) + 1, __name__="=" "__main__": array="[9,8,7,6,5]" 0, len(array) print(f'sorted array: {array}') code>

Output:

Sorted array: [5,6,7,8,9]

Test your understanding

Q1. How does the array [5,2,4,9,1,9] look after the first partition?

Q2. Sorting in Quick Sort occurs within the same array

A.True

B. False

Q3. How do you make sure scan indices i and j don't go out of bound?

(Hint: Compare Quick Sort algorithm and Quick Sort Python code)

Q4. Why do we stop scanning when we find an element equal to the pivot?

Time Complexity Analysis

Time Complexity Simplified with Easy Examples

Find out what is time complexity. Understand how to analyze time complexities with simple examples.

Crio BlogSandipan Das

Best case

Quick Sort makes n + 1 key comparisons if scanning indices cross over. If not, then n comparisons are made. If all partitions occur at the middle of all subarrays, you have the best case scenario.

Cbest(n) = 2Cbest(n/2) + n for n > 1 , Cbest(1) = 0

C = number of comparisons made.

By applying masters theorem,

Cbest(n) = nlogn

Worst Case

The worst case scenario will occur when the array is already sorted. It could be sorted in increasing or decreasing order. All the splits, in this case, will occur at the extremes of the array, and at least one of the two subarrays will be empty.

It also occurs when all elements are the same.

Say you have an array that is sorted in increasing order as the input. The scan i will have to scan and compare elements with the pivot all the way till the end of the array.

First, it will make n + 1 comparisons. It will exchange the pivot element with itself. Now it will run the scan for A[1..n-1]. It will make n comparisons. Then it will scan for A[2..n-1]. It will make n - 1 comparisons, and so on.

Cworst(n) = (n+1) + n + …….. + 3 = (n+1)(n+2)/2

Which belongs to O(n2)

Time complexity comparison of Quick Sort and randomized Quick Sort

You just learned that the worst case time complexity of Quick Sort is O(n2). Randomized Quick Sort improves the performance.

The worst case time complexity is still O(n2), but the chances of it occurring are decreased.

Here you will pass a sorted array to functions quicksort, and randomized_quicksort, and see which one has a better running time.

import time
from random import randint
arr1 = [randint(0,1000) for i in range(1000)]
times=[]
times_worstcase = []
randomized_worstcase = []

for x in range(0,1000,10):
start_time = time.time()
arr2 = (arr1[:x])
quicksort(arr2,0, len(arr2)-1)
elapsed_time = time.time() - start_time
times.append(elapsed_time)
#store the sorted array in arr1, so that this imitates worst case scenario for Quick Sort
arr1 = arr2

for x in range(0,1000,10):
start_time = time.time()
arr2 = (arr1[:x])
quicksort(arr2,0, len(arr2)-1)
elapsed_time = time.time() - start_time
times_worstcase.append(elapsed_time)
arr1 = arr2
for x in range(0,1000,10):
arr2 = (arr1[:x])
start_time = time.time()
randomized_quicksort(arr2,0, len(arr2)-1)
elapsed_time = time.time() - start_time
randomized_worstcase.append(elapsed_time)
x=[i for i in range(0,1000,10)]

import matplotlib.pyplot as plt
%matplotlib inline
plt.xlabel("No. of elements")
plt.ylabel("Time required")
plt.plot(x,times_worstcase,'r')
plt.plot(x,randomized_worstcase,'b')

Output

Observe that the running time plot for Quick Sort is leaning towards n2, while randomized_quicksort appears to have nlogn.

So even though a worst case input was passed to randomized_quicksort, it avoided the worst case by selecting a random pivot instead of the first element itself as the pivot.

Time Complexity Simplified with Easy Examples

Find out what is time complexity. Understand how to analyze time complexities with simple examples.

Crio BlogSandipan Das

Further Analysis of Quick Sort

The criteria for analyzing any sorting algorithm are the following:

Time complexity

The running time of Quick Sort heavily depends on the choice of the pivot element.

If worst case scenario does not occur in Quick Sort, its performance is comparable with merge sort. Quick Sort is one of the quickest sorting algorithms. Selection sort is the slowest.

Best case : O(nlogn)

Worst case: O(n2)

Average case: O(nlogn)

Space Complexity

Quick sort is an in-place sorting algorithm. It has a space complexity of O(1)

An in-place algorithm is a sorting algorithm in which the sorted items occupy the same storage as the original ones.

However, the worst case space complexity is O(logn).

Stability

Quick Sort is not a stable algorithm. An algorithm is said to be stable when it keeps elements with equal values in the same relative order in the output as they were originally, in the input.

Quick Sort works well on large data sets. Since it is in-place, it doesn't require additional memory.

Applications of Quick Sort

• Most commercial applications use Quick Sort to sort data. Data that is a mixture of different items can be assigned priorities and sorted. Miscellaneous data, such as student details, employee details, social media account profile sorting, sorting for e-commerce websites, etc.,
  
• Since Quick Sort works in-place, it is cache friendly
  
• It is used in Operations Research and Event Driven Simulation
  
• Amongst all the sorting algorithms which have an efficiency of nlogn, Quick Sort works best for sorting randomly ordered arrays.
  
• Java’s inbuilt Arrays.sort method uses dual pivot Quick Sort algorithm.

Test Your Understanding

Q4. Strictly decreasing arrays are

A. Worst-case input

B. Best-case input

C. Neither

Q5. Find out the worst case space complexity of Quick Sort. Why is this the case?

Q6. Which scenario is the best case for Quick Sort?

A.The elements are in ascending order

B.The pivot is the smallest element all of the time.

C.The elements are in random order

D.The elements are in alternating small/large order.

Q7. Quick Sort is the fastest sorting algorithm

A. True

B. False

Try it yourself

1. Apply Quick Sort to sort the list L, E, A, R, N, B, Y, D, O, I, N, G in alphabetical order.
2. Do a comparative study of Merge Sort and Quick Sort
3. Write Quick Sort code with fewer swaps

Conclusion

Quick Sort is a heavily researched sorting algorithm as it can be improved in several ways based on how the pivot is chosen, and how the array is partitioned. It performs well on large data sets, and since it works in-place, it is sometimes a better alternative than merge sort. For a large data set of randomly organized numbers, Quick Sort does have a very low running time compared to other sorting algorithms like bubble sort and insertion sort.  So yes! Quick Sort is pretty quick in sorting!

Further reading

10 Best Sorting Algorithms - Explained with Simple Examples

Find out which is the best sorting algorithm. Understand how to use the different types of sorting algorithms with simple examples.

Crio BlogSandipan Das

Everything You Need To Know About Merge Sort

Learn the fundamentals of Merge Sort with an example. Sharpen your understanding with fun quizzes and activities.

Crio BlogAbheetha Pradhan

Time Complexity Simplified with Easy Examples

Find out what is time complexity. Understand how to analyze time complexities with simple examples.

Crio BlogSandipan Das

Master Insertion Sort Before Your Next Big Interview

Learn the details of insertion sort and how you can use it effectively to sort your dataset

Crio BlogHarshita Bansal

Why do you need knowledge of data structures and algorithms?

Data structures and Algorithms are techniques used to write efficient code for a given problem, much like how you need music theory to master an instrument. To be a good programmer you need to learn to use the right data structure and algorithm for a given problem.

Say, you need to travel to a particular spot in your city. You take a car to travel to the spot but later discover that taking the metro would have been faster and cheaper. Similarly, insufficient knowledge in DSA can lead you to write inefficient code.

In interviews, an interviewer will test you on the basis of how quickly you come up with the solution, how efficient your code is, and they can go on to ask you in-depth questions about the data structure or algorithm you’ve used to solve the problem.

The popular opinion for mastering Data Structures and Algorithms is to solve hundreds of problems. But it is actually more valuable to focus on a handful of problems and get a thorough understanding of each data structure and algorithm and how to apply them.

10 Best Sorting Algorithms You Must Know About

What is the fastest sorting algorithm? Which one is the simplest sorting algorithm? Why do we even use sorting algorithms? Get all your answers.

Crio BlogSandipan Das

Once you take this approach to learning, you will find that you can segregate problems into different types and each of these will have the same approach and algorithm that can be used.

This blog will introduce you to frequently asked DSA interview questions in some of the top IT companies in the world.

List of Questions

1. Trapping Rainwater
2. Rat in a Maze
3. House Robber
4. Merge K sorted linked lists
5. Valid Parentheses
6. Search a 2D Matrix
7. Number of Islands
8. Merge Intervals
9. Minimize Cash Flow
10. LRU Cache

1. Trapping Rainwater

Steps

Rainwater can be trapped if there are bars of higher elevations to its left and right. The amount of water that can be trapped is the difference between the minimum of the two higher elevations to the left and right and the elevation in the current bar.

Here, two-pointer approach is used which uses two different pointers, one moving from the left to the right, and another from the right to the left of the elevation map.

1. Start with the left pointer on the leftmost bar, i.e, initialize left pointer to index 0, and the right pointer on the rightmost bar i.e., initialize right pointer to index n-1. Set the amount of water stored to be 0.
2. Create two variables maxLeft and maxRight to keep track of the highest elevations encountered by the left and right pointer respectively. Initalize maxLeft and maxRight as 0.
3. Traverse the array with these two pointers until they cross each other i,e., While left pointer <= right pointer

a. Find the highest bars on the left and right sides by performing the following comparisons.

• If the elevation at left pointer is greater than maxLeft, update maxLeft.
• If the elevation at right pointer is greater than maxRight, update maxRight.

b. There will be two cases at each iteration.

• If maxLeft <= maxRight

Increment the water stored by the difference between maxLeft and the elevation at the left pointer bar.

Increment the left pointer by 1.

• If maxLeft > maxRight

Increment the water stored by the difference between maxRight and the elevation at the right pointer bar.

Decrement the right pointer by 1.

4. Display the water stored, which is the required result.

2. Rat in a Maze

Steps

Two paths exist for the rat to travel to the destination (3,3)

We will use the principle of backtracking to find all valid paths.

1. Create a path matrix of N*N dimensions to keep track of the path that the rat will take. This matrix will be used to store the path that the rat takes by marking the cells it has visited with 1s and the unvisited cells with 0s.
2. Start the traversal of the input matrix that represents the maze starting from the rat’s initial position (0,0). The rat can traverse in 4 possible ways - either down, up, right, or left. Keep track of the visited cells by marking them as visited in the path matrix.
3. If the position  (x,y) is out of the matrix, or if it is blocked (0) backtrack to the previous step taken.

Else,

• Mark (x,y) as visited in the path matrix
• If (x,y) is the destination cell,
• Then
• Print the path taken as a solution (using the path matrix) and backtrack to the previous step

Else

• Move from (x,y) to (x+1,y) (right), (x-1,y) (left), (x,y+1) (down) (x,y-1) (up), one at a time, and repeat step 4 recursively from each of these positions.
• If these don’t lead to the destination cell, unmark (x,y) as visited in the path matrix and backtrack to the previous step.

3. House Robber

Steps

1. There can be no houses so the robber can't steal any money. There can be just one house, in which case the robber steals money from that house. If there are two or more houses, the robber will try to steal the maximum amount of money without stealing from any two adjacent houses.
2. Use an array called dp[ ] with the size equal to the number of houses. Each element of this array will indicate the maximum amount of money that can be stolen from the ith house (index of that element) to the last house.

To find out the maximum money that can be stolen you need to consider every possible combination of houses from the ith house to the last house. However, this will result in repeatedly calculating certain sub-problems. By storing the result of these subproblems (the maximum money that can be stolen from ith house to the last house) in the dp array, you can optimise the solution. This is the principle of Dynamic Programming.

3. The robber can steal money in two ways as he moves from the first house to the last

a. He can rob from the current house (i) and skip the next house ( go to the house at i + 2), and from there find the maximum money that can be stolen amongst all the houses that are remaining.

So the robber steals the money from the current house + the maximum money that can be stolen from house i+2 onwards.

b. He can skip the current house and move to the next house (at i + 1) and repeat step 3. So, the robber steals the maximum amount that can be stolen from house i + 1 onwards.

4. Now, find the maximum of the values calculated at steps a and b and update the dp array to this value.

Note: If the maximum money that can be stolen at a house i has already been calculated and stored in dp[i], the value is directly used.

4. Merge K Sorted Linked Lists

Steps

1. Pair the K linked lists into groups of 2 and combine each pair in a sorted way with linear time complexity.
2. A pair of linked lists can be combined by using 2 pointers, each pointer traversing one linked list. Both pointers start at the head node of their respective list and traverse through the nodes till the end. At each step, compare the value at the two nodes and pick the smallest of the nodes. Increment that smaller node pointer while the other pointer stays where it is.
3. After the first repetition, K / 2 lists remain, each with a size of 2 * N. In the second duplication, K / 4 linked lists remain, and so on.
4. Repeat this process until you have only one linked list left.

5. Valid Parentheses

For a set of parentheses to be valid, they have to be closed in the reverse order in which they have been opened. In other words, the most recently opened bracket has to be closed first. The Last In First Out property of a stack is well suited to handle this.

Steps

1. Use a stack to store characters.
2. Traverse the given string expression.
3. If the current character is an opening bracket, then push it into the stack.
4. If the current character is a closing bracket, compare it to the character at the top of the stack by popping from the stack. If they are a pair of opening and closing brackets of the same kind, the brackets are valid and we continue. If not, they are invalid, we can stop at this point and return false.
5. After the traversal, if there is an opening bracket left in the stack, then the parentheses are not valid.

6. Search a 2D Matrix

Steps

Binary Search is the optimal solution for this problem as we have a sorted matrix. You can perform Binary Search at the middle column of the sorted matrix. If the search element is less than the middle element of the middle column, then you can eliminate all the rows following that element. The vice versa can be done if the search element is greater than the middle element, which makes searching easier.

1. Perform binary search on the middle column of the matrix. If at any iteration, the search element is equal to the middle column element being compared, the search is successful. Else, continue binary search until only two rows are remaining.
2. Compare the search element with the middle elements of the two remaining rows. Now, there are four cases that may arise

• If the search element is equal to either of the middle elements, the search is successful.
• If the search element is lesser than both the middle elements, perform binary search on the first half of the first row.
• If the search element is between the middle elements, perform binary search first on the second half of the first row, and if the search element is not found, perform binary search on the first half of the second row.
• If the search element is greater than both the middle elements, perform binary search on the second half of the second row.

3. If the search element is still not found, label the search as unsuccessful.

4. Use a nested loop. An outer loop for the row and an inner loop for the column.

7. Number of Islands

Steps

There are 3 islands in this matrix

Since two pieces of land are connected only if they are vertically or horizontally adjacent to each other, the matrix can be treated as an undirected graph, with an edge between two horizontally or vertically adjacent nodes of value 1.

Because all the nodes in an island are connected, a graph search algorithm can be used to visit all the nodes of an island by starting at any island node. Any graph search algorithm such as Depth First Search or Breadth First Search can be used to solve this problem.

Here Depth First Search is used as the graph search algorithm.

1. Treat the 2D matrix as an undirected graph with an edge between two horizontally or vertically adjacent nodes of value 1.
2. Linear scan the 2D matrix.
3. Depth-first search is initiated upon finding an unvisited node 1. This node is taken as the root node.
4. During DFS, set every visited node as 0, to account for visited nodes.
5. The number of root nodes that trigger DFS would be the number of islands.

8. Merge Intervals

Steps

If you have a sorted list of intervals (sorted by their start time), with the first i intervals non overlapping, then the (i + 1)th interval can only overlap with the ith interval. Hence, if you push the first i intervals into a stack, then only the interval at the top of the stack is required for further comparison.

1. Sort the given intervals in increasing order of their starting time.
2. Create an empty stack and start traversing the list of intervals.
3. For each interval,

• Push the current interval into the stack only if the stack is empty or the top interval in the stack does not overlap with it.
• If the current interval overlaps with the top interval of the stack, that is, the starting time of the current interval is less than the ending time of the stack top interval, update the ending time of the stack top interval as the ending time of the current interval.

4. The stack now contains the list of merged intervals none of which overlap.

9. Minimize Cash Flow

Steps

1. Calculate the total amount of each person as -

Net amount at person i = Sum of all money i receives - Sum of all money i pays

2. Find two persons with the maximum and minimum net amount. Let the person with the maximum net amount be maxReceiver and the person with the minimum net amount be maxPayer.
3. Find the absolute minimum of maxReceiver and maxPayer. Let this amount be payment ‘x’.
4. maxPayer will pay ‘x’ to maxReceiver. X will be added to maxPayer’s net amount and subtracted from maxReceiver’s net amount.
5. Repeat steps 2 to 4 until all the net amounts become zero.

10. LRU Cache

Steps

Least Recently Used (LRU) is a common caching strategy. It implements a policy to evict elements from the cache. When the cache is full and new elements need to be added, it evicts the least recently used items first.

Also read,

Cache Memory Explained for Developers

Everything you need to know about cached data, cache memory, cache vs cookies, uses and importance of cache.

Crio BlogKevin Paulose

Take an example of a cache that has a capacity of 4 . The elements 1, 2, 3, 4 are cached with 1 being the first element to be cached and 4 the last element.

The cache state after first access of all four elements

1 2 3 4

Say you need to cache a new element 5.

In LRU cache, the least recently used element should be evicted in case a new element needs to be added.

So, 1 is removed and 5 is added to the cache. Now the cache has the elements

2, 3, 4, 5

.

A cache has to be able to access and retrieve the data in constant time. This can be achieved using the following data structures

Queue (representing the cache) - The maximum size of the queue will be equal to the cache size . The most recently used elements will be near the front end and the least recent elements will be near the rear end. A doubly linked list is used to implement this queue over a singly linked list because a doubly linked list can delete a node given its address, in constant time whereas a singly linked list achieves this in linear time.

Hashmap - Use a hashmap to access the node address of the doubly linked list which corresponds to a particular element in constant time.The hashmap will contain the element as key and address of the corresponding node as value.

1. When an element is referenced, try to lookup the cache by using the corresponding node address from the hash. The required element may be in the cache. If it is in the cache,  detach the particular node from the list and attach it to the front of the queue.
2. If the required element is not in cache, attach a new node to the front of the queue and write the corresponding node address in the hash.
3. If the queue is full, delete a node from the rear of the queue, and add the new node to the front of the queue. Update the hash.

Conclusion

Hope this blog helped you learn to apply different data structures and algorithms using the problem statements asked in interviews. Only some of the frequently asked questions were picked for this blog. But there are many more such problems you can find and practice. Crio’s DSA packs are a great place to start and master all the data structures and algorithms.

Why do you need knowledge of data structures and algorithms?

Data structures and Algorithms are techniques used to write efficient code for a given problem, much like how you need music theory to master an instrument. To be a good programmer you need to learn to use the right data structure and algorithm for a given problem.

Say, you need to travel to a particular spot in your city. You take a car to travel to the spot but later discover that taking the metro would have been faster and cheaper. Similarly, insufficient knowledge in DSA can lead you to write inefficient code.

In interviews, an interviewer will test you on the basis of how quickly you come up with the solution, how efficient your code is, and they can go on to ask you in-depth questions about the data structure or algorithm you’ve used to solve the problem.

The popular opinion for mastering Data Structures and Algorithms is to solve hundreds of problems. But it is actually more valuable to focus on a handful of problems and get a thorough understanding of each data structure and algorithm and how to apply them.

10 Best Sorting Algorithms You Must Know About

What is the fastest sorting algorithm? Which one is the simplest sorting algorithm? Why do we even use sorting algorithms? Get all your answers.

Crio BlogSandipan Das

Once you take this approach to learning, you will find that you can segregate problems into different types and each of these will have the same approach and algorithm that can be used.

This blog will introduce you to frequently asked DSA interview questions in some of the top IT companies in the world.

List of Questions

1. Trapping Rainwater
2. Rat in a Maze
3. House Robber
4. Merge K sorted linked lists
5. Valid Parentheses
6. Search a 2D Matrix
7. Number of Islands
8. Merge Intervals
9. Minimize Cash Flow
10. LRU Cache

1. Trapping Rainwater

Steps

Rainwater can be trapped if there are bars of higher elevations to its left and right. The amount of water that can be trapped is the difference between the minimum of the two higher elevations to the left and right and the elevation in the current bar.

Here, two-pointer approach is used which uses two different pointers, one moving from the left to the right, and another from the right to the left of the elevation map.

1. Start with the left pointer on the leftmost bar, i.e, initialize left pointer to index 0, and the right pointer on the rightmost bar i.e., initialize right pointer to index n-1. Set the amount of water stored to be 0.
2. Create two variables maxLeft and maxRight to keep track of the highest elevations encountered by the left and right pointer respectively. Initalize maxLeft and maxRight as 0.
3. Traverse the array with these two pointers until they cross each other i,e., While left pointer <= right pointer

a. Find the highest bars on the left and right sides by performing the following comparisons.

• If the elevation at left pointer is greater than maxLeft, update maxLeft.
• If the elevation at right pointer is greater than maxRight, update maxRight.

b. There will be two cases at each iteration.

• If maxLeft <= maxRight

Increment the water stored by the difference between maxLeft and the elevation at the left pointer bar.

Increment the left pointer by 1.

• If maxLeft > maxRight

Increment the water stored by the difference between maxRight and the elevation at the right pointer bar.

Decrement the right pointer by 1.

4. Display the water stored, which is the required result.

2. Rat in a Maze

Steps

Two paths exist for the rat to travel to the destination (3,3)

We will use the principle of backtracking to find all valid paths.

1. Create a path matrix of N*N dimensions to keep track of the path that the rat will take. This matrix will be used to store the path that the rat takes by marking the cells it has visited with 1s and the unvisited cells with 0s.
2. Start the traversal of the input matrix that represents the maze starting from the rat’s initial position (0,0). The rat can traverse in 4 possible ways - either down, up, right, or left. Keep track of the visited cells by marking them as visited in the path matrix.
3. If the position  (x,y) is out of the matrix, or if it is blocked (0) backtrack to the previous step taken.

Else,

• Mark (x,y) as visited in the path matrix
• If (x,y) is the destination cell,
• Then
• Print the path taken as a solution (using the path matrix) and backtrack to the previous step

Else

• Move from (x,y) to (x+1,y) (right), (x-1,y) (left), (x,y+1) (down) (x,y-1) (up), one at a time, and repeat step 4 recursively from each of these positions.
• If these don’t lead to the destination cell, unmark (x,y) as visited in the path matrix and backtrack to the previous step.

3. House Robber

Steps

1. There can be no houses so the robber can't steal any money. There can be just one house, in which case the robber steals money from that house. If there are two or more houses, the robber will try to steal the maximum amount of money without stealing from any two adjacent houses.
2. Use an array called dp[ ] with the size equal to the number of houses. Each element of this array will indicate the maximum amount of money that can be stolen from the ith house (index of that element) to the last house.

To find out the maximum money that can be stolen you need to consider every possible combination of houses from the ith house to the last house. However, this will result in repeatedly calculating certain sub-problems. By storing the result of these subproblems (the maximum money that can be stolen from ith house to the last house) in the dp array, you can optimise the solution. This is the principle of Dynamic Programming.

3. The robber can steal money in two ways as he moves from the first house to the last

a. He can rob from the current house (i) and skip the next house ( go to the house at i + 2), and from there find the maximum money that can be stolen amongst all the houses that are remaining.

So the robber steals the money from the current house + the maximum money that can be stolen from house i+2 onwards.

b. He can skip the current house and move to the next house (at i + 1) and repeat step 3. So, the robber steals the maximum amount that can be stolen from house i + 1 onwards.

4. Now, find the maximum of the values calculated at steps a and b and update the dp array to this value.

Note: If the maximum money that can be stolen at a house i has already been calculated and stored in dp[i], the value is directly used.

4. Merge K Sorted Linked Lists

Steps

1. Pair the K linked lists into groups of 2 and combine each pair in a sorted way with linear time complexity.
2. A pair of linked lists can be combined by using 2 pointers, each pointer traversing one linked list. Both pointers start at the head node of their respective list and traverse through the nodes till the end. At each step, compare the value at the two nodes and pick the smallest of the nodes. Increment that smaller node pointer while the other pointer stays where it is.
3. After the first repetition, K / 2 lists remain, each with a size of 2 * N. In the second duplication, K / 4 linked lists remain, and so on.
4. Repeat this process until you have only one linked list left.

5. Valid Parentheses

For a set of parentheses to be valid, they have to be closed in the reverse order in which they have been opened. In other words, the most recently opened bracket has to be closed first. The Last In First Out property of a stack is well suited to handle this.

Steps

1. Use a stack to store characters.
2. Traverse the given string expression.
3. If the current character is an opening bracket, then push it into the stack.
4. If the current character is a closing bracket, compare it to the character at the top of the stack by popping from the stack. If they are a pair of opening and closing brackets of the same kind, the brackets are valid and we continue. If not, they are invalid, we can stop at this point and return false.
5. After the traversal, if there is an opening bracket left in the stack, then the parentheses are not valid.

6. Search a 2D Matrix

Steps

Binary Search is the optimal solution for this problem as we have a sorted matrix. You can perform Binary Search at the middle column of the sorted matrix. If the search element is less than the middle element of the middle column, then you can eliminate all the rows following that element. The vice versa can be done if the search element is greater than the middle element, which makes searching easier.

1. Perform binary search on the middle column of the matrix. If at any iteration, the search element is equal to the middle column element being compared, the search is successful. Else, continue binary search until only two rows are remaining.
2. Compare the search element with the middle elements of the two remaining rows. Now, there are four cases that may arise

• If the search element is equal to either of the middle elements, the search is successful.
• If the search element is lesser than both the middle elements, perform binary search on the first half of the first row.
• If the search element is between the middle elements, perform binary search first on the second half of the first row, and if the search element is not found, perform binary search on the first half of the second row.
• If the search element is greater than both the middle elements, perform binary search on the second half of the second row.

3. If the search element is still not found, label the search as unsuccessful.

4. Use a nested loop. An outer loop for the row and an inner loop for the column.

7. Number of Islands

Steps

There are 3 islands in this matrix

Since two pieces of land are connected only if they are vertically or horizontally adjacent to each other, the matrix can be treated as an undirected graph, with an edge between two horizontally or vertically adjacent nodes of value 1.

Because all the nodes in an island are connected, a graph search algorithm can be used to visit all the nodes of an island by starting at any island node. Any graph search algorithm such as Depth First Search or Breadth First Search can be used to solve this problem.

Here Depth First Search is used as the graph search algorithm.

1. Treat the 2D matrix as an undirected graph with an edge between two horizontally or vertically adjacent nodes of value 1.
2. Linear scan the 2D matrix.
3. Depth-first search is initiated upon finding an unvisited node 1. This node is taken as the root node.
4. During DFS, set every visited node as 0, to account for visited nodes.
5. The number of root nodes that trigger DFS would be the number of islands.

8. Merge Intervals

Steps

If you have a sorted list of intervals (sorted by their start time), with the first i intervals non overlapping, then the (i + 1)th interval can only overlap with the ith interval. Hence, if you push the first i intervals into a stack, then only the interval at the top of the stack is required for further comparison.

1. Sort the given intervals in increasing order of their starting time.
2. Create an empty stack and start traversing the list of intervals.
3. For each interval,

• Push the current interval into the stack only if the stack is empty or the top interval in the stack does not overlap with it.
• If the current interval overlaps with the top interval of the stack, that is, the starting time of the current interval is less than the ending time of the stack top interval, update the ending time of the stack top interval as the ending time of the current interval.

4. The stack now contains the list of merged intervals none of which overlap.

9. Minimize Cash Flow

Steps

1. Calculate the total amount of each person as -

Net amount at person i = Sum of all money i receives - Sum of all money i pays

2. Find two persons with the maximum and minimum net amount. Let the person with the maximum net amount be maxReceiver and the person with the minimum net amount be maxPayer.
3. Find the absolute minimum of maxReceiver and maxPayer. Let this amount be payment ‘x’.
4. maxPayer will pay ‘x’ to maxReceiver. X will be added to maxPayer’s net amount and subtracted from maxReceiver’s net amount.
5. Repeat steps 2 to 4 until all the net amounts become zero.

10. LRU Cache

Steps

Least Recently Used (LRU) is a common caching strategy. It implements a policy to evict elements from the cache. When the cache is full and new elements need to be added, it evicts the least recently used items first.

Also read,

Cache Memory Explained for Developers

Everything you need to know about cached data, cache memory, cache vs cookies, uses and importance of cache.

Crio BlogKevin Paulose

Take an example of a cache that has a capacity of 4 . The elements 1, 2, 3, 4 are cached with 1 being the first element to be cached and 4 the last element.

The cache state after first access of all four elements

1 2 3 4

Say you need to cache a new element 5.

In LRU cache, the least recently used element should be evicted in case a new element needs to be added.

So, 1 is removed and 5 is added to the cache. Now the cache has the elements

2, 3, 4, 5

.

A cache has to be able to access and retrieve the data in constant time. This can be achieved using the following data structures

Queue (representing the cache) - The maximum size of the queue will be equal to the cache size . The most recently used elements will be near the front end and the least recent elements will be near the rear end. A doubly linked list is used to implement this queue over a singly linked list because a doubly linked list can delete a node given its address, in constant time whereas a singly linked list achieves this in linear time.

Hashmap - Use a hashmap to access the node address of the doubly linked list which corresponds to a particular element in constant time.The hashmap will contain the element as key and address of the corresponding node as value.

1. When an element is referenced, try to lookup the cache by using the corresponding node address from the hash. The required element may be in the cache. If it is in the cache,  detach the particular node from the list and attach it to the front of the queue.
2. If the required element is not in cache, attach a new node to the front of the queue and write the corresponding node address in the hash.
3. If the queue is full, delete a node from the rear of the queue, and add the new node to the front of the queue. Update the hash.

Conclusion

Hope this blog helped you learn to apply different data structures and algorithms using the problem statements asked in interviews. Only some of the frequently asked questions were picked for this blog. But there are many more such problems you can find and practice. Crio’s DSA packs are a great place to start and master all the data structures and algorithms.

Most programmers often feel the need to sort the data provided to them. Sorted data is easier to understand and process.

As resources become increasingly limited and time more valuable, the most efficient sorting mechanism must be implemented based on the characteristics of the data provided.

Various types of sorting mechanisms include:

1. Quick Sort
2. Bubble Sort
3. Merge Sort
4. Insertion Sort
5. Selection Sort
6. Heap Sort.
7. Radix Sort
8. Bucket Sort

This blog covers the fundamentals to get you started with insertion sort. Before moving forward, make sure you have gone through the earlier blog on 10 best sorting algorithms to easily grasp the following sections.

Why insertion sort?

Before diving into the technical details of insertion sort, consider this example:

You and your pet dog (let’s call him Fluffy) are participating in a competition.
To win, Fluffy must run to a basket, pick a bone and give it to you, while you need to arrange them in increasing order of length, all of it as quickly as possible.
Suppose Fluffy takes 60 seconds to bring a bone, and you need 10 seconds to sort it into its proper position. One approach would be to wait for Fluffy to stack all the bones near you and then sort them.

For 10 bones, this approach takes (60+10)*10 = 700 seconds.

Another possible approach would be to sort each bone as it comes into its proper position. This approach takes 60*10 = 600 seconds. That is 1 min 40 sec lesser! Yay!

Insertion sort does the same. It places a new bone in its proper position in an already sorted array (or subarray, as we will see further).

Now replace the dog, bone, and yourself with a hard drive, data, and a CPU. While transferring data from a slow hard drive to a CPU, data transfer may take more time than data processing at the CPU. Hence, to avoid wastage of CPU cycles, it is good to keep sorting data alongside and add new data to the sorted data.

Now let us study the process of insertion sort in detail.

What is insertion sort?

Insertion sort is a sorting method that works by shifting each element in the array one at a time. It iterates through the input elements, expanding the sorted array each time by comparing the current element to the sorted array's greatest value.

If the current element is greater, it remains in place and continues to the next element; otherwise, it locates the element's appropriate location in the sorted array and transfers it there.

Finally, it moves any elements in the sorted array that are greater than the current element one place forward.

Try it yourself

Insertion sort strongly resembles how we sort playing cards. To understand how, simply pick every subsequent card from a deck and place it in its proper position by comparing its value.

Another real-world example of insertion sort is how tailors arrange shirts in a closet. They always keep them in sorted order of size so that they can insert new shirts into the proper spot very quickly by shifting existing shirts forward to make room for the new shirt.

Insertion sort algorithm

Step 1: The first element is assumed to be already sorted

Step 2: Select the next element.

Step 3: Compare all elements in the sorted sublist with the element to be sorted.

Step 4: Shift all elements in the sorted sub-list that are greater than the value to be sorted.

Step 5: Fill in the value.

Step 6: Continue until the list is sorted.

Insertion sort pseudocode

Assume that the first element is already sorted, and begin the iteration from index = 1 (in a zero-based array).

This algorithm can also be implemented recursively, such that the function calls itself, as follows:

Now that you know the algorithm and the pseudocode, try implementing insertion sort on your own. You may take help from the code snippets provided. Feel free to reach out to us in the comments below in case you get stuck.

Insertion sort in C

Insertion sort in C++

Insertion sort in Java

Insertion sort in Python3

Time complexity analysis of insertion sort

The best case input to an insertion sort function is an array sorted in the required order (here, ascending). In such cases, the algorithm simply compares the values of the ith element and the sorted subarray. Thus we get a linear time complexity, i.e., O(n).

The worst-case input is an array sorted in the opposite order (here, descending). In such cases, the algorithm compares the ith elements to every value in the sorted subarray and shifts every element of the subarray one position forward, thus resulting in quadratic time complexity, i.e., O(n2).

The average case complexity of insertion sort is also quadratic. Hence insertion sort is not preferred for large data sets. However, insertion sort is the fastest algorithm for sorting small arrays. Note that while there is no concrete threshold value to define small and large arrays, it may lie anywhere between 10 to 50 elements.

Space complexity analysis of insertion sort

Space complexity is the same for all cases, i.e., O(1). Hence, no auxiliary memory is required.

Comparison of insertion sort with other sorting algorithms

Insertion sort is similar to selection sort; the primary difference is that the ith iteration in insertion sort gives the sorted subarray from the i elements input to it, whereas, in selection sort, the ith iteration gives the i smallest elements in the entire array.

Although bubble sort has the same time complexity, i.e., O(n2), it is far less efficient than both insertion and selection sort. While some divide-and-conquer algorithms, such as Quick Sort and Merge Sort, outperform insertion sort for larger arrays, non-recursive sorting methods such as insertion sort or selection sort are often quicker for small arrays.

Enhancements on insertion sort

Method 1:

Algorithm:

1. Just compare the ith element with (i-1)th element.
2. If ith > (i-1)th, then simply append the element to the list. Else
3. Compare ith element with ptr (i.e., the first element that is smallest in the current sorted list). We know that A[0] to A[i-1] is already sorted, and ptr points to A[0].
4. If ith < ptr, then insert the ith element before ptr and point ptr to this element. Swap the remaining list accordingly. Else
5. If the element lies between the 1st and the (i-1)th element, then we further divide the total number of sorted elements by 2 i.e. k = ceil(i/2).
6. Now compare the ith element with the kth element and check again.
7. If ith < kth, then continue comparing with smaller elements until we find an element kth < ith. Compare ith element with (k+1)th and swap.
8. If ith > kth then continue comparing with greater elements until we find an element kth > ith. Compare ith element with (k-1)th and swap.

Using this method, the average and worst-case complexity can be reduced to O(n^1.585) from O(n^2) as the number of comparisons reduces significantly.

Method 2:

Algorithm:

1. Start with the first and last elements of the array i.e. A[0] and A[n-1] where n is the length of the array.
2. Compare A[0] and A[n-1]. If A[0]>A[n-1], swap their values. Else continue.
3. Compare A[1] and A[n-2] and swap if A[1] > A[n-2].
4. Repeat this process until the two middle elements are processed or only one middle element remains.
5. Execute standard insertion sort on this array.

This algorithm makes insertion sort more practical for larger list sizes by significantly reducing the number of comparisons.

Congratulations! You have mastered insertion sort for your next big interview! If you haven’t already, try implementing insertion sort yourself. Trust us! It is worth the effort :)

Sorting algorithms may seem dreary or complex at first glance. If this is the case with you, don’t worry, we’ve got your back! Check out our simple yet comprehensive summary of the Top 10 Sorting Algorithms.

Happy Coding!

Most programmers often feel the need to sort the data provided to them. Sorted data is easier to understand and process.

As resources become increasingly limited and time more valuable, the most efficient sorting mechanism must be implemented based on the characteristics of the data provided.

Various types of sorting mechanisms include:

1. Quick Sort
2. Bubble Sort
3. Merge Sort
4. Insertion Sort
5. Selection Sort
6. Heap Sort.
7. Radix Sort
8. Bucket Sort

This blog covers the fundamentals to get you started with insertion sort. Before moving forward, make sure you have gone through the earlier blog on 10 best sorting algorithms to easily grasp the following sections.

Why insertion sort?

Before diving into the technical details of insertion sort, consider this example:

You and your pet dog (let’s call him Fluffy) are participating in a competition.
To win, Fluffy must run to a basket, pick a bone and give it to you, while you need to arrange them in increasing order of length, all of it as quickly as possible.
Suppose Fluffy takes 60 seconds to bring a bone, and you need 10 seconds to sort it into its proper position. One approach would be to wait for Fluffy to stack all the bones near you and then sort them.

For 10 bones, this approach takes (60+10)*10 = 700 seconds.

Another possible approach would be to sort each bone as it comes into its proper position. This approach takes 60*10 = 600 seconds. That is 1 min 40 sec lesser! Yay!

Insertion sort does the same. It places a new bone in its proper position in an already sorted array (or subarray, as we will see further).

Now replace the dog, bone, and yourself with a hard drive, data, and a CPU. While transferring data from a slow hard drive to a CPU, data transfer may take more time than data processing at the CPU. Hence, to avoid wastage of CPU cycles, it is good to keep sorting data alongside and add new data to the sorted data.

Now let us study the process of insertion sort in detail.

What is insertion sort?

Insertion sort is a sorting method that works by shifting each element in the array one at a time. It iterates through the input elements, expanding the sorted array each time by comparing the current element to the sorted array's greatest value.

If the current element is greater, it remains in place and continues to the next element; otherwise, it locates the element's appropriate location in the sorted array and transfers it there.

Finally, it moves any elements in the sorted array that are greater than the current element one place forward.

Try it yourself

Insertion sort strongly resembles how we sort playing cards. To understand how, simply pick every subsequent card from a deck and place it in its proper position by comparing its value.

Another real-world example of insertion sort is how tailors arrange shirts in a closet. They always keep them in sorted order of size so that they can insert new shirts into the proper spot very quickly by shifting existing shirts forward to make room for the new shirt.

Insertion sort algorithm

Step 1: The first element is assumed to be already sorted

Step 2: Select the next element.

Step 3: Compare all elements in the sorted sublist with the element to be sorted.

Step 4: Shift all elements in the sorted sub-list that are greater than the value to be sorted.

Step 5: Fill in the value.

Step 6: Continue until the list is sorted.

Insertion sort pseudocode

Assume that the first element is already sorted, and begin the iteration from index = 1 (in a zero-based array).

This algorithm can also be implemented recursively, such that the function calls itself, as follows:

Now that you know the algorithm and the pseudocode, try implementing insertion sort on your own. You may take help from the code snippets provided. Feel free to reach out to us in the comments below in case you get stuck.

Insertion sort in C

Insertion sort in C++

Insertion sort in Java

Insertion sort in Python3

Time complexity analysis of insertion sort

The best case input to an insertion sort function is an array sorted in the required order (here, ascending). In such cases, the algorithm simply compares the values of the ith element and the sorted subarray. Thus we get a linear time complexity, i.e., O(n).

The worst-case input is an array sorted in the opposite order (here, descending). In such cases, the algorithm compares the ith elements to every value in the sorted subarray and shifts every element of the subarray one position forward, thus resulting in quadratic time complexity, i.e., O(n2).

The average case complexity of insertion sort is also quadratic. Hence insertion sort is not preferred for large data sets. However, insertion sort is the fastest algorithm for sorting small arrays. Note that while there is no concrete threshold value to define small and large arrays, it may lie anywhere between 10 to 50 elements.

Space complexity analysis of insertion sort

Space complexity is the same for all cases, i.e., O(1). Hence, no auxiliary memory is required.

Comparison of insertion sort with other sorting algorithms

Insertion sort is similar to selection sort; the primary difference is that the ith iteration in insertion sort gives the sorted subarray from the i elements input to it, whereas, in selection sort, the ith iteration gives the i smallest elements in the entire array.

Although bubble sort has the same time complexity, i.e., O(n2), it is far less efficient than both insertion and selection sort. While some divide-and-conquer algorithms, such as Quick Sort and Merge Sort, outperform insertion sort for larger arrays, non-recursive sorting methods such as insertion sort or selection sort are often quicker for small arrays.

Enhancements on insertion sort

Method 1:

Algorithm:

1. Just compare the ith element with (i-1)th element.
2. If ith > (i-1)th, then simply append the element to the list. Else
3. Compare ith element with ptr (i.e., the first element that is smallest in the current sorted list). We know that A[0] to A[i-1] is already sorted, and ptr points to A[0].
4. If ith < ptr, then insert the ith element before ptr and point ptr to this element. Swap the remaining list accordingly. Else
5. If the element lies between the 1st and the (i-1)th element, then we further divide the total number of sorted elements by 2 i.e. k = ceil(i/2).
6. Now compare the ith element with the kth element and check again.
7. If ith < kth, then continue comparing with smaller elements until we find an element kth < ith. Compare ith element with (k+1)th and swap.
8. If ith > kth then continue comparing with greater elements until we find an element kth > ith. Compare ith element with (k-1)th and swap.

Using this method, the average and worst-case complexity can be reduced to O(n^1.585) from O(n^2) as the number of comparisons reduces significantly.

Method 2:

Algorithm:

1. Start with the first and last elements of the array i.e. A[0] and A[n-1] where n is the length of the array.
2. Compare A[0] and A[n-1]. If A[0]>A[n-1], swap their values. Else continue.
3. Compare A[1] and A[n-2] and swap if A[1] > A[n-2].
4. Repeat this process until the two middle elements are processed or only one middle element remains.
5. Execute standard insertion sort on this array.

This algorithm makes insertion sort more practical for larger list sizes by significantly reducing the number of comparisons.

Congratulations! You have mastered insertion sort for your next big interview! If you haven’t already, try implementing insertion sort yourself. Trust us! It is worth the effort :)

Sorting algorithms may seem dreary or complex at first glance. If this is the case with you, don’t worry, we’ve got your back! Check out our simple yet comprehensive summary of the Top 10 Sorting Algorithms.

Happy Coding!

Time complexity is a programming term that quantifies the amount of time it takes a sequence of code or an algorithm to process or execute in proportion to the size and cost of input.

It will not look at an algorithm's overall execution time. Rather, it will provide data on the variation (increase or reduction) in execution time when the number of operations in an algorithm increases or decreases.

Yes, as the definition suggests, the amount of time it takes is solely determined by the number of iterations of one-line statements inside the code.

Take a look at this piece of code:

Although there are three separate statements inside the main() function, the overall time complexity is still O(1) because each statement only takes unit time to complete execution.

Whereas, observe this example:

Here, the O(1) chunk of code (the 3 cout statements) is enclosed inside a looping statement which repeats iteration for 'n' number of times. Thus our overall time complexity becomes n*O(1), i.e., O(n).

You could say that when an algorithm employs statements that are only executed once, the time required is constant. However, when the statement is in loop condition, the time required grows as the number of times the loop is set to run grows.

When an algorithm has a mix of single-executed statements and LOOP statements, or nested LOOP statements, the time required increases according to the number of times each statement is run.

For example, if a recursive function is called multiple times, identifying and recognizing the source of its time complexity may help reduce the overall processing time from 600 ms to 100 ms, for instance. That's what time complexity analysis aims to achieve.

Understanding various Time Complexity notations

The following are some of the most common asymptotic notations for calculating an algorithm's running time complexity;

• Ο Notation
• Ω Notation
• θ Notation

Before you dig in, don't miss to check out the top 10 sorting algorithms used

10 Best Sorting Algorithms You Must To Know About

What is the fastest sorting algorithm? Which one is the simplest sorting algorithm? Why do we even use sorting algorithms? Get all your answers.

Crio BlogSandipan Das

Big Oh Notation, Ο

The systematic way to express the upper limit of an algorithm's running time is to use the Big-O notation O(n). It calculates the worst-case time complexity, or the maximum time an algorithm will take to complete execution.

Also, do remember that this is the most commonly used notation for expressing the time complexity of different algorithms unless specified otherwise.

Definition:

Let g and f be functions that belong to the set of natural numbers (N). The function f is said to be O(g), if there is a constant c > 0 and a natural number n0 such that:

f (n) ≤ cg(n) for all n >= n0

Omega Notation, Ω

The systematic way to express the lower bound of an algorithm's running time is to use the notation Ω(n). It calculates the best-case time complexity, or the shortest time an algorithm will take to complete.

Definition:

Ω(g(n)) ={ f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0 }

The above expression can be defined as a function f(n) which belongs to the set Ω(g(n)) if and only if there exists a positive constant c (c > 0) such that it is greater than c*g(n) for a sufficiently large value of n.

The minimum time required by an algorithm to complete its execution is given by Ω(g(n)).

Theta Notation, Θ

The systematic way to express both the lower limit and upper bound of an algorithm's running time is to use the notation (n).

Definition:

Θ(g(n)) = {f(n): there exist certain positive constants x1, x2 and n0  such that 0 ≤ x1g(n) ≤ f(n) ≤ x2g(n) for all n ≥ n0}

Why should you learn about the time complexity of algorithms?

In computer programming, an algorithm is a finite set of well-defined instructions that are usually performed in a computer to solve a class of problems or perform a common operation.

According to the description, a sequence of specified instructions must be provided to the machine for it to execute an algorithm or perform a specific task. A particular series of instructions may be interpreted in any number of ways to perform the same purpose.

We have mentioned that the algorithm is to be run on a computer, which leads to the next step of varying the operating system, processor, hardware, and other factors that can affect how an algorithm is run.

Now that you know that a variety of variables will affect the outcome of an algorithm, it's important to know how effective those algorithms are at completing tasks. To determine this, you must assess an algorithm's Space and Time complexity.

An algorithm's space complexity quantifies how much space or memory it takes to run as a function of the length of the input while an algorithm's time complexity measures how long it takes an algorithm to run as a function of the length of the input.

That's why it's so important to learn about the time and space complexity analysis of various algorithms.

Let's explore each time complexity type with an example.

1. O(1)

Where an algorithm's execution time is not based on the input size n, it is said to have constant time complexity with order O (1).

Whatever be the input size n, the runtime doesn’t change. Here's an example:

As you can see, the message "Hello World!!" is printed only once. So, regardless of the operating system or computer configuration you are using, the time complexity is constant: O(1), i.e. any time a constant amount of time is required to execute code.

2. O(n)

When the running time of an algorithm increases linearly with the length of the input, it is assumed to have linear time complexity, i.e. when a function checks all of the values in an input data set (or needs to iterate once through every value in the input), it is said to have a Time complexity of order O (n). Consider the following scenario:

Output:

Based on the above code, you can see that the number of times the statement "Hello fellow Developer!!" is displayed on the console is directly dependent on the size of the input variable 'n'.

If one unit of time is used to represent run time, the above program can be run in n times the amount of time. As a result, the program scales linearly with the size of the input, and it has an order of O(n).

3. O(n^2)

When the running time of an algorithm increases non-linearly O(n^2) with the length of the input, it is said to have a non-linear time complexity.

In general, nested loops fall into the O(n)*O(n) = O(n^2) time complexity order, where one loop takes O(n) and if the function includes loops inside loops, it takes O(n)*O(n) = O(n^2).

Similarly, if the function has ‘m' loops inside the O(n) loop, the order is given by O (n*m), which is referred to as polynomial time complexity function.

Consider the following program:

Output:

As you can see, there are two nested for loops such that the inner loop's complete iteration repeats based on the value of the outer loop. This is the primary reason why you see "Hello dev!!" printed 6 times (3*2).

This amounts to the cumulative time complexity of O(m*n)  or O(n^2) if you assume that the value of m is equal to the value of n.

4. O(log2 n)

When an algorithm decreases the magnitude of the input data in each step, it is said to have a logarithmic time complexity. This means that the number of operations is not proportionate to the size of the input.

O (log2 n) basically implies that time increases linearly while the value of 'n' increases exponentially. So, if computing 10 elements take 1 second, computing 100 elements takes 2 seconds, 1000 elements take 3 seconds, and so on.

When using divide and conquer algorithms, such as binary search, the time complexity is O(log n).

Another example is quicksort, in which we partition the array into two sections and find a pivot element in O(n) time each time. As a result, it is O(log2 n)

Binary trees and binary search functions are examples of algorithms having logarithmic time complexity. Here, the search for a particular value in an array is done by separating the array into two parts and starting the search in one of them. This guarantees that the action isn't performed on every data element.

Consider the following code snippet:

The above program is a demonstration of the binary search technique, a famous divide-and-conquer approach to searching in logarithmic time complexity.

Time Complexity Analysis

Let us assume that we have an array of length 32. We'll be applying Binary Search to search for a random element in it. At each iteration, the array is halved.

• Iteration 0:
  • Length of array = 32
• Iteration 1:
  • Length of array = 32/2 = 16
• Iteration 2:
  • Length of array = 32/2^2 = 8
• Iteration 3:
  • Length of array = 32/2^3 = 4
• Iteration 4:
  • Length of array = 32/2^4 = 2
• Iteration 5:
  • Length of array = 32/2^5 = 1

Another example would be that for an array of size 1024, only 10 iterations are needed to approach unity. For an array size of 32768, we'll need only 15 iterations. Thus we can see that the number of operations grows at a very small rate compared to the size of the input array while complexity is logarithmic.

To generalize, after k iterations, our array size approaches 1.

Hence, n/2^k = 1 => n = 2^k

Applying logarithmic function on both sides, we get
=> log2 (n) = log2 (2^k) => log2 (n) = k log2 (2)
or, => k = log2 (n)
Hence, the time complexity of Binary Search becomes log2(n), or O(log n)

5. O (n log n)

This time complexity is popularly known as linearithmic time complexity. It performs slightly slower as compared to linear time complexity but is still significantly better than the quadratic algorithm.

Consider the program snippet given below:

The program above represents the merge sort algorithm.

Sorting arrays on separate computers take a significant time. Merge Sort algorithm is recursive and has a recurrence relation for time complexity as follows:

T(n) = 2T(n/2) + θ(n)

The Recurrence Tree approach or the Master approach can be used to solve the aforementioned recurrence relation.

It belongs to Master Method Case II, and the recurrence answer is O(n*logn). Since Merge Sort always partitions the array into two halves and merges the two halves in linear time, it has a time complexity of (n*logn) in all three circumstances (worst, average, and best).

Also, remember this, when it comes to sorting algorithms, O(n*logn) is probably the best time complexity we can achieve.

6. O(2^N)

An algorithm with exponential time complexity doubles in magnitude with each increment to the input data set. If you're familiar with other exponential growth patterns, this one works similarly. The time complexity begins with a modest level of difficulty and gradually increases till the end.

The Fibonacci series is a great way to demonstrate exponential time complexity. Given below is a code snippet that calculates and returns the nth Fibonacci number:

Time Complexity Analysis:

The recurrence relation for the above code snippet is:

T(n) = T(n-1) + T(n-2)

Using the recurrence tree method, you can easily deduce that this code does a lot of redundant calculations as shown below.

Thus the time complexity of the Fibonacci series becomes exponential owing to these repetitive calculations.

Let's take an example here to drive home the magnitude of this time complexity.

For n=3, it takes 8 operations to calculate the 8th Fibonacci number.

For n=4, it takes 16 operations

.

.

For n=10, it takes 1024 operations to reach the 10th Fibonacci number.

.

.

Now if we bump it up to 100 (n=100), we literally exceed billions and billions of calculations just to reach the 100th Fibonacci number.

That's scary right. That's why exponential time complexity is one of the worst time complexities out there.

Now that you've explored the major time complexities in algorithms and data structures, take a look at their graphical representation below: (Time vs Input Size)

Here's a simple comparison between different time complexities to help you understand the graph better:

O(1) < O(log2n) < O(n1/2) < O(n) < O(n logn) < O(n^2) < O(n^3) < . . . . < O(2^n) < O(3^n) < . . . .  < O(n^n)

Of course, a visual representation clarifies a lot of concepts particularly related to the efficiency of different time complexities.

The noticeable thing to observe is how inefficient exponential and quadratic time complexities are with increasing input data size.

On the other hand, linearithmic and linear time complexities perform almost in a similar fashion with increasing input size.

The astounding part is the performance of logarithmic time complexity which clearly supersedes most algorithmic time complexities (except O(1)) in terms of execution time and efficiency.

Top 5 Sorting Algorithms and their time complexities

10 Best Sorting Algorithms You Must To Know About

What is the fastest sorting algorithm? Which one is the simplest sorting algorithm? Why do we even use sorting algorithms? Get all your answers.

Crio BlogSandipan Das

HEY, seems like you just completed learning about one of the most important concepts in Data Structures and Algorithms, i.e, time complexity analysis. Hope you enjoyed this code-based approach to such an interesting topic.

With DSA it becomes important to identify the Time Complexity of a given piece of code in the long run.

You can always jumpstart with the knowledge here and put it into practice analyzing various code snippets to up your Time Complexity game.

Of course, it will take time, but the experience you'll gain out of that will be more potent than just skimming through this article. So, what are you waiting for? Go ahead and crunch out some awesome problems for yourself.

Any particular time complexity that we missed out on? Let us know in the comments below.

Also, if you learned something new at any point in this article, please spread the knowledge by sharing it with your friends or with someone who might need it.

HAPPY CODING!!

Time complexity is a programming term that quantifies the amount of time it takes a sequence of code or an algorithm to process or execute in proportion to the size and cost of input.

It will not look at an algorithm's overall execution time. Rather, it will provide data on the variation (increase or reduction) in execution time when the number of operations in an algorithm increases or decreases.

Yes, as the definition suggests, the amount of time it takes is solely determined by the number of iterations of one-line statements inside the code.

Take a look at this piece of code:

Although there are three separate statements inside the main() function, the overall time complexity is still O(1) because each statement only takes unit time to complete execution.

Whereas, observe this example:

Here, the O(1) chunk of code (the 3 cout statements) is enclosed inside a looping statement which repeats iteration for 'n' number of times. Thus our overall time complexity becomes n*O(1), i.e., O(n).

You could say that when an algorithm employs statements that are only executed once, the time required is constant. However, when the statement is in loop condition, the time required grows as the number of times the loop is set to run grows.

When an algorithm has a mix of single-executed statements and LOOP statements, or nested LOOP statements, the time required increases according to the number of times each statement is run.

For example, if a recursive function is called multiple times, identifying and recognizing the source of its time complexity may help reduce the overall processing time from 600 ms to 100 ms, for instance. That's what time complexity analysis aims to achieve.

Understanding various Time Complexity notations

The following are some of the most common asymptotic notations for calculating an algorithm's running time complexity;

• Ο Notation
• Ω Notation
• θ Notation

Before you dig in, don't miss to check out the top 10 sorting algorithms used

10 Best Sorting Algorithms You Must To Know About

What is the fastest sorting algorithm? Which one is the simplest sorting algorithm? Why do we even use sorting algorithms? Get all your answers.

Crio BlogSandipan Das

Big Oh Notation, Ο

The systematic way to express the upper limit of an algorithm's running time is to use the Big-O notation O(n). It calculates the worst-case time complexity, or the maximum time an algorithm will take to complete execution.

Also, do remember that this is the most commonly used notation for expressing the time complexity of different algorithms unless specified otherwise.

Definition:

Let g and f be functions that belong to the set of natural numbers (N). The function f is said to be O(g), if there is a constant c > 0 and a natural number n0 such that:

f (n) ≤ cg(n) for all n >= n0

Omega Notation, Ω

The systematic way to express the lower bound of an algorithm's running time is to use the notation Ω(n). It calculates the best-case time complexity, or the shortest time an algorithm will take to complete.

Definition:

Ω(g(n)) ={ f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n) for all n ≥ n0 }

The above expression can be defined as a function f(n) which belongs to the set Ω(g(n)) if and only if there exists a positive constant c (c > 0) such that it is greater than c*g(n) for a sufficiently large value of n.

The minimum time required by an algorithm to complete its execution is given by Ω(g(n)).

Theta Notation, Θ

The systematic way to express both the lower limit and upper bound of an algorithm's running time is to use the notation (n).

Definition:

Θ(g(n)) = {f(n): there exist certain positive constants x1, x2 and n0  such that 0 ≤ x1g(n) ≤ f(n) ≤ x2g(n) for all n ≥ n0}

Why should you learn about the time complexity of algorithms?

In computer programming, an algorithm is a finite set of well-defined instructions that are usually performed in a computer to solve a class of problems or perform a common operation.

According to the description, a sequence of specified instructions must be provided to the machine for it to execute an algorithm or perform a specific task. A particular series of instructions may be interpreted in any number of ways to perform the same purpose.

We have mentioned that the algorithm is to be run on a computer, which leads to the next step of varying the operating system, processor, hardware, and other factors that can affect how an algorithm is run.

Now that you know that a variety of variables will affect the outcome of an algorithm, it's important to know how effective those algorithms are at completing tasks. To determine this, you must assess an algorithm's Space and Time complexity.

An algorithm's space complexity quantifies how much space or memory it takes to run as a function of the length of the input while an algorithm's time complexity measures how long it takes an algorithm to run as a function of the length of the input.

That's why it's so important to learn about the time and space complexity analysis of various algorithms.

Let's explore each time complexity type with an example.

1. O(1)

Where an algorithm's execution time is not based on the input size n, it is said to have constant time complexity with order O (1).

Whatever be the input size n, the runtime doesn’t change. Here's an example:

As you can see, the message "Hello World!!" is printed only once. So, regardless of the operating system or computer configuration you are using, the time complexity is constant: O(1), i.e. any time a constant amount of time is required to execute code.

2. O(n)

When the running time of an algorithm increases linearly with the length of the input, it is assumed to have linear time complexity, i.e. when a function checks all of the values in an input data set (or needs to iterate once through every value in the input), it is said to have a Time complexity of order O (n). Consider the following scenario:

Output:

Based on the above code, you can see that the number of times the statement "Hello fellow Developer!!" is displayed on the console is directly dependent on the size of the input variable 'n'.

If one unit of time is used to represent run time, the above program can be run in n times the amount of time. As a result, the program scales linearly with the size of the input, and it has an order of O(n).

3. O(n^2)

When the running time of an algorithm increases non-linearly O(n^2) with the length of the input, it is said to have a non-linear time complexity.

In general, nested loops fall into the O(n)*O(n) = O(n^2) time complexity order, where one loop takes O(n) and if the function includes loops inside loops, it takes O(n)*O(n) = O(n^2).

Similarly, if the function has ‘m' loops inside the O(n) loop, the order is given by O (n*m), which is referred to as polynomial time complexity function.

Consider the following program:

Output:

As you can see, there are two nested for loops such that the inner loop's complete iteration repeats based on the value of the outer loop. This is the primary reason why you see "Hello dev!!" printed 6 times (3*2).

This amounts to the cumulative time complexity of O(m*n)  or O(n^2) if you assume that the value of m is equal to the value of n.

4. O(log2 n)

When an algorithm decreases the magnitude of the input data in each step, it is said to have a logarithmic time complexity. This means that the number of operations is not proportionate to the size of the input.

O (log2 n) basically implies that time increases linearly while the value of 'n' increases exponentially. So, if computing 10 elements take 1 second, computing 100 elements takes 2 seconds, 1000 elements take 3 seconds, and so on.

When using divide and conquer algorithms, such as binary search, the time complexity is O(log n).

Another example is quicksort, in which we partition the array into two sections and find a pivot element in O(n) time each time. As a result, it is O(log2 n)

Binary trees and binary search functions are examples of algorithms having logarithmic time complexity. Here, the search for a particular value in an array is done by separating the array into two parts and starting the search in one of them. This guarantees that the action isn't performed on every data element.

Consider the following code snippet:

The above program is a demonstration of the binary search technique, a famous divide-and-conquer approach to searching in logarithmic time complexity.

Time Complexity Analysis

Let us assume that we have an array of length 32. We'll be applying Binary Search to search for a random element in it. At each iteration, the array is halved.

• Iteration 0:
  • Length of array = 32
• Iteration 1:
  • Length of array = 32/2 = 16
• Iteration 2:
  • Length of array = 32/2^2 = 8
• Iteration 3:
  • Length of array = 32/2^3 = 4
• Iteration 4:
  • Length of array = 32/2^4 = 2
• Iteration 5:
  • Length of array = 32/2^5 = 1

Another example would be that for an array of size 1024, only 10 iterations are needed to approach unity. For an array size of 32768, we'll need only 15 iterations. Thus we can see that the number of operations grows at a very small rate compared to the size of the input array while complexity is logarithmic.

To generalize, after k iterations, our array size approaches 1.

Hence, n/2^k = 1 => n = 2^k

Applying logarithmic function on both sides, we get
=> log2 (n) = log2 (2^k) => log2 (n) = k log2 (2)
or, => k = log2 (n)
Hence, the time complexity of Binary Search becomes log2(n), or O(log n)

5. O (n log n)

This time complexity is popularly known as linearithmic time complexity. It performs slightly slower as compared to linear time complexity but is still significantly better than the quadratic algorithm.

Consider the program snippet given below:

The program above represents the merge sort algorithm.

Sorting arrays on separate computers take a significant time. Merge Sort algorithm is recursive and has a recurrence relation for time complexity as follows:

T(n) = 2T(n/2) + θ(n)

The Recurrence Tree approach or the Master approach can be used to solve the aforementioned recurrence relation.

It belongs to Master Method Case II, and the recurrence answer is O(n*logn). Since Merge Sort always partitions the array into two halves and merges the two halves in linear time, it has a time complexity of (n*logn) in all three circumstances (worst, average, and best).

Also, remember this, when it comes to sorting algorithms, O(n*logn) is probably the best time complexity we can achieve.

6. O(2^N)

An algorithm with exponential time complexity doubles in magnitude with each increment to the input data set. If you're familiar with other exponential growth patterns, this one works similarly. The time complexity begins with a modest level of difficulty and gradually increases till the end.

The Fibonacci series is a great way to demonstrate exponential time complexity. Given below is a code snippet that calculates and returns the nth Fibonacci number:

Time Complexity Analysis:

The recurrence relation for the above code snippet is:

T(n) = T(n-1) + T(n-2)

Using the recurrence tree method, you can easily deduce that this code does a lot of redundant calculations as shown below.

Thus the time complexity of the Fibonacci series becomes exponential owing to these repetitive calculations.

Let's take an example here to drive home the magnitude of this time complexity.

For n=3, it takes 8 operations to calculate the 8th Fibonacci number.

For n=4, it takes 16 operations

.

.

For n=10, it takes 1024 operations to reach the 10th Fibonacci number.

.

.

Now if we bump it up to 100 (n=100), we literally exceed billions and billions of calculations just to reach the 100th Fibonacci number.

That's scary right. That's why exponential time complexity is one of the worst time complexities out there.

Now that you've explored the major time complexities in algorithms and data structures, take a look at their graphical representation below: (Time vs Input Size)

Here's a simple comparison between different time complexities to help you understand the graph better:

O(1) < O(log2n) < O(n1/2) < O(n) < O(n logn) < O(n^2) < O(n^3) < . . . . < O(2^n) < O(3^n) < . . . .  < O(n^n)

Of course, a visual representation clarifies a lot of concepts particularly related to the efficiency of different time complexities.

The noticeable thing to observe is how inefficient exponential and quadratic time complexities are with increasing input data size.

On the other hand, linearithmic and linear time complexities perform almost in a similar fashion with increasing input size.

The astounding part is the performance of logarithmic time complexity which clearly supersedes most algorithmic time complexities (except O(1)) in terms of execution time and efficiency.

Top 5 Sorting Algorithms and their time complexities

10 Best Sorting Algorithms You Must To Know About

What is the fastest sorting algorithm? Which one is the simplest sorting algorithm? Why do we even use sorting algorithms? Get all your answers.

Crio BlogSandipan Das

HEY, seems like you just completed learning about one of the most important concepts in Data Structures and Algorithms, i.e, time complexity analysis. Hope you enjoyed this code-based approach to such an interesting topic.

With DSA it becomes important to identify the Time Complexity of a given piece of code in the long run.

You can always jumpstart with the knowledge here and put it into practice analyzing various code snippets to up your Time Complexity game.

Of course, it will take time, but the experience you'll gain out of that will be more potent than just skimming through this article. So, what are you waiting for? Go ahead and crunch out some awesome problems for yourself.

Any particular time complexity that we missed out on? Let us know in the comments below.

Also, if you learned something new at any point in this article, please spread the knowledge by sharing it with your friends or with someone who might need it.

HAPPY CODING!!

What is DSA?

DSA stands for Data Structures and Algorithms. It is also sometimes referred to as PSDS - Problem Solving Data Structures. DSA is applied in problem-solving and enables developers to learn to write efficient code. The quality of the code can be judged by how much memory and time it consumes. The lesser memory the code consumes and the faster it runs, the more efficient it is.

Why is DSA important?

A person equipped with strong DSA skills will have better and more efficient approaches to solving a problem than someone who is not aware of DSA concepts.

You might not apply DSA directly in your job, but DSA is the foundation of computer science. You will certainly be a better software engineer if you have mastered DSA. So it's advisable to slowly master it at the beginning of your IT career itself.

How do companies use DSA?

Companies use DSA in mainly two ways -

In both of these cases, you as a candidate are required to write code to solve a problem that uses DSA.

Websites like HackerRank, LeetCode, and CodeForces have large sets of problems ranging from easy, medium, and hard levels of difficulty. Anybody can sign up on these websites and solve problems by writing code in any of the major programming languages and hone their skills in PSDS.

A lot of companies also use these websites to set interview questions. These websites have powerful evaluation tools to check your program for different test cases and also to test your program for plagiarism.

1. Online Screening

Companies use DSA to filter candidates. A company could have as many as 500 applicants and they might need to shortlist 20 candidates. DSA coding assessments serve as an objective way to filter the candidates.

By doing this,

1. The company spends < 1-2 hors setting problems on HackerRank and get automated leaderboard performance results back from Hackerrank.
2. Candidates don’t spend more than 2 hours of their time going to the next stage of the interview.
   

Without doing this,

1. The company asks all the 500 applicants to build a project for 12 hours
2. The company has to build automatic assessments for this project which is 20+ hours of work for their engineers
3. Candidates who get rejected have wasted 12 hours of their precious time.
   

How are coding assessments fair?

1. The coding ability of the candidates is judged.
2. Depth of DSA knowledge is judged based on the difficulty level of the problems set.
   

But there are some disadvantages to this method of filtering candidates

1. Plagiarism

Anybody can take up the online test unless strict measures of proctoring are implemented.

2. Problem Difficulty

The difficulty of the problems is progressively raised with a larger number of candidates. This is because companies don’t want all candidates to have the same score; they need a stack rank.

Because of this, online coding assessments can become too hard, more than what is required for the job.

2. Personal interviews

Apart from coding ability & DSA knowledge, the personal interview rounds aim at assessing a few more skills of the candidate:

Problem-solving ability

They evaluate if you are able to ask the right questions, come up with multiple solutions, are able to cover all aspects of the problem, make the right trade-offs, etc.

Debugging ability

The interviewer will also assess you by checking if you are able to structurally debug the code when you face issues.

In other terms, during online assessments, companies usually look for the final output of the code you have written. Whereas during personal interviews, the interviewer is interested in understanding your approach to solving the problem.

Well-prepared interviewers don’t usually ask standard leetcode problems in this round. They will ask you more realistic problems to see how you approach them.

Even if very difficult problems are asked here, interviewers are more interested in knowing what approach you have taken to solve the problem than the final output alone.

How effective are these interviews?

DSA interviews do a very fair estimation of your

Debugging skills are particularly assessed during the personal interviews.

In Reality…

PSDS has turned into a filtering criterion that everyone prepares too much for. A lot of companies end up asking some of the most standard questions, and since these are standard, if you have prepared for the exact same question, you will be able to solve it.

The idea of assessing the candidate's cognitive, problem-solving and coding abilities gets lost in the process.

Practicing some important 400+ leetcode problems sometimes becomes sufficient to crack online screening rounds.

To overcome this, companies keep bumping up the difficulty level of the problems, so that they can differentiate between candidates who have prepared in advance by solving a large number of problems and the ones who have genuinely solved the problem then and there.

For this reason, the DSA interviews have become 5 times more difficult than what is necessary for you to become a good software developer.

How much DSA do you really need to study?

Conclusion

Practice and expansion of your knowledge in DSA are going to be key to cracking interviews.

Ensure a good chunk of your time for this before you start applying for companies.

Here's a 3 stage DSA preparation plan to get you started.

All the best! And Good Luck!

What is DSA?

DSA stands for Data Structures and Algorithms. It is also sometimes referred to as PSDS - Problem Solving Data Structures. DSA is applied in problem-solving and enables developers to learn to write efficient code. The quality of the code can be judged by how much memory and time it consumes. The lesser memory the code consumes and the faster it runs, the more efficient it is.

Why is DSA important?

A person equipped with strong DSA skills will have better and more efficient approaches to solving a problem than someone who is not aware of DSA concepts.

You might not apply DSA directly in your job, but DSA is the foundation of computer science. You will certainly be a better software engineer if you have mastered DSA. So it's advisable to slowly master it at the beginning of your IT career itself.

How do companies use DSA?

Companies use DSA in mainly two ways -

In both of these cases, you as a candidate are required to write code to solve a problem that uses DSA.

Websites like HackerRank, LeetCode, and CodeForces have large sets of problems ranging from easy, medium, and hard levels of difficulty. Anybody can sign up on these websites and solve problems by writing code in any of the major programming languages and hone their skills in PSDS.

A lot of companies also use these websites to set interview questions. These websites have powerful evaluation tools to check your program for different test cases and also to test your program for plagiarism.

1. Online Screening

Companies use DSA to filter candidates. A company could have as many as 500 applicants and they might need to shortlist 20 candidates. DSA coding assessments serve as an objective way to filter the candidates.

By doing this,

1. The company spends < 1-2 hors setting problems on HackerRank and get automated leaderboard performance results back from Hackerrank.
2. Candidates don’t spend more than 2 hours of their time going to the next stage of the interview.
   

Without doing this,

1. The company asks all the 500 applicants to build a project for 12 hours
2. The company has to build automatic assessments for this project which is 20+ hours of work for their engineers
3. Candidates who get rejected have wasted 12 hours of their precious time.
   

How are coding assessments fair?

1. The coding ability of the candidates is judged.
2. Depth of DSA knowledge is judged based on the difficulty level of the problems set.
   

But there are some disadvantages to this method of filtering candidates

1. Plagiarism

Anybody can take up the online test unless strict measures of proctoring are implemented.

2. Problem Difficulty

The difficulty of the problems is progressively raised with a larger number of candidates. This is because companies don’t want all candidates to have the same score; they need a stack rank.

Because of this, online coding assessments can become too hard, more than what is required for the job.

2. Personal interviews

Apart from coding ability & DSA knowledge, the personal interview rounds aim at assessing a few more skills of the candidate:

Problem-solving ability

They evaluate if you are able to ask the right questions, come up with multiple solutions, are able to cover all aspects of the problem, make the right trade-offs, etc.

Debugging ability

The interviewer will also assess you by checking if you are able to structurally debug the code when you face issues.

In other terms, during online assessments, companies usually look for the final output of the code you have written. Whereas during personal interviews, the interviewer is interested in understanding your approach to solving the problem.

Well-prepared interviewers don’t usually ask standard leetcode problems in this round. They will ask you more realistic problems to see how you approach them.

Even if very difficult problems are asked here, interviewers are more interested in knowing what approach you have taken to solve the problem than the final output alone.

How effective are these interviews?

DSA interviews do a very fair estimation of your

Debugging skills are particularly assessed during the personal interviews.

In Reality…

PSDS has turned into a filtering criterion that everyone prepares too much for. A lot of companies end up asking some of the most standard questions, and since these are standard, if you have prepared for the exact same question, you will be able to solve it.

The idea of assessing the candidate's cognitive, problem-solving and coding abilities gets lost in the process.

Practicing some important 400+ leetcode problems sometimes becomes sufficient to crack online screening rounds.

To overcome this, companies keep bumping up the difficulty level of the problems, so that they can differentiate between candidates who have prepared in advance by solving a large number of problems and the ones who have genuinely solved the problem then and there.

For this reason, the DSA interviews have become 5 times more difficult than what is necessary for you to become a good software developer.

How much DSA do you really need to study?

Conclusion

Practice and expansion of your knowledge in DSA are going to be key to cracking interviews.

Ensure a good chunk of your time for this before you start applying for companies.

Here's a 3 stage DSA preparation plan to get you started.

All the best! And Good Luck!

What do Hitler, Napoleon, and Julius Caesar have in common?

They have all won major battles using the simple yet effective method of divide and conquer.

Divide and conquer has always been a fantastic approach for solving complex problems. This also stands true for data retrieval.
Binary search, based on the principle of divide and conquer, is a widely used search algorithm.

Try it yourself

Consider that you want to look for the word ‘Search’ in the dictionary.

Intuitively, you would open the dictionary in the middle and see if the first letter of the page comes after or before the letter ‘S’.

Let’s say that the letter you arrived at is ‘N’. Since ‘S’ comes after ‘N’ in the alphabet, you would then ignore the first half of the dictionary and divide the second half into two parts.

Now, say that you arrived at the letter ‘T’.

This process continues until you intuitively take to linear searching through pages of the letter ‘S’ to find the word.

Now consider a much bigger dataset. Let us say you want to find your name in a register that contains the names of all people in the world. If you go linearly, this might take you hours or even days to find your name. However, the same can be accomplished by binary search in no more than 33 iterations.

Prerequisites to Binary Search

Binary search has three simple prerequisites:

1. Your dataset must be sorted
2. Your dataset must be sorted
3. Your dataset MUST be sorted

Okay, now that you have a sorted dataset, let’s begin searching!

What is binary search?

Binary search, also known as half-interval search, logarithmic search, or binary chop in computer science, is a search technique that locates a target value inside a sorted array. It does so by dividing the sorted array and focussing on only the “relevant” or “valuable” half and ignoring the rest.

Search Algorithm

1. The required element should be compared to the centre element.
2. We return the mid index if the required element is equal to the middle element.
3. Else If it is bigger than the mid element, it can only be found after the mid element in the right half subarray. As a result, we repeat the process for the right half.
4. Otherwise, repeat for the left half.

Try it yourself

Try implementing binary search in your preferred language using this algorithm. You may take help from the code snippets below. Feel free to reach out to us in the comments section if you find any bugs!

Code: C (Recursive implementation)

Output: Element is present at index 4

Code: C++ (Iterative Implementation)

Output: Element is present at index 4

Code: Python3 (Recursive implementation)

Output: Element is present at index 4

Code: Java (Iterative implementation)

Output: Element found at index 4

Time complexity analysis

While implementing binary search, the target element may be at three kinds of positions:

1. Middle of the array (Best case)
2. First or last element of the array (Worst case)
3. Anywhere except the cases above (Average case)

The Best case time complexity of the binary search algorithm is O(1).

The Average and Worst case time complexity is O(log2n).

This time complexity is significantly better than the linear search algorithm, whose average and worst-case time complexity is O(n).

Add finishing touches to your knowledge!

Since Binary search is a quick way for searching through sorted databases, it is often used in debugging. Suppose you have 100 versions of a code, each of which is different from the other. The 1st version displays the correct output, but the 100th version doesn’t.

An efficient way to find the broken version would be to run a binary search through all the versions. The versions are logged in a Version Control System in sorted order, so don’t worry about that. Check out the code in the 50th release, build it, and see if the bug is still there.

Continue dividing until you discover when the bug was introduced. This approach comes in quite handy especially if you make small commits.

Test your understanding

Q1. Given an input array = {5,9,11,15,21} and target element = 21. How many iterations are done until the element is found?

1. 5
2. 2
3. 3
4. 4

Q2. Given an array = {23, 41, 52, 68, 84, 91,102} and target element = 102. What are the mid values (corresponding array elements) generated in the first and second iterations?

1. 68 and 91
2. 68 and 102
3. 52 and 84
4. 52 and 91

Improvements on Binary Search algorithm:

Congrats! You have learned how to implement the binary search algorithm. But there is always room for improvement, right?

One possible way is to reduce the worst-case time complexity to O(1); you may check if the target element is equal to the first or last element of the array right in the beginning.

You discovered the wonders of Divide and Conquer and explored binary search in detail! So, the next time you are faced with looking through a large dataset, like a dictionary or your closet, look through its sections instead :)

Before you leave...

Binary search forms the basis of a Binary Search Tree.

If you want to learn about it in a similar article, drop a comment below and let us know your interest.

And if you enjoyed learning the fundamentals of binary search through this article, share the knowledge with your fellow programmers and your social circle. Maybe someone out there really needs this resource, and you might be helping them out by sharing it.

Happy Coding!

What do Hitler, Napoleon, and Julius Caesar have in common?

They have all won major battles using the simple yet effective method of divide and conquer.

Divide and conquer has always been a fantastic approach for solving complex problems. This also stands true for data retrieval.
Binary search, based on the principle of divide and conquer, is a widely used search algorithm.

Try it yourself

Consider that you want to look for the word ‘Search’ in the dictionary.

Intuitively, you would open the dictionary in the middle and see if the first letter of the page comes after or before the letter ‘S’.

Let’s say that the letter you arrived at is ‘N’. Since ‘S’ comes after ‘N’ in the alphabet, you would then ignore the first half of the dictionary and divide the second half into two parts.

Now, say that you arrived at the letter ‘T’.

This process continues until you intuitively take to linear searching through pages of the letter ‘S’ to find the word.

Now consider a much bigger dataset. Let us say you want to find your name in a register that contains the names of all people in the world. If you go linearly, this might take you hours or even days to find your name. However, the same can be accomplished by binary search in no more than 33 iterations.

Prerequisites to Binary Search

Binary search has three simple prerequisites:

1. Your dataset must be sorted
2. Your dataset must be sorted
3. Your dataset MUST be sorted

Okay, now that you have a sorted dataset, let’s begin searching!

What is binary search?

Binary search, also known as half-interval search, logarithmic search, or binary chop in computer science, is a search technique that locates a target value inside a sorted array. It does so by dividing the sorted array and focussing on only the “relevant” or “valuable” half and ignoring the rest.

Search Algorithm

1. The required element should be compared to the centre element.
2. We return the mid index if the required element is equal to the middle element.
3. Else If it is bigger than the mid element, it can only be found after the mid element in the right half subarray. As a result, we repeat the process for the right half.
4. Otherwise, repeat for the left half.

Try it yourself

Try implementing binary search in your preferred language using this algorithm. You may take help from the code snippets below. Feel free to reach out to us in the comments section if you find any bugs!

Code: C (Recursive implementation)

Output: Element is present at index 4

Code: C++ (Iterative Implementation)

Output: Element is present at index 4

Code: Python3 (Recursive implementation)

Output: Element is present at index 4

Code: Java (Iterative implementation)

Output: Element found at index 4

Time complexity analysis

While implementing binary search, the target element may be at three kinds of positions:

1. Middle of the array (Best case)
2. First or last element of the array (Worst case)
3. Anywhere except the cases above (Average case)

The Best case time complexity of the binary search algorithm is O(1).

The Average and Worst case time complexity is O(log2n).

This time complexity is significantly better than the linear search algorithm, whose average and worst-case time complexity is O(n).

Add finishing touches to your knowledge!

Since Binary search is a quick way for searching through sorted databases, it is often used in debugging. Suppose you have 100 versions of a code, each of which is different from the other. The 1st version displays the correct output, but the 100th version doesn’t.

An efficient way to find the broken version would be to run a binary search through all the versions. The versions are logged in a Version Control System in sorted order, so don’t worry about that. Check out the code in the 50th release, build it, and see if the bug is still there.

Continue dividing until you discover when the bug was introduced. This approach comes in quite handy especially if you make small commits.

Test your understanding

Q1. Given an input array = {5,9,11,15,21} and target element = 21. How many iterations are done until the element is found?

1. 5
2. 2
3. 3
4. 4

Q2. Given an array = {23, 41, 52, 68, 84, 91,102} and target element = 102. What are the mid values (corresponding array elements) generated in the first and second iterations?

1. 68 and 91
2. 68 and 102
3. 52 and 84
4. 52 and 91

Improvements on Binary Search algorithm:

Congrats! You have learned how to implement the binary search algorithm. But there is always room for improvement, right?

One possible way is to reduce the worst-case time complexity to O(1); you may check if the target element is equal to the first or last element of the array right in the beginning.

You discovered the wonders of Divide and Conquer and explored binary search in detail! So, the next time you are faced with looking through a large dataset, like a dictionary or your closet, look through its sections instead :)

Before you leave...

Binary search forms the basis of a Binary Search Tree.

If you want to learn about it in a similar article, drop a comment below and let us know your interest.

And if you enjoyed learning the fundamentals of binary search through this article, share the knowledge with your fellow programmers and your social circle. Maybe someone out there really needs this resource, and you might be helping them out by sharing it.

Happy Coding!

A binary tree is defined as a data structure that is non-linear in nature and follows a hierarchical structure. Also, it has a maximum of two children nodes for each of its parent nodes. The word binary is self-explanatory since it is associated with the number two.

Every node in a binary tree is associated with three distinct fields, namely:

• Data element
• Reference to the left child node
• Reference to the right child node

Given above is a simple diagram of a binary tree data structure. As you can see, the tree has a hierarchical structure and descends from a root node (with value 1). You may have also noticed that each of the nodes has at most 2 children nodes except for the leaf nodes. This is what categorizes this tree as a binary tree.

Basic Tree Terminology

Root Node

The initial node in a tree data structure is known as the Root Node. A root node is required for every tree. The root node is the starting point for the tree data structure. There can only be one root node in any tree. A tree can never have more than one root node.

Edge

The EDGE is the connecting line between any two nodes in a tree data structure. There will be a maximum limit of 'N-1' number of edges in a tree with 'N' nodes.

Parent Node

In a tree data structure, the predecessor node of any given node is called a parent node. In simpler terms, any node which has one or more children nodes associated with it is termed a parent node.

Child Node

In a tree data structure, the successor node of any given node is called a child node. In simpler terms, the descendant node of a given parent node is termed a child node.

Leaf Node

In a tree data structure, a terminating node without any subsequent children nodes is called a leaf node.

Internal Node

In a tree data structure, any node with one or more children nodes associated with it is called an internal node.

Degree

The total number of children nodes associated with a given node in a tree is called a degree.

Level

In a tree data structure, each step from the top to the bottom constitutes a level. For example, the root node is at level 0, the children of the root node are at level 1, and so on.

Height

The total number of edges in the longest path from a leaf node to any given node in a tree data structure is defined as the height of the given node.

The height associated with the root node is also the height of the tree data structure.

Properties of Binary Tree Data Structure

• The maximum number of nodes at each level ‘i’ of a binary tree is given by 2^i
• The minimum number of nodes at height ‘h’ of a binary tree is given by (h+1)
• The maximum number of nodes at height ‘h’ of a binary tree is given by (2^(h+1))-1

Various Types of Binary Tree Data Structure

Proper Binary Tree

It is a type of binary tree that has either two children or zero children for each node. It is also called a strict binary tree. Given below is a simple diagram to illustrate a proper binary tree.

It's clearly observable that every node (except the leaf nodes) has strictly 2 children. That is why it is also known as a strict binary tree.

Complete Binary Tree

It is a type of binary tree data structure in which all internal nodes are completely filled except for the nodes at the last level. In the last level, the nodes must be filled from as left as possible. Given below is an example of a complete binary tree.

You can clearly observe that the nodes at the last level (marked 2 and 3) are filled from the left and are not necessarily filled.

Properties

• Maximum number of nodes present in a complete binary tree of height h: 2^(h+1)-1.
• Minimum number of nodes present in a complete binary tree of height h: 2^h.
• Minimum height of a complete binary tree: log2(n+1) - 1.

Perfect Binary Tree

A tree is said to be a perfect binary tree if each of its nodes has strictly 2 children and all its leaf nodes are at the same level. Given below is a simple illustration of a perfect binary tree.

As you see, the leaf nodes are all at the same level and all the internal nodes have exactly 2 children each. This is what categorizes it as a perfect binary tree.

Test your understanding

Given below is another example of a binary tree. Can you guess whether it is a perfect binary tree or not?

Guess the answer??

.

.

Okay, the answer is a no. It's not a perfect binary tree for the simple reason that although the internal nodes have strictly 2 children each, the leaf nodes are not at the same level. This is an example of a proper binary tree instead.

Degenerate Binary Tree

A binary tree is categorized as a degenerate binary tree if all its internal nodes have strictly one child node each except for the leaf node. Here's a diagram to illustrate this:

Here's another example to elucidate this concept:

In both the diagrams given above, each of the nodes in the tree has strictly one child node except for the terminating leaf node.

If all the nodes of a degenerate binary tree have a left child node only, it forms a left-skewed binary tree.

Similarly, if all nodes of the tree have a right child node only, it forms a right-skewed binary tree.

Balanced Binary Tree

In a balanced binary tree data structure, the height of the left and right subtrees for each node differ by at most 1. Some common examples of balanced binary trees are AVL trees and Red-Black trees.

Still unclear? Here's an example to understand balanced binary trees better.

Node 1

• Height of the left subtree for given node = 2
• Height of the right subtree for given node = 2
• Difference = 0

Node 2

• Height of the left subtree for given node = 1
• Height of the right subtree for given node = 1
• Difference = 0

Node 3

• Height of the left subtree for given node = 1
• Height of the right subtree for given node = 1
• Difference = 0

Test your understanding

Given below is another diagram of a binary tree. Can you guess whether it is a balanced binary tree or not?

Struggling with the answer?

.

.

The correct answer is yes, it is a balanced binary tree, for the simple reason that the difference of at most 1 still holds for every internal node.

Binary Tree Implementation in C++

Given above is a simple C++ implementation of a binary tree data structure. Once executed, the following tree structure gets stored in memory:

1. First define a struct for the basic outline of your binary tree. Inside the main() function, you can observe that the root node is defined first which is assigned a value of 10.

2. Next, define the left and right children nodes of the root node and assign values of 20 and 30 respectively.

3. This is the basic structure of a binary tree in C++.

4. Of course, you can expand on it to form more complex tree structures but this should be a good foundation to start with.

Real-Life Implementation of Tree Data Structure

• Machine learning employs decision-based algorithms which are heavily reliant on the tree data structure.
• SQL databases use B-Tree for indexing.
• The file directory structure of our laptops or computers resembles a hierarchical tree structure.

Conclusion

Binary trees have a lot of applications in different fields including machine learning, computing systems, databases, computer networking among many others. In other words, its applications are limitless.

Of course, we've barely touched the surface when it comes to the conceptual aspects of binary trees. You can branch out from this article and explore the transversal algorithms associated with trees, how it relates to other data structures in existence, or you may as well crunch out some problems related to them.

Before you go, could you please share this article with your friends or on your social media handles? Also if you enjoyed reading this article, please don't forget to give a thumbs up.

Happy coding!!!