## Sunday, December 4, 2011

### Data Structure: How to implement Straight Insertion Sort in C++?

An insertion sort is that which sort a record of data by inserting records into an existing sorted file. The list is divided into two parts: sorted and unsorted. In each pass, the first element of the unsorted sub-list is inserted into the sorted sub-list in proper position.

Algorithm

1. Declare and initialize necessary variable such as array[], n, i, j etc2. Insert each x[k] into sorted file i.e.      for k = 1 to k < n, repeat         temp = x[k]        2.1 Move down one position all elements greater than temp i.e.                for ( i = k-1; i >= i && temp < x[i]; i--)                   x[i+1]=x[i]        2.2 x[i+1] = temp3. Display the sorted array.In this algorithm, we take x[0] as sorted file initially

Source Code:

#include<iostream>using namespace std;class InsertionSort{    private:        int no_of_elements;        int elements[10];    public:        void getarray();        void sortit();        void display();};void InsertionSort::getarray(){    cout<<"How many elements? ";    cin>>no_of_elements;    cout<<"Insert array of element to sort: ";    for(int i = 0; i < no_of_elements; i++){        cin>>elements[i];    }}void InsertionSort::sortit(){    int temp, i , j;    for(i = 0; i < no_of_elements; i++){        temp = elements[i];        for(j = i-1; j >= 0 && temp < elements[j]; j--){            elements[j+1] = elements[j];        }        elements[j+1] = temp;        cout<<"Iteration "<<i+1<<" : ";        display();    }}void InsertionSort::display(){    for(int i = 0 ; i < no_of_elements; i++){        cout<<elements[i]<<" ";    }    cout<<endl;}int main(){    InsertionSort IS;    IS.getarray();    IS.sortit();    return 0;}

Output

How many elements? 6
Insert array of element to sort: 52 36 96 12 58 3
Iteration 1 : 52 36 96 12 58 3
Iteration 2 : 36 52 96 12 58 3
Iteration 3 : 36 52 96 12 58 3
Iteration 4 : 12 36 52 96 58 3
Iteration 5 : 12 36 52 58 96 3
Iteration 6 : 3 12 36 52 58 96

Efficiency of Straight Insertion sort

Efficiency of Straight Insertion sort is O(n^2)