Tutorialspoint.dev

Bucket Sort To Sort an Array with Negative Numbers

We have discussed bucket sort in the main post on Bucket Sort .
Bucket sort is mainly useful when input is uniformly distributed over a range. For example, consider the problem of sorting a large set of floating point numbers which are in range from 0.0 to 1.0 and are uniformly distributed across the range. In the above post, we have discussed Bucket Sort to sort numbers which are greater than zero.

How to modify Bucket Sort to sort both positive and negative numbers?

Example:

Input : arr[] = { -0.897, 0.565, 0.656, -0.1234, 0, 0.3434 } 
Output : -0.897 -0.1234  0 0.3434 0.565 0.656 



Here we considering number is in range -1.0 to 1.0 (floating point number)
Algorithm :

sortMixed(arr[], n)
1) Split array into two parts 
   create two Empty vector Neg[], Pos[] 
   (for negative and positive element respectively)
   Store all negative element in Neg[] by converting
   into positive (Neg[i] = -1 * Arr[i] )
   Store all +ve in pos[]  (pos[i] =  Arr[i])
2) Call function bucketSortPositive(Pos, pos.size())
   Call function bucketSortPositive(Neg, Neg.size())

bucketSortPositive(arr[], n)
3) Create n empty buckets (Or lists).
4) Do following for every array element arr[i]. 
       a) Insert arr[i] into bucket[n*array[i]]
5) Sort individual buckets using insertion sort.
6) Concatenate all sorted buckets. 

Below is c++ implementation of above idea (for floating point number )

// C++ program to sort an array of positive
// and negative numbers using bucket sort
#include <bits/stdc++.h>
using namespace std;
  
// Function to sort arr[] of size n using
// bucket sort
void bucketSort(vector<float> &arr, int n)
{
    // 1) Create n empty buckets
    vector<float> b[n];
  
    // 2) Put array elements in different
    //    buckets
    for (int i=0; i<n; i++)
    {
        int bi = n*arr[i]; // Index in bucket
        b[bi].push_back(arr[i]);
    }
  
    // 3) Sort individual buckets
    for (int i=0; i<n; i++)
        sort(b[i].begin(), b[i].end());
  
    // 4) Concatenate all buckets into arr[]
    int index = 0;
    arr.clear();
    for (int i = 0; i < n; i++)
        for (int j = 0; j < b[i].size(); j++)
            arr.push_back(b[i][j]);
}
  
// This function mainly slpits array into two
// and then calls bucketSort() for two arrays.
void sortMixed(float arr[], int n)
{
    vector<float>Neg ;
    vector<float>Pos;
  
    // traverse array elements
    for (int i=0; i<n; i++)
    {
        if (arr[i] < 0)
  
            // store -Ve elements by
            // converting into +ve element
            Neg.push_back (-1 * arr[i]) ;
        else
            // store +ve elements
            Pos.push_back (arr[i]) ;
    }
  
    bucketSort(Neg, (int)Neg.size());
    bucketSort(Pos, (int)Pos.size());
  
    // First store elements of Neg[] array
    // by converting into -ve
    for (int i=0; i < Neg.size(); i++)
        arr[i] = -1 * Neg[ Neg.size() -1 - i];
  
    // store +ve element
    for(int j=Neg.size(); j < n; j++)
        arr[j] = Pos[j - Neg.size()];
}
  
/* Driver program to test above function */
int main()
{
    float arr[] = {-0.897, 0.565, 0.656,
                   -0.1234, 0, 0.3434};
    int n = sizeof(arr)/sizeof(arr[0]);
    sortMixed(arr, n);
  
    cout << "Sorted array is ";
    for (int i=0; i<n; i++)
        cout << arr[i] << " ";
    return 0;
}

Output:

Sorted array is 
-0.897  -0.1234 0 0.3434 0.565 0.656 

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.



This article is attributed to GeeksforGeeks.org

leave a comment

code

0 Comments

load comments

Subscribe to Our Newsletter