The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

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