Sorting: Bucket Sort

Sorting: Bucket Sort

 

 

https://youtu.be/mMELgqz7Wnk

 

https://youtu.be/gFesW458zsU

 

def bucketSort(arr):
    # Assuming arr only contains 0, 1 or 2
    counts = [0, 0, 0]

    # Count the quantity of each val in arr
    for n in arr:
        counts[n] += 1
    
    # Fill each bucket in the original array
    i = 0
    for n in range(len(counts)):
        for j in range(counts[n]):
            arr[i] = n
            i += 1
    return arr

 

• Time: O(n)
• Space: O(1)
• Stable? : No

 

일반적으로.

빠르게 정렬해야하면.. MergeSort를 쓰자!!