leetcode-sorting

bucketSort.py

class Solution:
    def sortArray(self, nums: List[int]) -> List[int]:
        return self.bucketSort(nums)
    def bucketSort(self, A):
        """
        1. It's in-place sorting. 
        2. Bucket sort is mainly useful when input is uniformly distributed over a range.(floating number is allowed)
        
        step1: create n buckets
        step2: put element into buckets
        step3: 依序處理所有非空的桶子
        ref:https://www.geeksforgeeks.org/bucket-sort-2/?ref=lbp
        
        Average case, O(n+k)
        Worst case, every element was put into same bucket. Insertion sort might take O(n^2)
        """
        n = len(A)
        buckets = [[] for _ in range(n)]
        mini = min(A)
        maxi = max(A)
        rang = maxi-mini
        # edge case
        if rang == 0:
            return A
        
        # O(n), in below way, put val into bucekt in order.
        # This step also takes O(n) time on average if all numbers are uniformly distributed 
        for a in A:
            # index shoude be 0 to n-1
            i = int ( (a-mini)  * (n-1) / rang )
            buckets[i].append(a)
        
        #O(k+n), where k is nb of non-empty buckets, we need to process n elements. 
        i=0
        for b in buckets:
            # each bucket has the size O(1), so sorting is O(1) too
            b.sort(reverse=True) # decending
            while b:
                A[i] = b.pop()
                i += 1           
        return A