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