Tag: Sorting Algorithm Comparsion

Insertion Sort Algorithm | Example | Time Complexity

Design & Analysis of Algorithms

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

 

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

 

 

2 5 11 7 6 For j = 2; 11 > 7 so A[3] = 11
2 5 11 11 6 For j = 1; 5 < 7 so loop stops and A[2] = 7
2 5 7 11 6 After 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 Case n
Average Case n2
Worst Case n2

 

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

 

Other Popular Sorting Algorithms-

 

 

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

Design & Analysis of Algorithms

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 Case n2
Average Case n2
Worst Case n2

 

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- Bubble Sort

 

Other Popular Sorting Algorithms-

 

 

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

Watch video lectures by visiting our YouTube channel LearnVidFun.

Topological Sort | Topological Sort Examples

Design & Analysis of Algorithms

Topological Sort-

 

Topological Sort is a linear ordering of the vertices in such a way that

if there is an edge in the DAG going from vertex ‘u’ to vertex ‘v’,

then ‘u’ comes before ‘v’ in the ordering.

 

It is important to note that-

  • Topological Sorting is possible if and only if the graph is a Directed Acyclic Graph.
  • There may exist multiple different topological orderings for a given directed acyclic graph.

 

Topological Sort Example-

 

Consider the following directed acyclic graph-

 

 

For this graph, following 4 different topological orderings are possible-

  • 1 2 3 4 5 6
  • 1 2 3 4 6 5
  • 1 3 2 4 5 6
  • 1 3 2 4 6 5

 

Applications of Topological Sort-

 

Few important applications of topological sort are-

  • Scheduling jobs from the given dependencies among jobs
  • Instruction Scheduling
  • Determining the order of compilation tasks to perform in makefiles
  • Data Serialization

 

PRACTICE PROBLEMS BASED ON TOPOLOGICAL SORT-

 

Problem-01:

 

Find the number of different topological orderings possible for the given graph-

 

 

Solution-

 

The topological orderings of the above graph are found in the following steps-

 

Step-01:

 

Write in-degree of each vertex-

 

 

Step-02:

 

  • Vertex-A has the least in-degree.
  • So, remove vertex-A and its associated edges.
  • Now, update the in-degree of other vertices.

 

 

Step-03:

 

  • Vertex-B has the least in-degree.
  • So, remove vertex-B and its associated edges.
  • Now, update the in-degree of other vertices.

 

 

Step-04:

 

There are two vertices with the least in-degree. So, following 2 cases are possible-

 

In case-01,

  • Remove vertex-C and its associated edges.
  • Then, update the in-degree of other vertices.

 

In case-02,

  • Remove vertex-D and its associated edges.
  • Then, update the in-degree of other vertices.

 

 

Step-05:

 

Now, the above two cases are continued separately in the similar manner.

 

In case-01,

  • Remove vertex-D since it has the least in-degree.
  • Then, remove the remaining vertex-E.

 

In case-02,

  • Remove vertex-C since it has the least in-degree.
  • Then, remove the remaining vertex-E.

 

 

Conclusion-

 

For the given graph, following 2 different topological orderings are possible-

  • A B C D E
  • A B D C E

 

Problem-02:

 

Find the number of different topological orderings possible for the given graph-

 

 

Solution-

 

The topological orderings of the above graph are found in the following steps-

 

Step-01:

 

Write in-degree of each vertex-

 

 

Step-02:

 

  • Vertex-1 has the least in-degree.
  • So, remove vertex-1 and its associated edges.
  • Now, update the in-degree of other vertices.

 

 

Step-03:

 

There are two vertices with the least in-degree. So, following 2 cases are possible-

 

In case-01,

  • Remove vertex-2 and its associated edges.
  • Then, update the in-degree of other vertices.

 

In case-02,

  • Remove vertex-3 and its associated edges.
  • Then, update the in-degree of other vertices.

 

 

Step-04:

 

Now, the above two cases are continued separately in the similar manner.

 

In case-01,

  • Remove vertex-3 since it has the least in-degree.
  • Then, update the in-degree of other vertices.

 

In case-02,

  • Remove vertex-2 since it has the least in-degree.
  • Then, update the in-degree of other vertices.

 

 

Step-05:

 

In case-01,

  • Remove vertex-4 since it has the least in-degree.
  • Then, update the in-degree of other vertices.

 

In case-02,

  • Remove vertex-4 since it has the least in-degree.
  • Then, update the in-degree of other vertices.

 

 

Step-06:

 

In case-01,

  • There are 2 vertices with the least in-degree.
  • So, 2 cases are possible.
  • Any of the two vertices may be taken first.

 

Same is with case-02.

 

 

Conclusion-

 

For the given graph, following 4 different topological orderings are possible-

  • 1 2 3 4 5 6
  • 1 2 3 4 6 5
  • 1 3 2 4 5 6
  • 1 3 2 4 6 5

 

Problem-03:

 

Consider the directed graph given below. Which of the following statements is true?

 

 

  1. The graph does not have any topological ordering.
  2. Both PQRS and SRPQ are topological orderings.
  3. Both PSRQ and SPRQ are topological orderings.
  4. PSRQ is the only topological ordering.

 

Solution-

 

  • The given graph is a directed acyclic graph.
  • So, topological orderings exist.
  • P and S must appear before R and Q in topological orderings as per the definition of topological sort.

 

Thus, Correct option is (C).

 

Problem-04:

 

Consider the following directed graph-

 

 

The number of different topological orderings of the vertices of the graph is ________ ?

 

Solution-

 

Number of different topological orderings possible = 6.

Thus, Correct answer is 6.

 

(The solution is explained in detail in the linked video lecture.)

 

To gain better understanding about Topological Sort,

Watch this Video Lecture

 

To practice previous years GATE problems on Topological Sort,

Watch this Video Lecture

 

Next Article- Shortest Path Problems

 

Other Popular Sorting Algorithms-

 

 

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

Watch video lectures by visiting our YouTube channel LearnVidFun.

Quick Sort Algorithm | Example | Time Complexity

Design & Analysis of Algorithms

Quick Sort-

 

  • Quick Sort is a famous sorting algorithm.
  • It sorts the given data items in ascending order.
  • It uses the idea of divide and conquer approach.
  • It follows a recursive algorithm.

 

Quick Sort Algorithm-

 

Consider-

  • a = Linear Array in memory
  • beg = Lower bound of the sub array in question
  • end = Upper bound of the sub array in question

 

Then, Quick Sort Algorithm is as follows-

 

Partition_Array (a , beg , end , loc)


Begin

Set left = beg , right = end , loc = beg

Set done = false

While (not done) do

    While ( (a[loc] <= a[right] ) and (loc ≠ right) ) do

    Set right = right - 1

    end while


    if (loc = right) then

    Set done = true

    else if (a[loc] > a[right]) then

        Interchange a[loc] and a[right]

        Set loc = right

    end if


    if (not done) then

    While ( (a[loc] >= a[left] ) and (loc ≠ left) ) do

    Set left = left + 1

    end while


    if (loc = left) then

    Set done = true

    else if (a[loc] < a[left]) then

        Interchange a[loc] and a[left]

        Set loc = left

    end if

    end if

end while

End

 

How Does Quick Sort Works?

 

  • Quick Sort follows a recursive algorithm.
  • It divides the given array into two sections using a partitioning element called as pivot.

 

The division performed is such that-

  • All the elements to the left side of pivot are smaller than pivot.
  • All the elements to the right side of pivot are greater than pivot.

 

After dividing the array into two sections, the pivot is set at its correct position.

Then, sub arrays are sorted separately by applying quick sort algorithm recursively.

 

Quick Sort Example-

 

Consider the following array has to be sorted in ascending order using quick sort algorithm-

 

 

Quick Sort Algorithm works in the following steps-

 

Step-01:

 

Initially-

  • Left and Loc (pivot) points to the first element of the array.
  • Right points to the last element of the array.

 

So to begin with, we set loc = 0, left = 0 and right = 5 as-

 

 

Step-02:

 

Since loc points at left, so algorithm starts from right and move towards left.

As a[loc] < a[right], so algorithm moves right one position towards left as-

 

 

Now, loc = 0, left = 0 and right = 4.

 

Step-03:

 

Since loc points at left, so algorithm starts from right and move towards left.

As a[loc] > a[right], so algorithm swaps a[loc] and a[right] and loc points at right as-

 

 

Now, loc = 4, left = 0 and right = 4.

 

Step-04:

 

Since loc points at right, so algorithm starts from left and move towards right.

As a[loc] > a[left], so algorithm moves left one position towards right as-

 

 

Now, loc = 4, left = 1 and right = 4.

 

Step-05:

 

Since loc points at right, so algorithm starts from left and move towards right.

As a[loc] > a[left], so algorithm moves left one position towards right as-

 

 

Now, loc = 4, left = 2 and right = 4.

 

Step-06:

 

Since loc points at right, so algorithm starts from left and move towards right.

As a[loc] < a[left], so we algorithm swaps a[loc] and a[left] and loc points at left as-

 

 

Now, loc = 2, left = 2 and right = 4.

 

Step-07:

 

Since loc points at left, so algorithm starts from right and move towards left.

As a[loc] < a[right], so algorithm moves right one position towards left as-

 

 

Now, loc = 2, left = 2 and right = 3.

 

Step-08:

 

Since loc points at left, so algorithm starts from right and move towards left.

As a[loc] > a[right], so algorithm swaps a[loc] and a[right] and loc points at right as-

 

 

Now, loc = 3, left = 2 and right = 3.

 

Step-09:

 

Since loc points at right, so algorithm starts from left and move towards right.

As a[loc] > a[left], so algorithm moves left one position towards right as-

 

 

Now, loc = 3, left = 3 and right = 3.

 

Now,

  • loc, left and right points at the same element.
  • This indicates the termination of procedure.
  • The pivot element 25 is placed in its final position.
  • All elements to the right side of element 25 are greater than it.
  • All elements to the left side of element 25 are smaller than it.

 

 

Now, quick sort algorithm is applied on the left and right sub arrays separately in the similar manner.

 

Quick Sort Analysis-

 

  • To find the location of an element that splits the array into two parts, O(n) operations are required.
  • This is because every element in the array is compared to the partitioning element.
  • After the division, each section is examined separately.
  • If the array is split approximately in half (which is not usually), then there will be log2n splits.
  • Therefore, total comparisons required are f(n) = n x log2n = O(nlog2n).

 

Order of Quick Sort = O(nlog2n)

 

Worst Case-

 

  • Quick Sort is sensitive to the order of input data.
  • It gives the worst performance when elements are already in the ascending order.
  • It then divides the array into sections of 1 and (n-1) elements in each call.
  • Then, there are (n-1) divisions in all.
  • Therefore, here total comparisons required are f(n) = n x (n-1) = O(n2).

 

Order of Quick Sort in worst case = O(n2)

 

Advantages of Quick Sort-

 

The advantages of quick sort algorithm are-

  • Quick Sort is an in-place sort, so it requires no temporary memory.
  • Quick Sort is typically faster than other algorithms.

(because its inner loop can be efficiently implemented on most architectures)

  • Quick Sort tends to make excellent usage of the memory hierarchy like virtual memory or caches.
  • Quick Sort can be easily parallelized due to its divide and conquer nature.

 

Disadvantages of Quick Sort-

 

The disadvantages of quick sort algorithm are-

  • The worst case complexity of quick sort is O(n2).
  • This complexity is worse than O(nlogn) worst case complexity of algorithms like merge sort, heap sort etc.
  • It is not a stable sort i.e. the order of equal elements may not be preserved.

 

To gain better understanding about Quick Sort Algorithm,

Watch this Video Lecture

 

Next Article- Topological Sort

 

Other Popular Sorting Algorithms-

 

 

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

Watch video lectures by visiting our YouTube channel LearnVidFun.