Category: Design & Analysis of Algorithms

Merge Sort Algorithm | Example | Time Complexity

Merge Sort-

 

  • Merge sort is a famous sorting algorithm.
  • It uses a divide and conquer paradigm for sorting.
  • It divides the problem into sub problems and solves them individually.
  • It then combines the results of sub problems to get the solution of the original problem.

 

How Merge Sort Works?

 

Before learning how merge sort works, let us learn about the merge procedure of merge sort algorithm.

The merge procedure of merge sort algorithm is used to merge two sorted arrays into a third array in sorted order.

 

Consider we want to merge the following two sorted sub arrays into a third array in sorted order-

 

 

The merge procedure of merge sort algorithm is given below-

 

// L : Left Sub Array , R : Right Sub Array , A : Array

merge(L, R, A)
{
    nL = length(L)    // Size of Left Sub Array
    nR = length(R)    // Size of Right Sub Array

    i = j = k = 0

    while(i<nL && j<nR)
    {
      /* When both i and j are valid i.e. when both the sub arrays have elements to insert in A */
      
       if(L[i] <= R[j])
       {
          A[k] = L[i]
          k = k+1
          i = i+1
       }
       else
       {
          A[k] = R[j]
          k = k+1
          j = j+1
       }
    }

    // Adding Remaining elements from left sub array to array A
    while(i<nL)
    {
       A[k] = L[i]
       i = i+1
       k = k+1
    }

    // Adding Remaining elements from right sub array to array A
    while(j<nR)
    {
       A[k] = R[j]
       j = j+1
       k = k+1
    }
}

 

The above merge procedure of merge sort algorithm is explained in the following steps-

 

Step-01:

 

  • Create two variables i and j for left and right sub arrays.
  • Create variable k for sorted output array.

 

 

Step-02:

 

  • We have i = 0, j = 0, k = 0.
  • Since L[0] < R[0], so we perform A[0] = L[0] i.e. we copy the first element from left sub array to our sorted output array.
  • Then, we increment i and k by 1.

 

Then, we have-

 

 

Step-03:

 

  • We have i = 1, j = 0, k = 1.
  • Since L[1] > R[0], so we perform A[1] = R[0] i.e. we copy the first element from right sub array to our sorted output array.
  • Then, we increment j and k by 1.

 

Then, we have-

 

 

Step-04:

 

  • We have i = 1, j = 1, k = 2.
  • Since L[1] > R[1], so we perform A[2] = R[1].
  • Then, we increment j and k by 1.

 

Then, we have-

 

 

Step-05:

 

  • We have i = 1, j = 2, k = 3.
  • Since L[1] < R[2], so we perform A[3] = L[1].
  • Then, we increment i and k by 1.

 

Then, we have-

 

 

Step-06:

 

  • We have i = 2, j = 2, k = 4.
  • Since L[2] > R[2], so we perform A[4] = R[2].
  • Then, we increment j and k by 1.

 

Then, we have-

 

 

Step-07:

 

  • Clearly, all the elements from right sub array have been added to the sorted output array.
  • So, we exit the first while loop with the condition while(i<nL && j<nR) since now j>nR.
  • Then, we add remaining elements from the left sub array to the sorted output array using next while loop.

 

Finally, our sorted output array is-

 

 

Basically,

  • After finishing elements from any of the sub arrays, we can add the remaining elements from the other sub array to our sorted output array as it is.
  • This is because left and right sub arrays are already sorted.

 

Time Complexity

The above mentioned merge procedure takes Θ(n) time.

This is because we are just filling an array of size n from left & right sub arrays by incrementing i and j at most Θ(n) times.

 

Also Read- Insertion Sort

 

Merge Sort Algorithm-

 

Merge Sort Algorithm works in the following steps-

  • It divides the given unsorted array into two halves- left and right sub arrays.
  • The sub arrays are divided recursively.
  • This division continues until the size of each sub array becomes 1.
  • After each sub array contains only a single element, each sub array is sorted trivially.
  • Then, the above discussed merge procedure is called.
  • The merge procedure combines these trivially sorted arrays to produce a final sorted array.

 

The division procedure of merge sort algorithm which uses recursion is given below-

 

// A : Array that needs to be sorted

MergeSort(A)
{
   n = length(A)
   if n<2 return
   mid = n/2
   left = new_array_of_size(mid)       // Creating temporary array for left
   right = new_array_of_size(n-mid)    // and right sub arrays

   for(int i=0 ; i<=mid-1 ; ++i)
   {
      left[i] = A[i]                  // Copying elements from A to left
   }

   for(int i=mid ; i<=n-1 ; ++i)
   {
      right[i-mid] = A[i]             // Copying elements from A to right
   }

   MergeSort(left)                    // Recursively solving for left sub array
   MergeSort(right)                   // Recursively solving for right sub array

   merge(left, right, A)              // Merging two sorted left/right sub array to final array
}

 

Merge Sort Example-

 

Consider the following elements have to be sorted in ascending order-

6, 2, 11, 7, 5, 4

 

The merge sort algorithm works as-

 

 

Time Complexity Analysis-

 

In merge sort, we divide the array into two (nearly) equal halves and solve them recursively using merge sort only.

So, we have-

 

 

Finally, we merge these two sub arrays using merge procedure which takes Θ(n) time as explained above.

 

If T(n) is the time required by merge sort for sorting an array of size n, then the recurrence relation for time complexity of merge sort is-

 

 

On solving this recurrence relation, we get T(n) = Θ(nlogn).

Thus, time complexity of merge sort algorithm is T(n) = Θ(nlogn).

 

Also Read- Master’s Theorem for Solving Recurrence Relations

 

Space Complexity Analysis-

 

  • Merge sort uses additional memory for left and right sub arrays.
  • Hence, total Θ(n) extra memory is needed.

 

Properties-

 

Some of the important properties of merge sort algorithm are-

  • Merge sort uses a divide and conquer paradigm for sorting.
  • Merge sort is a recursive sorting algorithm.
  • Merge sort is a stable sorting algorithm.
  • Merge sort is not an in-place sorting algorithm.
  • The time complexity of merge sort algorithm is Θ(nlogn).
  • The space complexity of merge sort algorithm is Θ(n).

 

NOTE

Merge sort is the best sorting algorithm in terms of time complexity Θ(nlogn)

if we are not concerned with auxiliary space used.

 

PRACTICE PROBLEMS BASED ON MERGE SORT ALGORITHM-

 

Problem-

 

Assume that a merge sort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes? (GATE 2015)

  1. 256
  2. 512
  3. 1024
  4. 2048

 

Solution-

 

We know, time complexity of merge sort algorithm is Θ(nlogn).

 

Step-01:

 

It is given that a merge sort algorithm in the worst case takes 30 seconds for an input of size 64.

So, we have-

 

k x nlogn = 30                   (for n = 64)

k x 64 log64 = 30

k x 64 x 6 = 30

From here, k = 5 / 64.

 

Step-02:

 

Let n be the maximum input size of a problem that can be solved in 6 minutes (or 360 seconds).

Then, we have-

 

k x nlogn = 360

(5/64) x nlogn = 360         { Using Result of Step-01 }

nlogn = 72 x 64

nlogn = 4608

On solving this equation, we get n = 512.

 

Thus, correct option is (B).

 

To gain better understanding about Merge Sort Algorithm,

Watch this Video Lecture

 

Next Article- Quick Sort

 

Get more notes and other study material of Design and Analysis of Algorithms.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Insertion Sort Algorithm | Example | Time Complexity

Insertion Sort-

 

  • Insertion sort is an in-place sorting algorithm.
  • It uses no auxiliary data structures while sorting.
  • It is inspired from the way in which we sort playing cards.

 

How Insertion Sort Works?

 

Consider the following elements are to be sorted in ascending order-

6, 2, 11, 7, 5

 

Insertion sort works as-

 

Firstly,

  • It selects the second element (2).
  • It checks whether it is smaller than any of the elements before it.
  • Since 2 < 6, so it shifts 6 towards right and places 2 before it.
  • The resulting list is 2, 6, 11, 7, 5.

 

Secondly,

  • It selects the third element (11).
  • It checks whether it is smaller than any of the elements before it.
  • Since 11 > (2, 6), so no shifting takes place.
  • The resulting list remains the same.

 

Thirdly,

  • It selects the fourth element (7).
  • It checks whether it is smaller than any of the elements before it.
  • Since 7 < 11, so it shifts 11 towards right and places 7 before it.
  • The resulting list is 2, 6, 7, 11, 5.

 

Fourthly,

  • It selects the fifth element (5).
  • It checks whether it is smaller than any of the elements before it.
  • Since 5 < (6, 7, 11), so it shifts (6, 7, 11) towards right and places 5 before them.
  • The resulting list is 2, 5, 6, 7, 11.

 

As a result, sorted elements in ascending order are-

2, 5, 6, 7, 11

 

Also Read- Selection Sort

 

Insertion Sort Algorithm-

 

Let A be an array with n elements. The insertion sort algorithm used for sorting is as follows-

 

for (i = 1 ; i < n ; i++)

{

   key = A [ i ];

   j = i - 1;

   while(j > 0 && A [ j ] > key)

   {

       A [ j+1 ] = A [ j ];

       j--;

    }

    A [ j+1 ] = key;

}

 

Here,

  • i = variable to traverse the array A
  • key = variable to store the new number to be inserted into the sorted sub-array
  • j = variable to traverse the sorted sub-array

 

Insertion Sort Example-

 

Consider the following elements are to be sorted in ascending order-

6, 2, 11, 7, 5

 

The above insertion sort algorithm works as illustrated below-

 

Step-01: For i = 1

 

 

Step-02: For i = 2

 

 

Step-03: For i = 3

 

 

251176For j = 2; 11 > 7 so A[3] = 11
2511116For j = 1; 5 < 7 so loop stops and A[2] = 7
257116After inner loop ends

 

Working of inner loop when i = 3

 

Step-04: For i = 4

 

 

Loop gets terminated as ‘i’ becomes 5. The state of array after the loops are finished-

 

 

With each loop cycle,

  • One element is placed at the correct location in the sorted sub-array until array A is completely sorted.

 

Time Complexity Analysis-

 

  • Selection sort algorithm consists of two nested loops.
  • Owing to the two nested loops, it has O(n2) time complexity.

 

Time Complexity
Best Casen
Average Casen2
Worst Casen2

 

Space Complexity Analysis-

 

  • Selection sort is an in-place algorithm.
  • It performs all computation in the original array and no other array is used.
  • Hence, the space complexity works out to be O(1).

 

Important Notes-

 

  • Insertion sort is not a very efficient algorithm when data sets are large.
  • This is indicated by the average and worst case complexities.
  • Insertion sort is adaptive and number of comparisons are less if array is partially sorted.

 

To gain better understanding about Insertion Sort Algorithm,

Watch this Video Lecture

 

Next Article- Merge Sort

 

Get more notes and other study material of Design and Analysis of Algorithms.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Selection Sort Algorithm | Example | Time Complexity

Selection Sort-

 

  • Selection sort is one of the easiest approaches to sorting.
  • It is inspired from the way in which we sort things out in day to day life.
  • It is an in-place sorting algorithm because it uses no auxiliary data structures while sorting.

 

How Selection Sort Works?

 

Consider the following elements are to be sorted in ascending order using selection sort-

6, 2, 11, 7, 5

 

Selection sort works as-

  • It finds the first smallest element (2).
  • It swaps it with the first element of the unordered list.
  • It finds the second smallest element (5).
  • It swaps it with the second element of the unordered list.
  • Similarly, it continues to sort the given elements.

 

As a result, sorted elements in ascending order are-

2, 5, 6, 7, 11

 

Selection Sort Algorithm-

 

Let A be an array with n elements. Then, selection sort algorithm used for sorting is as follows-

 

for (i = 0 ; i < n-1 ; i++)

{

   index = i;

   for(j = i+1 ; j < n ; j++)

   {

      if(A[j] < A[index])

      index = j;

   }

   temp = A[i];

   A[i] = A[index];

   A[index] = temp;

}

 

Here,

  • i = variable to traverse the array A
  • index = variable to store the index of minimum element
  • j = variable to traverse the unsorted sub-array
  • temp = temporary variable used for swapping

 

Selection Sort Example-

 

Consider the following elements are to be sorted in ascending order-

6, 2, 11, 7, 5

 

The above selection sort algorithm works as illustrated below-

 

Step-01: For i = 0

 

 

Step-02: For i = 1

 

 

Step-03: For i = 2

 

 

Step-04: For i = 3

 

 

Step-05: For i = 4

 

Loop gets terminated as ‘i’ becomes 4.

 

The state of array after the loops are finished is as shown-

 

 

With each loop cycle,

  • The minimum element in unsorted sub-array is selected.
  • It is then placed at the correct location in the sorted sub-array until array A is completely sorted.

 

Time Complexity Analysis-

 

  • Selection sort algorithm consists of two nested loops.
  • Owing to the two nested loops, it has O(n2) time complexity.

 

Time Complexity
Best Casen2
Average Casen2
Worst Casen2

 

Space Complexity Analysis-

 

  • Selection sort is an in-place algorithm.
  • It performs all computation in the original array and no other array is used.
  • Hence, the space complexity works out to be O(1).

 

Important Notes-

 

  • Selection sort is not a very efficient algorithm when data sets are large.
  • This is indicated by the average and worst case complexities.
  • Selection sort uses minimum number of swap operations O(n) among all the sorting algorithms.

 

To gain better understanding about Selection Sort Algorithm,

Watch this Video Lecture

 

Next Article- Insertion Sort

 

Get more notes and other study material of Design and Analysis of Algorithms.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Difference Between Prim’s and Kruskal’s Algorithm

Prim’s and Kruskal’s Algorithms-

 

Before you go through this article, make sure that you have gone through the previous articles on Prim’s Algorithm & Kruskal’s Algorithm.

 

We have discussed-

  • Prim’s and Kruskal’s Algorithm are the famous greedy algorithms.
  • They are used for finding the Minimum Spanning Tree (MST) of a given graph.
  • To apply these algorithms, the given graph must be weighted, connected and undirected.

 

Some important concepts based on them are-

 

Concept-01:

 

If all the edge weights are distinct, then both the algorithms are guaranteed to find the same MST.

 

Example-

 

Consider the following example-

 

 

Here, both the algorithms on the above given graph produces the same MST as shown.

 

Concept-02:

 

  • If all the edge weights are not distinct, then both the algorithms may not always produce the same MST.
  • However, cost of both the MSTs would always be same in both the cases.

 

Example-

 

Consider the following example-

 

 

Here, both the algorithms on the above given graph produces different MSTs as shown but the cost is same in both the cases.

 

Concept-03:

 

Kruskal’s Algorithm is preferred when-

  • The graph is sparse.
  • There are less number of edges in the graph like E = O(V)
  • The edges are already sorted or can be sorted in linear time.

 

Prim’s Algorithm is preferred when-

  • The graph is dense.
  • There are large number of edges in the graph like E = O(V2).

 

Concept-04:

 

Difference between Prim’s Algorithm and Kruskal’s Algorithm-

 

Prim’s AlgorithmKruskal’s Algorithm
The tree that we are making or growing always remains connected.The tree that we are making or growing usually remains disconnected.
Prim’s Algorithm grows a solution from a random vertex by adding the next cheapest vertex to the existing tree.Kruskal’s Algorithm grows a solution from the cheapest edge by adding the next cheapest edge to the existing tree / forest.
Prim’s Algorithm is faster for dense graphs.Kruskal’s Algorithm is faster for sparse graphs.

 

To gain better understanding about Difference between Prim’s and Kruskal’s Algorithm,

Watch this Video Lecture

 

Next Article- Linear Search

 

Get more notes and other study material of Design and Analysis of Algorithms.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Kruskal’s Algorithm | Kruskal’s Algorithm Example | Problems

Kruskal’s Algorithm-

 

  • Kruskal’s Algorithm is a famous greedy algorithm.
  • It is used for finding the Minimum Spanning Tree (MST) of a given graph.
  • To apply Kruskal’s algorithm, the given graph must be weighted, connected and undirected.

 

Kruskal’s Algorithm Implementation-

 

The implementation of Kruskal’s Algorithm is explained in the following steps-

 

Step-01:

 

  • Sort all the edges from low weight to high weight.

 

Step-02:

 

  • Take the edge with the lowest weight and use it to connect the vertices of graph.
  • If adding an edge creates a cycle, then reject that edge and go for the next least weight edge.

 

Step-03:

 

  • Keep adding edges until all the vertices are connected and a Minimum Spanning Tree (MST) is obtained.

 

Thumb Rule to Remember

 

The above steps may be reduced to the following thumb rule-

  • Simply draw all the vertices on the paper.
  • Connect these vertices using edges with minimum weights such that no cycle gets formed.

 

Kruskal’s Algorithm Time Complexity-

 

Worst case time complexity of Kruskal’s Algorithm

= O(ElogV) or O(ElogE)

 

Analysis-

 

  • The edges are maintained as min heap.
  • The next edge can be obtained in O(logE) time if graph has E edges.
  • Reconstruction of heap takes O(E) time.
  • So, Kruskal’s Algorithm takes O(ElogE) time.
  • The value of E can be at most O(V2).
  • So, O(logV) and O(logE) are same.

 

Special Case-

 

  • If the edges are already sorted, then there is no need to construct min heap.
  • So, deletion from min heap time is saved.
  • In this case, time complexity of Kruskal’s Algorithm = O(E + V)

 

Also Read- Prim’s Algorithm

 

PRACTICE PROBLEMS BASED ON KRUSKAL’S ALGORITHM-

 

Problem-01:

 

Construct the minimum spanning tree (MST) for the given graph using Kruskal’s Algorithm-

 

 

Solution-

 

To construct MST using Kruskal’s Algorithm,

  • Simply draw all the vertices on the paper.
  • Connect these vertices using edges with minimum weights such that no cycle gets formed.

 

Step-01:

 

 

Step-02:

 

 

Step-03:

 

 

Step-04:

 

 

Step-05:

 

 

Step-06:

 

 

Step-07:

 

 

Since all the vertices have been connected / included in the MST, so we stop.

Weight of the  MST

= Sum of all edge weights

= 10 + 25 + 22 + 12 + 16 + 14

= 99 units

 

To gain better understanding about Kruskal’s Algorithm,

Watch this Video Lecture

 

To practice previous years GATE problems based on Kruskal’s Algorithm,

Watch this Video Lecture

 

Next Article- Prim’s Algorithm Vs Kruskal’s Algorithm

 

Get more notes and other study material of Design and Analysis of Algorithms.

Watch video lectures by visiting our YouTube channel LearnVidFun.