Caută
  • oanaunciuleanu

Bucket Sort in C++


The Bucket Sort algorithm is used for sorting arrays that have values equally distributed inside a range. We create a few buckets for values, for instance one bucket holds the numbers from 0 to 4, the next from 5 to 9, then from 10 to 14. After inserting the corresponding elements inside, we must sort them. In the end we put all the buckets together, in a sorted manner.



// Bucket Sort

#include <iostream>
using namespace std;


struct bucket
{
    int howMany;
    int* value;
};

// Used for sorting
int compareIntegers(const void* first, const void* second)
{
    int x = *((int*)first), y =  *((int*)second);
    if (x == y)
    {
        return 0;
    }
    else if (x < y)
    {
        return -1;
    }
    else
    {
        return 1;
    }
}

void bucketSort(int arrayOfNumbers[],int numberOfElements, int numberOfBuckets)
{
    //Create the buckets
    struct bucket buckets[numberOfBuckets];
    for (int i = 0; i < numberOfBuckets; i++)
    {
        buckets[i].howMany = 0;
        buckets[i].value = (int*)malloc(sizeof(int) * numberOfElements);
    }

    // Add values to buckets
    for (int i = 0; i < numberOfElements; i++)
    {
        if (arrayOfNumbers[i] < 10)
        {
            buckets[0].value[buckets[0].howMany++] = arrayOfNumbers[i];
        }
        else if (arrayOfNumbers[i] > 20)
        {
            buckets[2].value[buckets[2].howMany++] = arrayOfNumbers[i];
        }
        else
        {
            buckets[1].value[buckets[1].howMany++] = arrayOfNumbers[i];
        }
    }

    // Sort the elements in a bucket
    for (int k = 0, i = 0; i < numberOfBuckets; i++)
    {
        qsort(buckets[i].value, buckets[i].howMany, sizeof(int), &compareIntegers);
        for (int j = 0; j < buckets[i].howMany; j++)
        {
            arrayOfNumbers[k + j] = buckets[i].value[j];
        }
        k += buckets[i].howMany;
        free(buckets[i].value);
    }
}

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]);
  int numberOfBuckets = 3;

  bucketSort(arrayOfNumbers, numberOfElements, numberOfBuckets);
  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