Insertion Sort In C++
Insertion sort is a simple sorting algorithm that
works similar to the way you sort playing cards in your hands. The array is
virtually split into a sorted and an unsorted part. Values from the unsorted
part are picked and placed at the correct position in the sorted part.
Algorithm
To sort an array of size n in ascending order:
1: Iterate from arr[1] to arr[n] over the array.
2: Compare the current element (key) to its predecessor.
3: If the key element is smaller than its predecessor, compare it to the
elements before. Move the greater elements one position up to make space for
the swapped element.
Fig: Insertion Sort In C++ |
Program:
#include<iostream.h>
#include<conio.h>
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;
}
void main()
{
int arr[] = { 12, 11, 13, 5, 6 };
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
printArray(arr, n);
getch();
}
Output:
5 6
11 12 13
No comments:
Post a Comment