Skip to main content

Bucket Sort

Here given code implementation process.

/*
  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
/*
 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