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

7 afișare

© 2018 by The Art Of Coding. by Oana Unciuleanu

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