내가 공부하기 위한 공간 - [알고리즘] 13 - 정렬(힙, 기수)

[힙 정렬]

배열을 완전 이진트리로 구성

맥스/민 힙으로 재구성 후 루트와 마지막 노드를 교환하는 작업을 반복하여 오름차순/내림차순으로 정렬

[8 5 9 1 3]

8

5 9

1 3

맥스 힙으로 재구성

9

5 8

1 3

9와 3을 교체

3

5 8

1 9

9는 정렬되어 있는 상태이므로 제외하고 맥스 힙

8

5 1

3 9

9과 3을 교체

3

5 1

8 9

이를 반복하면

1

3 5

8 9

[1 3 5 8 9]

 

<유사코드>

힙정렬(배열 A)
    최대힙_만들기(A)
    for i ← A의 길이부터 2까지 감소하면서
        A[1]과 A[i]를 교환
        힙 크기 ← 힙 크기 - 1
        최대힙_정리(A, 1)

최대힙_만들기(배열 A)
    힙 크기 ← A의 길이
    for i ← (A의 길이 ÷ 2)부터 1까지 감소하면서
        최대힙_정리(A, i)

최대힙_정리(배열 A, 정점 i)
    왼쪽 ← 왼쪽자식(i)
    오른쪽 ← 오른쪽자식(i)
    
    만약 왼쪽 ≤ 힙 크기이고 A[왼쪽] > A[i]이면
        가장큰값 ← 왼쪽
    아니면
        가장큰값 ← i
    
    만약 오른쪽 ≤ 힙 크기이고 A[오른쪽] > A[가장큰값]이면
        가장큰값 ← 오른쪽
    
    만약 가장큰값 ≠ i이면
        A[i]와 A[가장큰값]을 교환
        최대힙_정리(A, 가장큰값)

왼쪽자식(i) = 2 × i  
오른쪽자식(i) = 2 × i + 1

시간복잡도 O(nlogn)

 

 

[기수정렬]

각 자릿수 별로 정렬

일의자리 정렬 후 십의자리 정렬 후 … n자릿수 정렬

[17 192 26 9 108 7]

일의자리 정렬

192

026

017

007

108

009

십의자리 정렬

007

108

009

017

026

192

백의자리 정렬

007

009

017

026

108

192

 

<유사코드>

기수정렬(배열 A, 최대자릿수 d)
    for i ← 1부터 d까지  // i: 현재 자릿수 (1의 자리 → 10의 자리 → ...)
        자리수별_안정정렬(A, i)

자리수별_안정정렬(배열 A, 자릿수 i)
    0부터 9까지의 빈 큐 큐[0..9] 만들기

    for 각 원소 x in A
        digit ← x의 i번째 자릿수
        큐[digit]에 x를 넣기

    A를 큐[0]부터 큐[9]까지 차례대로 꺼내서 다시 구성

시간복잡도 O(n)