Posted on by Kalkicode
Code Sorting

Bucket Sort

Bucket sort is a sorting algorithm that works by distributing the elements of an array into a number of buckets or bins. Each bucket is then sorted individually, either using another sorting algorithm or by recursively applying the bucket sort algorithm. After all the buckets are sorted, they are concatenated to form a final sorted array.

The basic idea of bucket sort is to divide an array into smaller arrays or buckets, with each bucket capable of holding a range of values. The range of values in each bucket should be such that no two elements in the same bucket are greater than the range of the bucket. For example, if the range of the values in the array is from 0 to 999, and there are 10 buckets, then each bucket can hold a range of 100 values (bucket 1 holds 0-99, bucket 2 holds 100-199, and so on).

The elements in the array are then placed into their corresponding buckets based on their values. Once all the elements have been placed into buckets, each bucket is sorted individually, either using another sorting algorithm or by recursively applying the bucket sort algorithm. After all the buckets are sorted, the elements are concatenated in order to form a final sorted array.

The time complexity of bucket sort depends on the sorting algorithm used to sort the buckets, as well as the distribution of the values in the array. In the best case scenario, where the values are evenly distributed among the buckets, the time complexity is O(n). However, in the worst case scenario, where all the values are in the same bucket, the time complexity is O(n^2).

Bucket sort is useful when the range of values in the array is known beforehand and is relatively small compared to the size of the array. It is also useful when the values in the array are uniformly distributed, since this ensures that the buckets will be approximately the same size and the time complexity will be optimal.

Here given code implementation process.

/*
 C++ Program
 Sort the Array elements using bucket Sort
*/

#include<iostream>

using namespace std;

// This are storing information about array element
class Node {
  public:
  int data;
  Node *next;
  Node(int data) {
    this->data = data;
    this->next = NULL;
  }
};
class BucketSort {
  public:
  Node **slot;
  BucketSort(int size) {
    // First create auxiliary memory to Bucket type
    // Which is store the information of sort element
    slot = new Node*[size];
    //Set that initial have no element in bucket

    for (int i = 0; i < size; i++) {
      slot[i] = NULL;
    }
  }
  //Get the location of array elements
  int location(int data, int element, int max_value) {
    return data *element / (max_value + 1);
  }
  //Find the maximum element in given array
  int maximum_element(int arr[], int size) {
    int max_value = arr[0];
    for (int i = 1; i < size; ++i) {
      if (max_value < arr[i]) {
        max_value = arr[i];
      }
    }
    return max_value;
  }
  void sorted_add(Node *auxiliary, int data) {
    //Find node to insert new element
    while (auxiliary != NULL && auxiliary->next != NULL && auxiliary->next->data <= data) {
      auxiliary = auxiliary->next;
    }
    //Create new node and fit into bucket
    Node *node = new Node(data);
    node->next = auxiliary->next;
    auxiliary->next = node;
  }
  void bucket_sort(int arr[], int size) {
    if (size <= 0) {
      return;
    }
    // We are need to find maximum element in array 
    // Because calculation is based on max element value
    int max_value = this->maximum_element(arr, size);
    //Some variables which are using to perform sorting execution
    Node *auxiliary = NULL, *temp = NULL;
    int index = 0;
    for (int i = 0; i < size; ++i) {
      index = this->location(arr[i], size, max_value);
      // check given slot are null or not

      if (this->slot[index] == NULL) {
        // inserting first element in given (index) slot
        this->slot[index] = new Node(arr[i]);
      } else {
        // In this case slots are not empty then get first node in slot
        auxiliary = this->slot[index];
        if (auxiliary->data >= arr[i]) {
          //add new node at first position in bucket
          temp = new Node(arr[i]);
          temp->next = auxiliary;
          this->slot[index] = temp;
        } else {
          //otherwise add node in sorted way
          this->sorted_add(auxiliary, arr[i]);
        }
      }
    }
    //Assign slot value into actual array

    for (int i = 0, j = 0; i < size && j < size; ++i) {
      if (this->slot[i] != NULL) {
        auxiliary = this->slot[i];
        //Check if bucket slot empty or not
        while (auxiliary != NULL) {
          arr[j] = auxiliary->data;
          auxiliary = auxiliary->next;
          j++;
        }
      }
    }
  }
  //Display array element
  void display(int arr[], int size) {
    for (int i = 0; i < size; ++i) {
      //print array element value

      cout << "  " << arr[i];
    }
    cout << "\n";
  }
};
int main() {
   //Array which are sorting by using bucket sort
  int arr[] = {8,3,8,1,3,73,-3,121,54,23,84,13,67,23,52};
  //Get the size of array
  int size = sizeof(arr)/sizeof(arr[0]);
  BucketSort obj(size);
  //sort element
  obj.bucket_sort(arr, size);
  //display array element
  obj.display(arr, size);
  return 0;
}

Output

  -3  1  3  3  8  8  13  23  23  52  54  67  73  84  121
/*
  Java Program
   Sort the Array elements using bucket Sort
*/
// This are storing information about array element
class Node {

  public int data;

  public Node next;

  public Node(int data) {
    this.data = data;
    this.next = null;
  }
}


public class BucketSort {

  public Node[] slot;

  public BucketSort(int size) {
    // First create auxiliary memory to Bucket type
    // Which is store the information of sort element
    slot = new Node[size];

    //Set that initial have no element in bucket
    for (int i = 0; i < size; i++) {
      slot[i] = null;
    }
  }

  //Get the location of array elements
  public int location(int data, int element, int max_value) {
    return data*element / (max_value + 1);
  }
  //Find the maximum element in given array
  public int maximum_element(int []arr, int size) {

    int max_value = arr[0];
    for (int i = 1; i < size; ++i) {
      if (max_value < arr[i]) {
        max_value = arr[i];
      }

    }
    return max_value;
  }

  public void sorted_add(Node auxiliary, int data) {
    //Find node to insert new element
    while (auxiliary != null && auxiliary.next != null && auxiliary.next.data <= data) {
      auxiliary = auxiliary.next;
    }
    //Create new node and fit into bucket
    Node node = new Node(data);
    node.next = auxiliary.next;
    auxiliary.next = node;
  }

  public void bucket_sort(int []arr, int size) {
    if (size <= 0) {
      return;
    }


    // We are need to find maximum element in array 
    // Because calculation is based on max element value
    int max_value = maximum_element(arr, size);

    //Some variables which are using to perform sorting execution
    Node auxiliary = null, temp = null;

    int index = 0;


    for (int i = 0; i < size; ++i) {
      index = location(arr[i], size, max_value);
      // check given slot are null or not
      if (slot[index] == null) {
        // inserting first element in given (index) slot
        slot[index] = new Node(arr[i]);
      } else {
        // In this case slots are not empty then get first node in slot
        auxiliary = slot[index];

        if (auxiliary.data >= arr[i]) {
          //add new node at first position in bucket
          temp = new Node(arr[i]);
          temp.next = auxiliary;
          slot[index] = temp;

        } else {
          //otherwise add node in sorted way
          sorted_add(auxiliary, arr[i]);
        }
      }
    }
    //Assign slot value into actual array
    for (int i = 0, j = 0; i < size && j < size; ++i) {
      if (slot[i] != null) {
        auxiliary = slot[i];
        //Check if bucket slot empty or not
        while (auxiliary != null) {

          arr[j] = auxiliary.data;
          auxiliary = auxiliary.next;
          j++;
        }

      }
    }
  }
  //Display array element
  public void display(int []arr, int size) {
    for (int i = 0; i < size; ++i) {
      //print array element value
      System.out.print("  " + arr[i]);
    }
    System.out.print("\n");
  }

  public static void main(String[] args) {

    //Array which are sorting by using bucket sort
    int[] arr = {8,3,8,1,3,73,-3,121,54,23,84,13,67,23,52};
    //Get the size of array
    int size = arr.length;

    BucketSort obj = new BucketSort(size);
    //sort element
    obj.bucket_sort(arr, size);

    //display array element
    obj.display(arr, size);
  }
}

Output

  -3  1  3  3  8  8  13  23  23  52  54  67  73  84  121
Demonstration of Bucket Sort
/*
  C# Program
   Sort the Array elements using bucket Sort
*/
using System;
// This are storing information about array element
public class Node {

  public int data;

  public Node next;

  public Node(int data) {
    this.data = data;
    this.next = null;
  }
}


public class BucketSort {

  public Node[] slot;

  public BucketSort(int size) {
    // First create auxiliary memory to Bucket type
    // Which is store the information of sort element
    slot = new Node[size];

    //Set that initial have no element in bucket
    for (int i = 0; i < size; i++) {
      slot[i] = null;
    }
  }

  //Get the location of array elements
  public int location(int data, int element, int max_value) {
    return data*element / (max_value + 1);
  }
  //Find the maximum element in given array
  public int maximum_element(int []arr, int size) {

    int max_value = arr[0];
    for (int i = 1; i < size; ++i) {
      if (max_value < arr[i]) {
        max_value = arr[i];
      }

    }
    return max_value;
  }

  public void sorted_add(Node auxiliary, int data) {
    //Find node to insert new element
    while (auxiliary != null && auxiliary.next != null && auxiliary.next.data <= data) {
      auxiliary = auxiliary.next;
    }
    //Create new node and fit into bucket
    Node node = new Node(data);
    node.next = auxiliary.next;
    auxiliary.next = node;
  }

  public void bucket_sort(int []arr, int size) {
    if (size <= 0) {
      return;
    }


    // We are need to find maximum element in array 
    // Because calculation is based on max element value
    int max_value = maximum_element(arr, size);

    //Some variables which are using to perform sorting execution
    Node auxiliary = null, temp = null;

    int index = 0;


    for (int i = 0; i < size; ++i) {
      index = location(arr[i], size, max_value);
      // check given slot are null or not
      if (slot[index] == null) {
        // inserting first element in given (index) slot
        slot[index] = new Node(arr[i]);
      } else {
        // In this case slots are not empty then get first node in slot
        auxiliary = slot[index];

        if (auxiliary.data >= arr[i]) {
          //add new node at first position in bucket
          temp = new Node(arr[i]);
          temp.next = auxiliary;
          slot[index] = temp;

        } else {
          //otherwise add node in sorted way
          sorted_add(auxiliary, arr[i]);
        }
      }
    }
    //Assign slot value into actual array
    for (int i = 0, j = 0; i < size && j < size; ++i) {
      if (slot[i] != null) {
        auxiliary = slot[i];
        //Check if bucket slot empty or not
        while (auxiliary != null) {

          arr[j] = auxiliary.data;
          auxiliary = auxiliary.next;
          j++;
        }

      }
    }
  }
  //Display array element
  public void display(int []arr, int size) {
    for (int i = 0; i < size; ++i) {
      //print array element value
      Console.Write("  " + arr[i]);
    }
    Console.Write("\n");
  }

  public static void Main(String[] args) {

    //Array which are sorting by using bucket sort
    int[] arr = {8,3,8,1,3,73,-3,121,54,23,84,13,67,23,52};
    //Get the size of array
    int size = arr.Length;

    BucketSort obj = new BucketSort(size);
    //sort element
    obj.bucket_sort(arr, size);

    //display array element
    obj.display(arr, size);
  }
}

Output

  -3  1  3  3  8  8  13  23  23  52  54  67  73  84  121
# Python 3 Program
# Sort the Array elements using bucket Sort


#  This are storing information about array element

class Node :
  
  def __init__(self, data) :
    self.data = data
    self.next = None
  

class BucketSort :
  
  def __init__(self,size) :
    #  Which is store the information of sort element

    #  First create auxiliary memory to Bucket type
    self.slot = [None]*size
    i = 0
    # Set that initial have no element in bucket
    while (i < size) :
      self.slot[i] = None
      i += 1
    
  
  # Get the location of array elements
  def location(self, data, element, max_value) :
    return int(data * element / (max_value + 1))
  
  # Find the maximum element in given array
  def maximum_element(self, arr, size) :
    max_value = arr[0]
    i = 1
    while (i < size) :
      if (max_value < arr[i]) :
        max_value = arr[i]
      
      i += 1
    
    return max_value
  
  def sorted_add(self, auxiliary, data) :
    # Find node to insert new element
    while (auxiliary != None and auxiliary.next != None and auxiliary.next.data <= data) :
      auxiliary = auxiliary.next
    
    # Create new node and fit into bucket
    node = Node(data)
    node.next = auxiliary.next
    auxiliary.next = node
  
  def bucket_sort(self, arr, size) :
    if (size <= 0) :
      return
    
    #  Because calculation is based on max element value

    #  We are need to find maximum element in array 
    max_value = self.maximum_element(arr, size)
    # Some variables which are using to perform sorting execution
    auxiliary = None
    temp = None
    index = 0
    i = 0
    j = 0
    while (i < size) :
      index = self.location(arr[i], size, max_value)
      #  check given slot are null or not

      if (self.slot[index] == None) :
        #  inserting first element in given (index) slot
        self.slot[index] = Node(arr[i])
      else :
        #  In this case slots are not empty then get first node in slot
        auxiliary = self.slot[index]
        if (auxiliary.data >= arr[i]) :
          # add new node at first position in bucket
          temp = Node(arr[i])
          temp.next = auxiliary
          self.slot[index] = temp
        else :
          # otherwise add node in sorted way
          self.sorted_add(auxiliary, arr[i])
        
      
      i += 1
    
    i = 0
    j = 0
    # Assign slot value into actual array
    while (i < size and j < size) :
      if (self.slot[i] != None) :
        auxiliary = self.slot[i]
        # Check if bucket slot empty or not
        while (auxiliary != None) :
          arr[j] = auxiliary.data
          auxiliary = auxiliary.next
          j += 1
        
      
      i += 1
    
  
  # Display array element
  def display(self, arr, size) :
    i = 0
    while (i < size) :
      # print array element value
      print(" ", arr[i],end="")
      i += 1
    
    print(end="\n")
  

def main() :

  # Array which are sorting by using bucket sort
  arr = [8, 3, 8, 1, 3, 73, -3, 121, 54, 23, 84, 13, 67, 23, 52]
  # Get the size of array
  size = len(arr)
  obj = BucketSort(size)
  # sort element
  obj.bucket_sort(arr, size)
  # display array element
  obj.display(arr, size)

if __name__ == "__main__":
  main()

Output

  -3  1  3  3  8  8  13  23  23  52  54  67  73  84  121
# Ruby Program 
#  Sort the Array elements using bucket Sort

#  This are storing information about array element
class Node 
  # Define the accessor and reader of class Node
  attr_reader :data, :next
    attr_accessor :data, :next
  def initialize(data) 
    self.data = data
    self.next = nil
  end
end

class BucketSort 
  # Define the accessor and reader of class BucketSort
    attr_reader :slot
    attr_accessor :slot
  def initialize(size) 
    #  Which is store the information of sort element

    #  First create auxiliary memory to Bucket type
    @slot = Array.new(size,nil)
    i = 0
    # Set that initial have no element in bucket
    while (i < size) 
      @slot[i] = nil
      i += 1
    end
  end
  # Get the location of array elements
  def location(data, size, max_value) 

    return ((data * size) / (max_value + 1)).to_i
  end
  # Find the maximum element in given array
  def maximum_element(arr, size) 
    max_value = arr[0]
    i = 1
    while (i < size) 
      if (max_value < arr[i]) 
        max_value = arr[i]
      end
      i += 1
    end
    return max_value
  end
  def sorted_add(auxiliary, data) 
    # Find node to insert new element
    while (auxiliary != nil and auxiliary.next != nil and auxiliary.next.data <= data) 
      auxiliary = auxiliary.next
    end
    # Create new node and fit into bucket
    node = Node.new(data)
    node.next = auxiliary.next
    auxiliary.next = node
  end
  def bucket_sort(arr, size) 
    if (size <= 0) 
      return
    end
    #  Because calculation is based on max element value

    #  We are need to find maximum element in array 
    max_value = self.maximum_element(arr, size)
    # Some variables which are using to perform sorting execution
    auxiliary = nil
    temp = nil
    location = 0
    i = 0
    j = 0
    while (i < size) 
      location = self.location(arr[i], size, max_value)
      if(location<0)
        # when unnecessarily producing a invalid index
        # ex : (-3*15 / 121 ) == -0.37190082644
        # but ruby (ruby 2.3) producing -1
        location=0
      end
    
      #  check given slot are null or not

      if (@slot[location] == nil) 
        #  inserting first element in given (location) slot
        @slot[location] = Node.new(arr[i])
      else 
        #  In this case slots are not empty then get first node in slot
        auxiliary = @slot[location]
        if (auxiliary.data >= arr[i]) 
          # add new node at first position in bucket
          temp = Node.new(arr[i])
          temp.next = auxiliary
          @slot[location] = temp
        else 
          # otherwise add node in sorted way
          self.sorted_add(auxiliary, arr[i])
        end
      end
      i += 1
    end
    i = 0
    j = 0
    # Assign slot value into actual array
    while (i < size and j < size) 
      if (@slot[i] != nil) 
        auxiliary = @slot[i]
        # Check if bucket slot empty or not
        while (auxiliary != nil) 
          arr[j] = auxiliary.data
          auxiliary = auxiliary.next
          j += 1
        end
      end
      i += 1
    end
  end
  # Display array element
  def display(arr, size) 
    i = 0
    while (i < size) 
      # print array element value

      print("  ", arr[i])
      i += 1
    end
    print("\n")
  end
end
def main() 

  # Array which are sorting by using bucket sort
  arr = [8, 3, 8, 1, 3, 73, -3, 121, 54, 23, 84, 13, 67, 23, 52]
  # Get the size of array
  size = arr.length
  obj = BucketSort.new(size)
  # sort element
  obj.bucket_sort(arr, size)
  # display array element
  obj.display(arr, size)
end


main()

Output

  -3  1  3  3  8  8  13  23  23  52  54  67  73  84  121
<?php

/*
 Php Program
 Sort the Array elements using bucket Sort
*/

// This are storing information about array element
class Node {
  public $data;
  public $next;

  function __construct($data) {
    $this->data = $data;
    $this->next = null;
  }
}
class BucketSort {
  public $slot;

  function __construct($size) {
    // First create auxiliary memory to Bucket type
    // Which is store the information of sort element
    
    //Set that initial have no element in bucket
    $this->slot = array_fill(0, $size, null);
   
  }
  //Get the location of array elements

  public function location($data, $element, $max_value) {
    return intval($data *$element / ($max_value + 1));
  }
  //Find the maximum element in given array

  public function maximum_element($arr, $size) {
    $max_value = $arr[0];
    for ($i = 1; $i < $size; ++$i) {
      if ($max_value < $arr[$i]) {
        $max_value = $arr[$i];
      }
    }
    return $max_value;
  }
  public function sorted_add($auxiliary, $data) {
    //Find node to insert new element
    while ($auxiliary != null && $auxiliary->next != null && $auxiliary->next->data <= $data) {
      $auxiliary = $auxiliary->next;
    }
    //Create new node and fit into bucket
    $node = new Node($data);
    $node->next = $auxiliary->next;
    $auxiliary->next = $node;
  }
  public function bucket_sort(&$arr, $size) {
    if ($size <= 0) {
      return;
    }
    // We are need to find maximum element in array 
    // Because calculation is based on max element value
    $max_value = $this->maximum_element($arr, $size);
    //Some variables which are using to perform sorting execution
    $auxiliary = null;
    $temp = null;
    $index = 0;
    for ($i = 0; $i < $size; ++$i) {
      $index = $this->location($arr[$i], $size, $max_value);
      // check given slot are null or not

      if ($this->slot[$index] == null) {
        // inserting first element in given (index) slot
        $this->slot[$index] = new Node($arr[$i]);
      } else {
        // In this case slots are not empty then get first node in slot
        $auxiliary = $this->slot[$index];
        if ($auxiliary->data >= $arr[$i]) {
          //add new node at first position in bucket
          $temp = new Node($arr[$i]);
          $temp->next = $auxiliary;
          $this->slot[$index] = $temp;
        } else {
          //otherwise add node in sorted way
          $this->sorted_add($auxiliary, $arr[$i]);
        }
      }
    }
    //Assign slot value into actual array
    for ($i = 0, $j = 0; $i < $size && $j < $size; ++$i) {
      if ($this->slot[$i] != null) {
        $auxiliary = $this->slot[$i];
        //Check if bucket slot empty or not
        while ($auxiliary != null) {
          $arr[$j] = $auxiliary->data;
          $auxiliary = $auxiliary->next;
          $j++;
        }
      }
    }
  }
  //Display array element
  public function display($arr, $size) {
    for ($i = 0; $i < $size; ++$i) {
      //print array element value

      echo ("  ". $arr[$i]);
    }
    echo("\n");
  }
}

function main() {
  //Array which are sorting by using bucket sort
  $arr = array(8, 3, 8, 1, 3, 73, -3, 121, 54, 23, 84, 13, 67, 23, 52);
  //Get the size of array
  $size = count($arr);
  $obj = new BucketSort($size);
  //sort element

  $obj->bucket_sort($arr, $size);
  //display array element

  $obj->display($arr, $size);
}
main();

Output

  -3  1  3  3  8  8  13  23  23  52  54  67  73  84  121
/*
 Node Js Program
 Sort the Array elements using bucket Sort
*/

// This are storing information about array element
class Node {
  
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}
class BucketSort {
  
  constructor(size) {
    // First create auxiliary memory to Bucket type
    // Which is store the information of sort element
    // Set that initial have no element in bucket
    this.slot = Array(size).fill(null);
    
  }
  //Get the location of array elements
  location(data, element, max_value) {
    return parseInt(data *element / (max_value + 1));
  }
  //Find the maximum element in given array
  maximum_element(arr, size) {
    var max_value = arr[0];
    for (var i = 1; i < size; ++i) {
      if (max_value < arr[i]) {
        max_value = arr[i];
      }
    }
    return max_value;
  }
  sorted_add(auxiliary, data) {
    //Find node to insert new element
    while (auxiliary != null && auxiliary.next != null && auxiliary.next.data <= data) {
      auxiliary = auxiliary.next;
    }
    //Create new node and fit into bucket
    var node = new Node(data);
    node.next = auxiliary.next;
    auxiliary.next = node;
  }
  bucket_sort(arr, size) {
    if (size <= 0) {
      return;
    }
    // We are need to find maximum element in array 
    // Because calculation is based on max element value
    var max_value = this.maximum_element(arr, size);
    //Some variables which are using to perform sorting execution
    var auxiliary = null;
    var temp = null;
    var index = 0;
    for (var i = 0; i < size; ++i) {
      index = this.location(arr[i], size, max_value);
      // check given slot are null or not

      if (this.slot[index] == null) {
        // inserting first element in given (index) slot
        this.slot[index] = new Node(arr[i]);
      } else {
        // In this case slots are not empty then get first node in slot
        auxiliary = this.slot[index];
        if (auxiliary.data >= arr[i]) {
          //add new node at first position in bucket
          temp = new Node(arr[i]);
          temp.next = auxiliary;
          this.slot[index] = temp;
        } else {
          //otherwise add node in sorted way
          this.sorted_add(auxiliary, arr[i]);
        }
      }
    }
    //Assign slot value into actual array

    for (var i = 0,j = 0; i < size && j < size; ++i) {
      if (this.slot[i] != null) {
        auxiliary = this.slot[i];
        //Check if bucket slot empty or not
        while (auxiliary != null) {
          arr[j] = auxiliary.data;
          auxiliary = auxiliary.next;
          j++;
        }
      }
    }
  }
  //Display array element
  display(arr, size) {
    for (var i = 0; i < size; ++i) {
      //print array element value

      process.stdout.write("  " + arr[i]);
    }
    process.stdout.write("\n");
  }
}

function main() {
  //Array which are sorting by using bucket sort
  var arr = [8, 3, 8, 1, 3, 73, -3, 121, 54, 23, 84, 13, 67, 23, 52];
  //Get the size of array
  var size = arr.length;
  var obj = new BucketSort(size);
  //sort element
  obj.bucket_sort(arr, size);
  //display array element
  obj.display(arr, size);
}

main();

Output

  -3  1  3  3  8  8  13  23  23  52  54  67  73  84  121
/*
 Swift 4 Program
  Sort the Array elements using bucket Sort
*/


// This are storing information about array element
class Node {
  var data: Int;
  var next: Node? ;
  init(_ data: Int) {
    self.data = data;
    self.next = nil;
  }
}
class BucketSort {
  var slot: [Node?] = [Node]() ;
  init(_ size: Int) {
    // First create auxiliary memory to Bucket type
    // Which is store the information of sort element
    var i: Int = 0;
    //Set that initial have no element in bucket
    while (i < size) {
      self.slot.append(nil);
      i += 1;
    }
  }
  //Get the location of array elements
  func location(_ data: Int, _ element: Int, _ max_value: Int) ->Int {
    return data * element / (max_value + 1);
  }
  //Find the maximum element in given array
  func maximum_element(_ arr: [Int] , _ size : Int) -> Int {
    var max_value: Int = arr[0];
    var i: Int = 1;
    while (i < size) {
      if (max_value < arr[i]) {
        max_value = arr[i];
      }
      i += 1;
    }
    return max_value;
  }
  func sorted_add(_ element: Node? , _ data : Int) {
    var auxiliary : Node? = element;
    //Find node to insert new element
    while (auxiliary != nil && auxiliary!.next != nil && auxiliary!.next!.data <= data) {
      auxiliary = auxiliary!.next;
    }
    //Create new node and fit into bucket
    let node: Node? = Node(data);
    node!.next = auxiliary!.next;
    auxiliary!.next = node;
  }
  func bucket_sort(_ arr: inout [Int] , _ size : Int) {
    if (size <= 0) {
      return;
    }
    // We are need to find maximum element in array 
    // Because calculation is based on max element value
    let max_value: Int = self.maximum_element(arr, size);
    //Some variables which are using to perform sorting execution
    var auxiliary: Node? = nil;
    var temp: Node? = nil;
    var index: Int = 0;
    var i: Int = 0;
    var j = 0;
    while (i < size) {
      index = self.location(arr[i], size, max_value);
      // check given slot are null or not

      if (self.slot[index] == nil) {
        // inserting first element in given (index) slot
        self.slot[index] = Node(arr[i]);
      } else {
        // In this case slots are not empty then get first node in slot
        auxiliary = self.slot[index];
        if (auxiliary!.data >= arr[i]) {
          //add new node at first position in bucket
          temp = Node(arr[i]);
          temp!.next = auxiliary;
          self.slot[index] = temp;
        } else {
          //otherwise add node in sorted way
          self.sorted_add(auxiliary, arr[i]);
        }
      }
      i += 1;
    }
    i = 0;
    j = 0;
    //Assign slot value into actual array
    while (i < size && j < size) {
      if (self.slot[i] != nil) {
        auxiliary = self.slot[i];
        //Check if bucket slot empty or not
        while (auxiliary != nil) {
          arr[j] = auxiliary!.data;
          auxiliary = auxiliary!.next;
          j += 1;
        }
      }
      i += 1;
    }
  }
  //Display array element
  func display(_ arr: [Int] , _ size : Int) {
    var i: Int = 0;
    while (i < size) {
      //print array element value
      print(" ", arr[i],terminator:"");
      i += 1;
    }
    print(terminator:"\n");
  }
}
func main() {
  //Array which are sorting by using bucket sort
  var arr: [Int] = [8, 3, 8, 1, 3, 73, -3, 121, 54, 23, 84, 13, 67, 23, 52];
  //Get the size of array
  let size: Int = arr.count;
  let obj: BucketSort = BucketSort(size);
  //sort element
  obj.bucket_sort(&arr, size);
  //display array element
  obj.display(arr, size);
}
main();

Output

  -3  1  3  3  8  8  13  23  23  52  54  67  73  84  121
/*
  Scala Program
   Sort the Array elements using bucket Sort
*/
// This are storing information about array element
class Node(var data: Int,
  var next: Node) {


  def this(data: Int) {
    this(data,null);
  }
}
class BucketSort(var slot: Array[Node]) {

  def this(size: Int) {
    // First create auxiliary memory to Bucket type
    // Which is store the information of sort element
    this(Array.fill[Node](size)(null));
  }
  //Get the location of array elements
  def location(data: Int, element: Int, max_value: Int): Int = {
    return (data * element / (max_value + 1)).toInt;
  }
  //Find the maximum element in given array
  def maximum_element(arr: Array[Int], size: Int): Int = {
    var max_value: Int = arr(0);
    var i = 1;
    while (i < size) {
      if (max_value < arr(i)) {
        max_value = arr(i);
      }
            i+=1;
    }
    return max_value;
  }
  def sorted_add(temp : Node, data: Int): Unit = {
        var auxiliary : Node = temp;
    //Find node to insert new element
    while (auxiliary != null &&
      auxiliary.next != null &&
      auxiliary.next.data <= data) {
      auxiliary = auxiliary.next;
    }
    //Create new node and fit into bucket
    var node: Node = new Node(data);
    node.next = auxiliary.next;
    auxiliary.next = node;
  }
  def bucket_sort(arr: Array[Int], size: Int): Unit = {
    if (size <= 0) {
      return;
    }
    // We are need to find maximum element in array 
    // Because calculation is based on max element value
    var max_value: Int = maximum_element(arr, size);

    //Some variables which are using to perform sorting execution
    var auxiliary: Node = null;
    var temp: Node = null;
    var index: Int = 0;
    var i = 0;
    while (i < size) {
      index = location(arr(i), size, max_value);

      // check given slot are null or not

      if (slot(index) == null) {
        // inserting first element in given (index) slot
        slot(index) = new Node(arr(i));
      } else {
        // In this case slots are not empty then get first node in slot
        auxiliary = slot(index);

        if (auxiliary.data >= arr(i)) {
          //add new node at first position in bucket
          temp = new Node(arr(i));
          temp.next = auxiliary;
          slot(index) = temp;
        } else {
          //otherwise add node in sorted way
          sorted_add(auxiliary, arr(i));
        }
      }
            i+=1;
    }
    //Assign slot value into actual array
    i  = 0;
    var j : Int = 0;
    while (i < size &&
      j < size) {
      if (slot(i) != null) {
        auxiliary = slot(i);

        //Check if bucket slot empty or not
        while (auxiliary != null) {
          arr(j) = auxiliary.data;
          auxiliary = auxiliary.next;
          j += 1;
        }
      }
           i+=1;
    }
  }
  //Display array element
  def display(arr: Array[Int], size: Int): Unit = {
    var i = 0;
    while (i < size) {
      //print array element value
      print(" " + arr(i));
      i+=1;
    }
    print("\n");
  }
}
object Main {
  def main(args: Array[String]): Unit = {
    //Array which are sorting by using bucket sort
    var arr: Array[Int] = Array(8, 3, 8, 1, 3, 73, -3, 121, 54, 23, 84, 13, 67, 23, 52);

    //Get the size of array
    var size: Int = arr.length;
    var obj: BucketSort = new BucketSort(size);

    //sort element
    obj.bucket_sort(arr, size);

    //display array element
    obj.display(arr, size);
  }
}

Output

 -3 1 3 3 8 8 13 23 23 52 54 67 73 84 121

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment