힙 정렬

개인적으로 힙도 어려웠는데 힙으로 정렬을 하라니 무서웠다. 하지만 힙을 이해했다면 힙 정렬을 하는 것은 문제가 아니다.

힙 복습

우선 힙에 대해 복습해보자. 힙은 우선순위 큐의 일종이다. 맨 처음 노드가 젤 작거나 혹은 젤 크다. 힙에서 부모가 k일 때 자식은 [2k+1] 과 [2k+2]이다. 이 점을 이용해서 힙 구조를 일단 만들어준다. 힙에서 부모는 자식보다 큰 구조였다. 힙 구조를 만들 때 우리는 percolateDown이라는 함수를 만들어 주어서 부모 자식 간의 관계를 만족시켜줬다.

def percolatedown(A, k, end):
  left = 2*k+1
  right = 2*k+2

  child = left
  # 종료 조건
  if child <= end:
    if right<=end and A[child] < A[right]:
      child = right
    if A[k] < A[child]:
      A[k], A[child] = A[child], A[k]
      percolatedown(A, child, end)

이 코드에서 end 자리에 len(A) - 1을 넣어주게 되면 그저 힙을 만드는 것이다. buildHeap 코드는 다음과 같다.

def buildheap(A):
  for i in range((len(A)-2) // 2, -1, -1):
    percolatedown(A, i, len(A)-1)

하지만 여기서 end 자리를 바꾸어 주면서 진행하면 정렬을 할 수 있다. 좀 더 자세히 설명하자면 힙 구조의 맨 끝에 젤 큰 값을 넣어준다.

그러면 맨 위에는 조건을 만족하지 않는 값이 나오니까 percolateDown을 해준다. 그렇게 계속 계속 진행하면 다음과 같이 된다.

코드는 간단하다.

def heapsort(A):
  buildheap(A)
  for last in range(len(A) -1, 0, -1):
    A[last], A[0] = A[0], A[last]
    percolatedown(A, 0, last-1)

이런식으로 last자리를 바꾸어줘 가면서 스며내려가기를 해주면 된다.

계수 정렬 (Counting Sort)

계수 정렬은 원소의 크기가 모두 -O(n) ~ O(n) 정수 범위에 있을 때 사용한다.

https://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html
이 사이트 들어가서 step 눌러가면서 진행하면 어떻게 흘러가는지 이해가 될 것이다.

def countingsort(A):
  k = max(A)
  C = [0 for _ in range(k+1)]

  for j in range(len(A)):
    C[A[j]] += 1

  for i in range(1, k+1):
    C[i] = C[i] + C[i-1]

  B = [0 for _ in range(len(A))]
  
  for j in range(len(A)-1, -1, -1):
    B[C[A[j]]-1] = A[j]
    C[A[j]] -= 1
  return B

이건 코드를 봐야 이해가 된다.

처음에 배열이 이렇게 있을 때 가장 큰 값은 5이다.
때문에 크기가 5인 배열을 만들어준다.
여기에 저 숫자들의 크기에 해당하는 인덱스에 +=1을 해준다. 그러면 결과는 다음과 같다.
여기서 이 값을 인덱스처럼 활용하기 위해서 누적합을 해준다.
그렇게 되면 다음과 같이 3줄의 코드로 정렬을 할 수 있다.

  for j in range(len(A)-1, -1, -1):
    B[C[A[j]]-1] = A[j]
    C[A[j]] -= 1

A의 끝에서 부터 B에 하나씩 값을 집어 넣는 것인데 미리 만들어준 C를 이용해서 본인의 인덱스에 맞는 값에 집어 넣는 것이다.

기수 정렬

모든 원소가 k 이하의 자릿수를 가진 자연수인 특수한 경우일 때 사용한다고 한다.
신기하게도 다음과 같이 한다고 한다. 약간 사전 느낌이다. 오 신기하게도 자리수를 계산해서 하는 정렬이다.

예를 들어서

array = [123, 2154, 222, 4,  283, 1560, 1061 ,2150]

배열이 다음과 같을 때 처음에 정렬을 다음과 같이 한다.

[[1560, 2150], [1061], [222], [123, 283], [2154, 4], [], [], [], [], []]

느낌이 확 오지 않는가?
그 다음은

[[4], [], [222, 123], [], [], [2150, 2154], [1560, 1061], [], [283], []]

이런식으로 진행하고 정렬 되는 순서를 보면 다음과 같다.

[1560, 2150, 1061, 222, 123, 283, 2154, 4]
[4, 222, 123, 2150, 2154, 1560, 1061, 283]
[4, 1061, 123, 2150, 2154, 222, 283, 1560]
[4, 123, 222, 283, 1061, 1560, 2150, 2154]

핵심은 이 코드이니 잘 기억하자.

  for i in range(numDigits):
    for x in A:
      y = (x // 10** i) % 10
      bucket[y].append(x)

전체 코드

import math
def radixSort(A):
  maxvalue = max(A)
  numDigits = math.ceil(math.log10(maxvalue))
  bucket = [[] for _ in range(10)]
  for i in range(numDigits):
    for x in A:
      y = (x // 10** i) % 10
      bucket[y].append(x)
    A.clear()
    for j in range(10):
      A.extend(bucket[j])
      bucket[j].clear()

array = [123, 2154, 222, 4,  283, 1560, 1061 ,2150]
radixSort(array)
print(array)