Insertion Sort algorithm is a sorting technique that arranges elements in an array. Many people compare it to the way that we sort playing cards in our hand. Meaning that we sort cards one by one, when we introduce a new card, we insert it precisely at its position, comparing it to the rest of the cards. So, in our existing sorted set we make space for the new value, in the right order.
// Insertion Sort
#include <iostream>
using namespace std;
void insertionSort(int arrayOfNumbers[], int numberOfElements)
{
int currentValue;
int j;
for (int i = 1; i < numberOfElements; i++)
{
// Take each value
currentValue = arrayOfNumbers[i];
j = i - 1;
// Move the elements
while (j >= 0 && arrayOfNumbers[j] > currentValue)
{
arrayOfNumbers[j + 1] = arrayOfNumbers[j];
j = j - 1;
}
// Insert in the right place
arrayOfNumbers[j + 1] = currentValue;
}
}
void printElementsOfArray(int arrayOfNumbers[], int numberOfElements)
{
for (int i = 0; i < numberOfElements; ++i)
{
cout << arrayOfNumbers[i] << " ";
}
cout << endl;
}
int main(void)
{
int arrayOfNumbers[] = {4, 7, 9, 3, 21, 18, 23, 15, 8, 17};
int numberOfElements = sizeof(arrayOfNumbers) / sizeof(arrayOfNumbers[0]);
insertionSort(arrayOfNumbers, numberOfElements);
cout<<"The sorted array is: \n";
printElementsOfArray(arrayOfNumbers, numberOfElements);
}
Comments