# Data Structure How to implement Straight Insertion Sort in C

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

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 "< : ";
display();
}
}

void InsertionSort::display(){
for(int i = 0 ; i < no_of_elements; i++){
cout< ";
}
cout<
}

int main(){
InsertionSort IS;
IS.getarray();
IS.sortit();
return 0;
}

Output

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

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

Related PostsOctober 4, 2012 Data Structure How to implement Straight Insertion Sort in COctober 2, 2012 Data Structure How to implement Straight Selection Sort in COctober 6, 2012 Data Structure How to implement Merge Sort in COctober 7, 2012 Data Structure How to implement Shell Sort in COctober 8, 2012 Data Structure Implementing Tree Sort in CZemanta

```