FOR FREE YEAR SOLVED

Bucket sort is a sorting algorithm in which the array elements are distributed into different buckets that are sorted individually. The sorting can be done using some other sorting algorithms or it can be done by calling the bucket sort function recursively. This is a distribution sort. The complexity of this sorting technique depends on the sorting algorithm used to sort the elements of the bucket. Here, insertion sort is used to sort the elements of the bucket.

Bucket sort can be divided into four phases:

1. Initially, the empty buckets are created.

2. The original array is scanned and each element is inserted into the appropriate bucket.

3. The elements of each bucket are sorted individually.

4. The elements of the buckets are gathered and inserted back to the array.

The bucket sort is applied if the elements of the array are uniformly distributed over a range. Here, the range of the elements is taken from 0.0 to 1.0. the buckets are taken according to the range of the elements.

EXAMPLE:

Suppose the array elements are:

Suppose, 10 buckets are created to store the array elements. Here, the index of the bucket for each element is calculated as n*arr[i] where n is the number of elements of the array and arr[i] is the ith element of the array.

Initially, the buckets are initialized with a null value.

The first element of the array is 0.14. Now, it will be multiplied by 5 (here, n = 5). Therefore, we get the index of the bucket as: integer (0.14 × 5) = 0. Therefore, the element will be added to bucket 0.

Now, the next element of the array is 0.25. The same procedure will be followed. The index of the bucket is: integer of 0.25 × 5 = 1.

So, this element will be inserted into bucket 1.

Similarly, the indexes of the next elements are:

Integer of 0.10 × 5 = 0

Integer of 0.19 × 5 = 0

Integer of 0.02 × 5 = 0

Therefore, all the elements will be inserted into bucket 0.

Now, the elements of bucket ‘0’ will be sorted using insertion sort. After sorting the bucket ‘0’ we will get the bucket as:

Therefore, all the elements will be inserted into bucket 0.

For details about insertion sort follow: 

bucket 1 contains a single element. Now it will be inserted back to the original array. 

So, after sorting the array will be:

INPUT: The array elements
OUTPUT: Array after sorting using bucket sort
 

PROCESS:
Step 1: [Function ‘bucket_sort(array,n)’]
	    [Creating a bucket]
	    Create a list b
    	    for i=0 to n-1 repeat
       	 	Set b[i]<-Null
	    [End of ‘for’ loop]
    for i=0 to n-1 repeat 
        		Set bi <- integer of  n * j
        		Create a node with the data arr[i]
Append the node with b[bi]
	      [End of ‘for’ loop]
      for i =0 to n-1 repeat
        		Sort the list b[i]
	      [End of ‘for’ loop]
    	      for i=0 to n-1 repeat
		put the elements of each list (b[i]) into the original array ‘arr’ 
            	       [End of ‘for’ loop]
[End of function ‘bucket_sort()’]

Step 2: [Function ‘main()’]
	Read n [number of elements]
	For i= 0 to n-1 repeat
		Read arr[i]
	[End of ‘for’ loop]
	Call the function ‘bucket_sort(arr,n)’
[End of ‘main’ function]

Step 3: Stop.