Caută
  • oanaunciuleanu

Pigeonhole Sort Algorithm in C++


Pigeonhole is a sorting algorithm. It works best if the number of elements in the array and the number of keys is similar. It is a non-comparison sorting technique. For solving this algorithm, we must make some “holes” where we can store values. The number of holes is decided by the range of values. We will store there the temporary values associated with the index, and in the end, we move the values in the final array.


// Pigeonhole Sort

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

void pigeonholeSort(int arrayOfNumbers[], int numberOfElements)
{
    // Find the min and max values
    int minimum = arrayOfNumbers[0];
    int maximum = arrayOfNumbers[0];
    for (int i = 1; i < numberOfElements; i++)
    {
        if (arrayOfNumbers[i] < minimum)
        {
            minimum = arrayOfNumbers[i];
        }
        if (arrayOfNumbers[i] > maximum)
        {
            maximum = arrayOfNumbers[i];
        }
    }
    // Calculate the range
    int range = maximum - minimum + 1;

    // Create the pigeonholes
    vector<int> holes[range];

    // Put elements in their hole
    for (int i = 0; i < numberOfElements; i++)
    {
        holes[arrayOfNumbers[i] - minimum].push_back(arrayOfNumbers[i]);
    }

    // Put the sorted elements back to the array
    int index = 0;
    for (int i = 0; i < range; i++)
    {
        vector<int>::iterator it;
        for (it = holes[i].begin(); it != holes[i].end(); ++it)
        {
            arrayOfNumbers[index++] = *it;
        }
    }
}
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]);

  pigeonholeSort(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