Sorting

Problem 
Implement the Insertion sort algorithm.

Solution 
This algorithm works by taking elements from an unsorted array one by one and inserting them in their proper position in the new sorted array. This invloves comparison and shifting operation.
Complexity of the algorithm is O(n2).
Consider the following array { 7, 2, 5, 3, 4 }. Let’s see how Insertion sort technique works :-

First Iteration :: { 7, 2, 5, 3, 4 } -> { 2, 7, 5, 3, 4 } ( 2 is placed in its proper position and 7 is shifted )

Second Iteration :: { 2, 7, 5, 3, 4 } -> { 2, 5, 7, 3, 4 } ( 5 is placed in its proper position and 7 is shifted )

Third Iteration :: { 2, 5, 7, 3, 4 } -> { 2, 3, 5, 7, 4 } ( 3 is placed in its proper position and 5 & 7 are shifted )

Fourth Iteration :: { 2, 3, 5, 7, 4 } -> { 2, 3, 4, 5, 7 } ( 4 is placed in its proper position and 5 & 7 are shifted )

#include<iostream>
using namespace std;

// Display the Array
void displayArray(int arr[], int size) {
   int i;
   for (i=0;i<size;i++) {
      cout<<arr[i]<<" ";
   }
}

// swap elements in the array
void swap(int arr[],int idx1,int idx2) {
   int temp;
   temp = arr[idx1];
   arr[idx1] = arr[idx2];
   arr[idx2] = temp;
}

// insertion sort
void insertionSort(int arr[],int size) {
   int i,j;
   // select elements one by one and insert them in 
   // their proper position in the sorted array
   for (i=1;i<size;i++) {
      j = i;
      // iterate and shift leftwards till we find the 
      // first element less than the selected element
      while (j > 0 && arr[j] < arr[j-1]) {
         swap(arr,j,j-1);
         j--;
      }
   }
}

// main
int main() {
   int arr[] = {7,4,5,2,3,19,11,6,9,12,8};
   int size = sizeof(arr)/sizeof(arr[0]);
   cout<<"\nOriginal Array :: ";
   displayArray(arr,size);
   insertionSort(arr,size);
   cout<<"\nSorted Array   :: ";
   displayArray(arr,size);
   cout<<endl;
   return 0;
}

Back | Next

All problems on Sorting
* Implement the Bubble Sort algorithm
* Implement the Selection Sort algorithm
* Implement the Insertion Sort algorithm
* Implement the Merge Sort algorithm
* Implement the Quick Sort algorithm
About    Contact    Sitemap    Terms    Privacy