4
Q:

java bucket sort

public static int[] bucketSort(int[] a) {
  Queue<Integer>[] buckets = fillBuckets(a);
  int[] sorted = readBuckets(buckets);
  return sorted;
}

public static Queue<Integer>[] fillBuckets(int[] array) {
  if(array.length == 0){
    Queue<Integer>[] r = new Queue[0];
    return r;
  }
  int vmin = array[0];
  int vmax = array[0];
  for(int i = 0; i < array.length; i++){
    if(array[i] > vmax){
      vmax = array[i];
    }
    if(array[i] < vmin){
      vmin = array[i];
    }
  }
  Queue<Integer>[] buckets = new Queue[vmax - vmin + 1];
  for(int i = 0; i < buckets.length; i++){
    buckets[i] = new LinkedList<Integer>();
  }
  for(int i = 0; i < array.length; i++){
    buckets[array[i] - vmin].add(array[i]);
  }
  return buckets;
}

public static int[] readBuckets(Queue<Integer>[] buckets) {
  if(buckets.length == 0){
    int[] e = new int[0];
    return e;
  }
  ArrayList<Integer> a = new ArrayList<Integer>();
  for(int i = 0 ; i < buckets.length; i++){
    while(buckets[i].peek() != null){
      a.add(buckets[i].remove());
    }
  }
  int[] result = new int[a.size()];
  for(int i = 0; i < a.size(); i++){
    result[i] = a.get(i);
  }
  return result;
}
1
// C++ program to sort an array using bucket sort 
#include <iostream> 
#include <algorithm> 
#include <vector> 
using namespace std; 
  
// Function to sort arr[] of size n using bucket sort 
void bucketSort(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; 
    for (int i = 0; i < n; i++) 
        for (int j = 0; j < b[i].size(); j++) 
          arr[index++] = b[i][j]; 
} 
  
/* Driver program to test above funtion */
int main() 
{ 
    float arr[] = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    bucketSort(arr, n); 
  
    cout << "Sorted array is \n"; 
    for (int i=0; i<n; i++) 
       cout << arr[i] << " "; 
    return 0; 
} 
0

New to Communities?

Join the community