Tutorial 24

 ---- 24 Insertion sort

//---- Method 1

#include <bits/stdc++.h>

using namespace std;

void insertionSort(int arr[], int n)

{

int i, key, j;

for (i = 1; i < n; i++) 

    {

key = arr[i];

j = i - 1;

while (j >= 0 && arr[j] > key) 

        {

arr[j + 1] = arr[j];

j = j - 1;

}

arr[j + 1] = key;

}

}

void printArray(int arr[], int n)

{

int i;

for (i = 0; i < n; i++)

cout << arr[i] << " ";

cout << endl;

}

// Driver code

int main()

{

int arr[] = { 12, 11, 13, 5, 6 };

int N = sizeof(arr) / sizeof(arr[0]);

insertionSort(arr, N);

printArray(arr, N);

return 0;

}

//----Method 2

#include<iostream>  

using namespace std;  

int main ()  

{    

    int myarray[10] = {12,4,3,1,15,45,33,21,10,2};   

       

    cout<<"\nInput list is \n";

    for(int i=0;i<10;i++)  

    {  

        cout <<myarray[i]<<"\t";  

    }    

    for(int k=1; k<10; k++)   

    {  

        int temp = myarray[k];  

        int j= k-1;  

        while(j>=0 && temp <= myarray[j])  

        {  

            myarray[j+1] = myarray[j];   

            j = j-1;  

        }  

        myarray[j+1] = temp;  

    }  

    cout<<"\nSorted list is \n";

    for(int i=0;i<10;i++)  

    {  

        cout <<myarray[i]<<"\t";  

    }  

    return 0;

}