Caută
  • oanaunciuleanu

Insertion Sort Algorithm in C++




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);
}

© 2018 by The Art Of Coding. by Oana Unciuleanu

This site was designed with the
.com
website builder. Create your website today.
Start Now