Python program for bucket sort algorithm














































Python program for bucket sort algorithm



Bucket sort, or bin sort, is a sorting algorithm that works by distributing the elements of an array into a number of buckets. Each bucket is then sorted individually, either using a different sorting algorithm, or by recursively applying the bucket sorting algorithm. It is a distribution sort. Bucket sort can be implemented with comparisons and therefore can also be considered a comparison sort algorithm. The computational complexity depends on the algorithm used to sort each bucket, the number of buckets to use, and whether the input is uniformly distributed.

Bucket sort is mainly useful when input is uniformly distributed over a range. When the input contains several keys that are close to each other, those elements are likely to be placed in the same bucket, which results in some buckets containing more elements than average. The worst-case scenario occurs when all the elements are placed in a single bucket. The overall performance would then be dominated by the algorithm used to sort each bucket, which is typically O(n^{2}) insertion sort, making bucket sort less optimal than O(n\log(n)comparison sort algorithms like Quicksort.

Bucket sort works as follows:

Set up an array of initially empty "buckets".
Scatter: Go over the original array, putting each object in its bucket.
Sort each non-empty bucket.
Gather: Visit the buckets in order and put all elements back into the original array.

Pseudocode:

function bucketSort(array, k) is
  buckets %u2190 new array of k empty lists
  M %u2190 the maximum key value in the array
  for i = 1 to length(array) do
    insert array[i] into buckets[floor(array[i] / M * k)]
  for i = 1 to k do
    nextSort(buckets[i])
  return the concatenation of buckets[1], ...., buckets[k]

Program:

def insertion(inpvalue): for i in range(1, len(inpvalue)): temp = inpvalue[i] j = i - 1 while (j >= 0 and temp < inpvalue[j]): inpvalue[j + 1] = inpvalue[j] j = j - 1 inpvalue[j + 1] = temp def bucket_sort(inpvalue): largest = max(inpvalue) length = len(inpvalue) size = largest/length buckets = [[] for _ in range(length)] for i in range(length): j = int(inpvalue[i]/size) if j != length: buckets[j].append(inpvalue[i]) else: buckets[length - 1].append(inpvalue[i]) for i in range(length): insertion(buckets[i]) res = [] for i in range(length): res = res + buckets[i] return res inpvalue = input('Enter the list of (nonnegative) numbers: ').split() inpvalue = [int(x) for x in inpvalue] sorted_list = bucket_sort(inpvalue) print('Sorted list: ', end='') print(sorted_list)

Output:

Enter the list of (nonnegative) numbers: 101 32 100 200 32 10 2 4 6 9
Sorted list: [2, 4, 6, 9, 10, 32, 32, 100, 101, 200]

Problems:
Still cannot figure out how to perform bucket sort on negetive numbers

Comments