top of page
Caută
Poza scriitoruluioanaunciuleanu

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

146 afișări0 comentarii

Postări recente

Afișează-le pe toate

Tiling Problem in JAVA

You can use a board that is 2 x n size. The tiles are of size 2 x 1. Count the number of ways to tile the board. Tiles can be placed...

Kommentarer


bottom of page