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