Insertion Sort


1. Algorithm

- See sequence of one element is a0 orderly sequence.
- Add orderly sequence a1 to a0 such that new sequence a0, a1 is ordered sequence. If a1 <a0 we permutations a1 to a0.
- Add a2 in orderly sequence a0, a1 a0 so that new ranges, a1, a2 are orderly sequence.
- Continue to n-1 such steps would have ordered sequence a0, a1, ..., an-1

Insertion_Sort_example_1

2. Source Code 

#include <iostream>
#include <conio.h>
#define max 100
using namespace std;
//Input Array
void InputArray(int A[],int n){
for(int i=0; i<n; i++) {
cout<<"Input element A["<<i<<"] =";
cin>>A[i];
}
}

//Print Array
void PrintArray(int A[],int n){
cout<<endl;
for(int i=0; i<n; i++)
cout<<A[i]<<"\t";
}
//Swap 2 elements
void Swap(int &a,int &b) {
int temp = a;
a = b;
b = temp;
}
//Insertion Sort Algorithm
void InsertionSort(int A[],int n) {
for(int i=1; i<n; i++)
for(int j=i; j>0; j--)
if(A[j]<A[j-1])
Swap(A[j],A[j-1]);
}
//Main Function
int main() {
int A[max],n;
cout<<"Input number of array:";
cin>>n;
InputArray(A,n);
cout<<"\nOriginal Array:";
PrintArray(A,n);
cout<<endl;
InsertionSort (A,n);
cout<<"\nSorted Array:";
PrintArray(A,n);
getch();
return 0;
}

3. Result

Insertion_Sort_example


Advertisements