Sep 28, 2019 β€’1 min read β˜•

πŸ’» Bucket Sort, 버킷 μ •λ ¬μ΄λž€?

Bucket Sort(버킷정렬)은 리슀트 λ‚΄μ˜ 값듀이 λ²”μœ„ 내에 μΌμ •ν•˜κ²Œ λΆ„ν¬λ˜μ–΄ μžˆμ„ λ•Œ μ‚¬μš©ν•˜λŠ” 것이 κ°€μž₯ μ ν•©ν•˜λ‹€. 0~1 μ‚¬μ΄μ˜ μˆ«μžλ“€μ„ μ •λ ¬ν•˜λŠ” 것과 같은 κ²½μš°μ— 이 bucket sortλ₯Ό μ‚¬μš©ν•  수 μžˆλ‹€.

이 μ •λ ¬ μ•Œκ³ λ¦¬μ¦˜μ„ μ‰½κ²Œ μ„€λͺ…ν•˜μžλ©΄, 리슀트 λ‚΄μ˜ 값듀을 νΌμ§ν•˜κ²Œ λΆ„λ₯˜ν•  수 μžˆμ„λ§Œν•œ μΉ΄ν…Œκ³ λ¦¬ ν˜Ήμ€ 버킷듀을 λ§Œλ“ λ‹€. κ·Έ λ‹€μŒμ— λ¦¬μŠ€νŠΈμ—μ„œ 버킷에 ν¬ν•¨λ˜λŠ” 값듀을 μ •λ ¬ν•œλ‹€. λ§ˆμ§€λ§‰μ—λŠ”, 버킷듀을 κΈ°μ€€μœΌλ‘œ 정렬을 ν•œλ‹€. μ„€λͺ…은 μ–΄λ ΅μ§€λ§Œ 그림으둜 보면 이해가 더 μ‰½κ²Œ λœλ‹€.

0~1 사이 값듀을 μ§€λ‹Œ λ¦¬μŠ€νŠΈκ°€ μžˆλ‹€κ³  κ°€μ •ν•΄λ³΄μž.

  1. Input Array의 값듀을 μΌμ •ν•œ 값듀을 κΈ°μ€€μœΌλ‘œ λ²„ν‚·μœΌλ‘œ λ‚˜λˆˆλ‹€. 이 λ•Œ λ²„ν‚·μ˜ κ°―μˆ˜λ„ 주어진 λ¦¬μŠ€νŠΈμ™€ 길이λ₯Ό κ°™κ²Œ λ§Œλ“€μ–΄μ„œ λΆ„λ₯˜λ₯Ό ν•œλ‹€.
  2. κ·Έ λ‹€μŒμ—λŠ” 각 버킷에 ν•΄λ‹Ήλ˜λŠ” 값에 κΈ°μ‘΄ 리슀트의 값듀을 μ§‘μ–΄λ„£λŠ”λ‹€. 이 λ•Œ μ§‘μ–΄λ„£μœΌλ©΄μ„œ 정렬을 ν•œλ‹€. μ—¬κΈ°μ„œ μ‚¬μš©λ˜λŠ” μ•Œκ³ λ¦¬μ¦˜μ€ 이전에 λ°°μ› λ˜ μ •λ ¬ μ•Œκ³ λ¦¬μ¦˜μ„ μ‚¬μš©ν•΄λ„ 뙨닀.
  3. λ§ˆμ§€λ§‰μœΌλ‘œ 버킷듀을 λ‹€ μ΄μ–΄μ„œ μ •λ ¬λœ ν•˜λ‚˜μ˜ 리슀트λ₯Ό λ§Œλ“ λ‹€.

Python Code

def bucket_sort(num):
    # 버킷을 담을 λΉ„μ–΄ μžˆλŠ” listλ₯Ό ν•˜λ‚˜ μƒμ„±ν•œλ‹€
    arr = [[] for _ in range(len(num))]

    # 버킷에닀 각각 elements듀을 λ„£λŠ”λ‹€
    # ex. 0.78 * 10 = 7.8
    # int(7.8)을 ν•΄μ„œ arr[7] 버킷에 ν•΄λ‹Ή 값을 λ„£λŠ”λ‹€
    for n in num: 
        index = int(len(num) * n)  
        arr[index].append(n) 
    
    # 각 sub list듀을 μ •λ ¬ν•œλ‹€
    for i in range(len(num)):
        arr[i] = insertion_sort(arr[i])

    # 각 버킷듀을 μ—°κ²°ν•œλ‹€
    k = 0
    for i in range(len(num)):
        for j in range(len(arr[i])):
            num[k] = arr[i][j]
            k += 1
            
    return num

number = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68] 
print(number)
bucket = bucket_sort(number)
print(bucket)
Β© 2021 Dojin Kim, Built with Gatsby