Algorithms

Bucket Sort



Implementation of Bucket Sort

# function for bucket sort
def bucketsort(MyList):   
    bucket_number = 10
    bucket = []

    #creating empty buckets
    for i in range(bucket_number):
      bucket.append([])
    
    #transfer elements of list into respective bucket
    for i in MyList:
      b_index = int(i*10)
      bucket[b_index].append(i) 
    
    #sort all elements of each bucket
    for i in range(bucket_number):
      bucket[i] = sorted(bucket[i])

    k = 0
    #combine all buckets to create sorted list
    for i in range(bucket_number):
      for j in bucket[i]:
        MyList[k] = j
        k = k + 1

# function to print list
def PrintList(MyList):
  for i in MyList:
    print(i, end=" ")
  print("\n")

# test the code                 
MyList = [0.18, 0.58, 0.93, 0.05, 0.12, 0.67, 0.55, 0.51]
print("Original List")
PrintList(MyList)

bucketsort(MyList)
print("Sorted List")
PrintList(MyList)

The above code will give the following output:

Original List
0.18 0.58 0.93 0.05 0.12 0.67 0.55 0.51 

Sorted List
0.05 0.12 0.18 0.51 0.55 0.58 0.67 0.93 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

  // function for bucket sort
  static void bucketsort(float Array[], int n) 
  {
    int bucket_number = 10;

    //creating empty buckets
    vector<float> bucket[bucket_number];

    //transfer elements of array into respective bucket
    for (int i = 0; i < n; i++)
    {
      bucket[int(Array[i] * 10)].push_back(Array[i]);
    }

    //sort all elements of each bucket
    for (int i = 0; i < bucket_number; i++)
    {
      sort(bucket[i].begin(), bucket[i].end());
    }

    //combine all buckets to create sorted list
    int k = 0;
    for (int i = 0; i < bucket_number; i++)
    {
      for (int j = 0; j < bucket[i].size(); j++)
      { Array[k++] = bucket[i][j]; }
    }
  }

  // function to print array
  static void PrintArray(float Array[], int n) 
  { 
    for (int i=0; i<n; i++) 
    {  
      cout<<Array[i]<<" "; 
    }
    cout<<"\n"; 
  } 

 // test the code
 int main (){
    float MyArray[] = {0.18, 0.58, 0.93, 0.05, 0.12, 0.67, 0.55, 0.51};
    int n = sizeof(MyArray) / sizeof(MyArray[0]); 
    cout<<"Original Array\n";
    PrintArray(MyArray, n);

    bucketsort(MyArray, n);
    cout<<"\nSorted Array\n";
    PrintArray(MyArray, n);
    return 0;
 }

The above code will give the following output:

Original Array
0.18 0.58 0.93 0.05 0.12 0.67 0.55 0.51 

Sorted Array
0.05 0.12 0.18 0.51 0.55 0.58 0.67 0.93