# 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**

2. 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] = temp

3. 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)