Bucket sort is a sorting algorithm that separate the elements into multiple groups said to be buckets. Elements in bucket sort are first uniformly divided into groups called buckets, and then they are sorted by any other sorting algorithm. After that, elements are gathered in a sorted manner.The data items in the bucket sort are distributed in the form of buckets. In coding or technical interviews for software engineers, sorting algorithms are widely asked.
Example :
Algorithm Bucketsort [A (0..n-1)]
// Sort a given array by Counting sort.
// Input : An array A(0,n-1) of orderable elements.
// Output : Array A [0,n-1] sorted in non- decreasing order .
void bucketSort(float[] a,int n)
{
for(each floating integer 'x' in n)
{
insert x into bucket[n*x];
}
for(each bucket)
{
sort(bucket);
}
}
#include < stdio.h>
int getMax(int a[], int n) // function to get maximum element from the given array
{
int max = a[0];
for (int i = 1; i < n; i++)
if (a[i] > max)
max = a[i];
return max;
}
void bucket(int a[], int n) // function to implement bucket sort
{
int max = getMax(a, n); //max is the maximum element of array
int bucket[max], i;
for (int i = 0; i <= max; i++)
{
bucket[i] = 0;
}
for (int i = 0; i < n; i++)
{
bucket[a[i]]++;
}
for (int i = 0, j = 0; i <= max; i++)
{
while (bucket[i] > 0)
{
a[j++] = i;
bucket[i]--;
}
}
}
void printArr(int a[], int n) // function to print array elements
{
for (int i = 0; i < n; ++i)
printf("%d ", a[i]);
}
int main()
{
int a[] = {54, 12, 84, 57, 69, 41, 9, 5};
int n = sizeof(a) / sizeof(a[0]); // n is the size of array
printf("Before sorting array elements are - \n");
printArr(a, n);
bucket(a, n);
printf("\nAfter sorting array elements are - \n");
printArr(a, n);
}
Code
public class Bucket
{
int getMax(int a[]) // function to get maximum element from the given
array
{
int n = a.length;
int max = a[0];
for (int i = 1; i < n; i++)
if (a[i] > max)
max = a[i];
return max;
}
void bucket(int a[]) // function to implement bucket sort
{
int n = a.length;
int max = getMax(a); //max is the maximum element of array
int bucket[] = new int[max+1];
for (int i = 0; i <= max; i++)
{
bucket[i] = 0;
}
for (int i = 0; i < n; i++)
{
bucket[a[i]]++;
}
for (int i = 0, j = 0; i <= max; i++)
{
while (bucket[i] > 0)
{
a[j++] = i;
bucket[i]--;
}
}
}
void printArr(int a[]) /* function to print the array */
{
int i;
int n = a.length;
for (i = 0; i < n; i++)
System.out.print(a[i] + " ");
}
public static void main(String[] args) {
int a[] = { 90, 40, 5, 15, 30, 9 };
Bucket b1 = new Bucket();
System.out.print("Before sorting array elements are - \n");
b1.printArr(a);
b1.bucket(a);
System.out.print("\nAfter sorting array elements are - \n");
b1.printArr(a);
}
Code
max_value = max(input_list)
size = max_value/len(input_list)
buckets_list= []
for x in range(len(input_list)):
buckets_list.append([])
for i in range(len(input_list)):
j = int (input_list[i] / size)
if j != len (input_list):
buckets_list[j].append(input_list[i])
else:
buckets_list[len(input_list) - 1].append(input_list[i])
for z in range(len(input_list)):
insertion_sort(buckets_list[z])
final_output = []
for x in range(len (input_list)):
final_output = final_output + buckets_list[x]
return final_output
def insertion_sort(bucket):
for i in range (1, len (bucket)):
var = bucket[i]
j = i - 1
while (j >= 0 and var < bucket[j]):
bucket[j + 1] = bucket[j]
j = j - 1
bucket[j + 1] = var
def main():
input_list = [1.20, 0.22, 0.43, 0.36,0.39,0.27]
print('ORIGINAL LIST:')
print(input_list)
sorted_list = bucket_sort(input_list)
print('SORTED LIST:')
print(sorted_list)-
Code
2 3 1 8 3 4
1 2 2 3 3 4 8
Bubble sort
Counting sort