정렬 - 4) 기수 정렬 (radix sort)

 

📍 기수 정렬: 값을 비교하지 않는 특이한 정렬

• 맨 뒤에 있는 자릿수부터 정렬, 점점 앞으로 이동하며 각 자릿수를 정렬
• 시간복잡도: O(kn)
  • k는 자릿수 
  • 각각의 데이터에 대해 매 자릿수마다 분류작업을 하기 때문에, 분류작업이 k번 반복됨

 

---

 

💬 python 코드

function radix_sort(arr, k)
  for pos = k - 1 ... pos >= 0:
    set arr_new = [10][]
    for i = 0 ... i < arr.size
      set digit = posth digit of arr[i]
      arr_new[digit].append(arr[i])

    set store_arr = []
    for i = 0 ... i < 10
      for j = 0 ... j < arr_new[i].size
        store_arr.append(arr_new[i][j])
  
    arr = store_arr

  return arr