Tag: algorithms

Insertion Sort | Insertion Sort Algorithm

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 more element is placed at correct location in the sorted sub-array until array A is completely sorted.

 

Selection Sort Time Complexity-

 

  • 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

 

Selection Sort Space Complexity-

 

  • 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

 

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

Watch video lectures by visiting our YouTube channel LearnVidFun.

Selection Sort | Selection Sort Algorithm

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 i.e. it uses no auxiliary data structures while sorting.

 

How Selection Sort Works?

 

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

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. The 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.
  • And placed at the correct location in the sorted sub-array until array A is completely sorted.

 

Selection Sort Time Complexity-

 

  • 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

 

Selection Sort Space Complexity-

 

  • 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

 

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

Watch video lectures by visiting our YouTube channel LearnVidFun.

Master’s Theorem | Master’s Theorem Examples

Master’s Theorem-

 

Master’s Theorem is a popular method for solving the recurrence relations.

 

Master’s theorem solves recurrence relations of the form-

 

 

where a >= 1, b > 1, k >= 0 and p is a real number

 

Solving Recurrence Relations-

 

To solve recurrence relations using Master’s theorem, we compare a with bk.

Then, we follow the following cases-

 

Case-01:

 

If a > bk, then T(n) = θ (nlogba)

 

Case-02:

 

If a = band

  • If p < -1, then T(n) = θ (nlogba)
  • If p = -1, then T(n) = θ (nlogba.log2n)
  • If p > -1, then T(n) = θ (nlogba.logp+1n)

 

Case-03:

 

If a < band

  • If p < 0,  then T(n) = O (nk)
  • If p >= 0, then T(n) = θ (nklogpn)

 

PRACTICE PROBLEMS BASED ON MASTER’S THEOREM-

 

Problem-01:

 

Solve the following recurrence relation using Master’s theorem-

T(n) = 3T(n/2) + n2

 

Solution-

 

On comparing the given recurrence relation with-

T(n) = aT(n/b) + θ (nklogpn)

we have-

a = 3

b = 2

k = 2

p = 0

 

Now, a = 3 and bk = 22 = 4.

Clearly, a < bk

So, we follow case-03.

Since p = 0, so we have-

T(n) = θ (nklogpn)

T(n) = θ (n2log0n)

 

Thus,

T(n) = θ (n2)

 

Problem-02:

 

Solve the following recurrence relation using Master’s theorem-

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

 

Solution-

 

On comparing the given recurrence relation with-

T(n) = aT(n/b) + θ (nklogpn)

we have-

a = 2

b = 2

k = 1

p = 1

 

Now, a = 2 and bk = 21 = 2.

Clearly, a = bk

So, we follow case-02.

Since p = 1, so we have-

T(n) = θ (nlogba.logp+1n)

T(n) = θ (nlog22.log1+1n)

 

Thus,

T(n) = θ (nlog2n)

 

Problem-03:

 

Solve the following recurrence relation using Master’s theorem-

T(n) = 2T(n/4) + n0.51

 

Solution-

 

On comparing the given recurrence relation with-

T(n) = aT(n/b) + θ (nklogpn)

we have-

a = 2

b = 4

k = 0.51

p = 0

 

Now, a = 2 and bk = 40.51 = 2.0279.

Clearly, a < bk

So, we follow case-03.

Since p = 0, so we have-

T(n) = θ (nklogpn)

T(n) = θ (n0.51log0n)

 

Thus,

T(n) = θ (n0.51)

 

Problem-04:

 

Solve the following recurrence relation using Master’s theorem-

T(n) = √2T(n/2) + logn

 

Solution-

 

On comparing the given recurrence relation with-

T(n) = aT(n/b) + θ (nklogpn)

we have-

a = √2

b = 2

k = 0

p = 1

 

Now, a = √2 = 1.414 and bk = 20 = 1.

Clearly, a > bk

So, we follow case-01.

So, we have-

T(n) = θ (nlogba)

T(n) = θ (nlog2√2)

T(n) = θ (n1/2)

 

Thus,

T(n) = θ (√n)

 

Problem-05:

 

Solve the following recurrence relation using Master’s theorem-

T(n) = 8T(n/4) – n2logn

 

Solution-

 

  • The given recurrence relation does not correspond to the general form of Master’s theorem.
  • So, it can not be solved using Master’s theorem.

 

Problem-06:

 

Solve the following recurrence relation using Master’s theorem-

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

 

Solution-

 

  • We can write the given recurrence relation as T(n) = 3T(n/3) + n.
  • This is because in the general form, we have θ for function f(n) which hides constants in it.
  • Now, we can easily apply Master’s theorem.

 

On comparing the given recurrence relation with-

T(n) = aT(n/b) + θ (nklogpn)

we have-

a = 3

b = 3

k = 1

p = 0

 

Now, a = 3 and bk = 31 = 3.

Clearly, a = bk

So, we follow case-02.

Since p = 0, so we have-

T(n) = θ (nlogba.logp+1n)

T(n) = θ (nlog33.log0+1n)

T(n) = θ (n1.log1n)

 

Thus,

T(n) = θ (nlogn)

 

Problem-07:

 

Form a recurrence relation for the following code and solve it using Master’s theorem-

 

A(n)
{
   if(n<=1)
     return 1;
   else
     return A(√n);
}

 

Solution-

 

  • We can write a recurrence relation for the given code as T(n) = T(n) + 1.
  • Here 1 = Constant time taken for comparing and returning the value.
  • We can not directly apply Master’s Theorem on this recurrence relation.
  • This is because it does not correspond to the general form of Master’s theorem.
  • However, we can modify and bring it in the general form to apply Master’s theorem.

 

Let-

n = 2m    ……(1)

then-

T(2m) = T(2m/2) + 1

 

Now, let T(2m) = S(m), then T(2m/2) = S(m/2)

So, we have-

S(m) = S(m/2) +1

Now, we can easily apply Master’s Theorem.

 

On comparing the given recurrence relation with-

S(m) = aS(m/b) + θ (mklogpm)

we have-

a = 1

b = 2

k = 0

p = 0

 

Now, a = 1 and bk = 20 = 1.

Clearly, a = bk

So, we follow case-02.

Since p = 0, so we have-

S(m) = θ (mlogba.logp+1m)

S(m) = θ (mlog21.log0+1m)

S(m) = θ (m0.log1m)

 

Thus,

S(m) = θ(logm)    ……(2)

 

Now,

  • From (1), we have n = 2m.
  • So, logn = mlog2 which implies m = log2n.

 

Substituting in (2), we get-

S(m) = θ(loglog2n)

Or

T(n) = θ (loglog2n)

 

To gain better understanding about Master’s Theorem,

Watch this Video Lecture

 

Next Article- Recursion Tree

 

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

Watch video lectures by visiting our YouTube channel LearnVidFun.