# 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 as sorted file initially`

Source Code:

```#include

using namespace std;

class InsertionSort{
private:
int no_of_elements;
int elements;
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 Posts October 4, 2012 Data Structure How to implement Straight Insertion Sort in C October 2, 2012 Data Structure How to implement Straight Selection Sort in C October 6, 2012 Data Structure How to implement Merge Sort in C October 7, 2012 Data Structure How to implement Shell Sort in C October 8, 2012 Data Structure Implementing Tree Sort in CZemanta

```