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 etc
2. Insert each x[k] into sorted file i.e.
for k = 1 to k 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+1]=x[i]
2.2 x[i+1] = temp
3. Display the sorted array.
In this algorithm, we take x[0] as sorted file initially

Source Code:

 
#include
 
 
 
using namespace std;
 
 
 
class InsertionSort{
 
    private:
 
        int no_of_elements;
 
        int elements[10];
 
    public:
 
        void getarray();
 
        void sortit();
 
        void display();
 
};
 
 
 
void InsertionSort::getarray(){
 
    coutHow many elements? ";
 
    cin>>no_of_elements;
 
    coutInsert array of element to sort: ";
 
    for(int i = 0; i 
 
        cin>>elements[i];
 
    }
 
}
 
 
 
void InsertionSort::sortit(){
 
    int temp, i , j;
 
    for(i = 0; i 
 
        temp = elements[i];
 
        for(j = i-1; j >= 0 && temp 
 
            elements[j+1] = elements[j];
 
        }
 
        elements[j+1] = temp;
 
        coutIteration " : ";
 
        display();
 
    }
 
}
 
 
 
void InsertionSort::display(){
 
    for(int i = 0 ; i 
 
        cout ";
 
    }
 
    cout
 
}
 
 
 
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)