Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
leetcode-sorting
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.
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment