virtualgate's picture

Sorting Algorithms: Insertion, Selection, Bubble

Insertion sort algorithm and analysis
Content covered: 

Insertion Sort:
Insertion sort is based on the card game in which we sort the playing cards in our hand. In this sorting, each time we compare the element to be inserted in sorted subarray and find it's right position before inserting it.

Insertion_Sort (A)
{
  for j=2 to A.length
  Key = A[j]
  // insert A[j] into sorted sequence A[1.......j-1]
  i=j-1
  while (i>0 and A[i] > Key)
       A[i+1] = A[i]
       i = i-1
   A[i+1] = key
}

Time Complexity:
Best Case: O(n)
Average Case: O(n2)
Worst Case: O(n2)

More Less
0Comment
Introduction to Bubble sort
Content covered: 

Bubble Sort:
Bubble sort is a comparative sort in which we compare an element with its adjacent element, if second element is smaller than the first one then those element will be interchanged. Now again element is selected and compared with its adjacent. This process will be continued untill the highest element will reach at the last position. 

Bubble_Sort (a, n)
Begin 
  for k=1 to n-1
     for j=0 to n-k-1 
         if a[j] > a[j+1] then
              Set temp = a[j];
              Set a[j] = a[j+1];
              Set a[j+1] = temp;
          endif
      endfor
   endfor
End

Time Complexity:
Best Case: O(n)
Average Case: O(n2)
Worst Case: O(n2)

More Less
0Comment
Time complexity of Bubble sort algorithm
Content covered: 

Time Complexity of Bubble sort algorithm:
Best Case: O(n)
Average Case: O(n2)
Worst Case: O(n2)

More Less
0Comment
Selection Sort | Algorithm and Analysis
Content covered: 

Selection Sort:
The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

Void SelectionSort (int*arr, int n)
{
   for (int i=0; i<n-1; ++i)
   {
        int minIdx = i;
        for(int j = i+1; j<n; ++j)
        {
             if (arr[j] < arr[minIdx)
                  minIdx = j;
         }
         if (minIdx != i)
             swap (arr, i, minIdx);
    }
}  

Time Complexity:
Best Case: O(n2)
Average Case: O(n2)
Worst Case: O(n2)
Note:- Selection is stable with O(n) extra space, for example using lists.

More Less
0Comment
GATE 2003 Example on Insertion Sort

The unusual \(\Theta(n^2)\) implementation of Insertion Sort to sort an array uses linear search to identify the position where and
element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position,
the worst case running time will be:

A) Remains \(\Theta(n^2)\)

B) become \(\Theta(n(\log n)^2)\)

C) become \(\Theta(n)\)

d) become \(\Theta(n\log n)\)

void insertionSort(int arr[], int n)
{
   int i, key, j;
   for (i = 1; i < n; i++)
   {
       key = arr[i];
       j = i-1;
 
       /* Move elements of arr[0..i-1], that are
          greater than key, to one position ahead
          of their current position */
       while (j >= 0 && arr[j] > key)
       {
           arr[j+1] = arr[j];
           j = j-1;
       }
       arr[j+1] = key;
   }
}

 

Consider, Intermediate state of Array (containing numbers) while the execution of insertion sort :

 {Here, numbers to the left of number-0 are sorted }

When linear search is used

Time to find the correct position of key \(\Theta(n)\)

Time to move the elements to make space for key : \(\Theta(n)\)

Total elements = n

\(\therefore Total\ \ Time = n(\Theta(n) + \Theta(n)) = \Theta(n^2)\)

 

When binary search is used

Time to find the correct position of key : \(\Theta(\log n)\)

Time to move the elements in the array to make space for key \(\Theta(n)\)

Total elements = \(n\)

\(\therefore Total \ \ Time = n(\Theta(\log n) + \Theta(n)) = \Theta(n^2)\)

Hence, Although we made impovement over the searching for the position of the key, but we still need to move the elements which'll take the same time \(\Theta(n)\). Therefore the total time remains same i.e \(\Theta(n^2)\)

Ans (A)

1Comment
GATE 2009 Example on Selection Sort

What is the number of swaps required to sort elements using selection sort, in the worst case?
A) \(\Theta(n)\)

B) \(\Theta(\log n)\)

C) \(\Theta(n^2)\)

D) \(\Theta(n^2\log n)\)

Things you need to know

Refer : http://www.techtud.com/video-lecture/selection-sort-algorithm-and-analysis

Now, if you look at the algorithm of selection sort:

Void SelectionSort (int*arr, int n)
{
   for (int i=0; i<n-1; ++i)
   {
        int minIdx = i;
        for(int j = i+1; j<n; ++j)
        {
             if (arr[j] < arr[minIdx)
                  minIdx = j;
         }
         if (minIdx != i)
             swap (arr, i, minIdx);
    }
}  

 

We are finding the minimum among the numbers, in each iteration placing it at the appropritate position. 

No. of swaps required to place one number at its proper position is = \(\Theta(1)\)

\(\therefore\) For \(n\) numbers total number of swaps required = \(n*(\Theta(1)) = \Theta(n)\)

Hence, Ans (A)

0Comment

  • This quiz contains 5 questions on the topic Sorting Algorithms -1 (Insertion Sort, Bubble Sort, Selection Sort)
  • Lean well before you attempt the quiz
  • You can attempt the quiz unlimited number of times.

Difficulty Level:  basic