퀵 정렬의 하이라이트

이름 그대로 빠른 정렬이 가능한 알고리즘입니다.

핵심은 피벗(Pivot)입니다.

피벗은 또 다르게 파티션이라고도 부를 수 있습니다.

퀵 정렬은 불안정한 정렬인데 왜그런지는 뒤에서 설명하겠습니다.

어쨋든 퀵 정렬의 실행 시간은 다음과 같습니다.

최악의 경우 실행 시간: Θ(n^2).

기대 실행 시간: Θ(n lg n)

Θ(n lg n)에 숨겨진 상수는 작습니다.
제자리에서 정렬됩니다.

! 글에서 파티션은 피벗이라 생각해주시기 바랍니다. !

진짜 좋은 영상 있으니 참고

https://www.youtube.com/watch?v=Hoixgm4-P4M

퀵 정렬의 세가지 전략 

나누기: 

배열 A[p . . r ]에서 A[q]를 파티션(피벗)으로 삼아 

두 개의 (아마도 비어 있는) 하위 배열 A[p . . q − 1] 및 A[q + 1 . . r ]로 분할합니다.

첫 번째 하위 배열 A[p 의 각 요소. . q − 1] 은 ≤ A[q] 이고 A[q] 는 ≤ 두 번째 하위 배열 A[q + 1 의 각 요소입니다. . r ]

이게 말이 어려운데 눈으로 이해해봅시다.

이렇게 A[p .. r] 과 피벗 A[q]를 잘 설정했습니다.

여기서 p는 배열의 시작 인덱스, r은 끝 인덱스입니다.

이렇게 선택한 피벗을 기준으로 왼쪽 오른쪽 정렬해봅시다.

이렇게 되면 배열이 두 부분으로 나뉩니다:
1. A[p..q-1]: [2, 1] (3보다 작은 요소들)
2. A[q+1..r]: [5, 7, 6, 9] (3보다 큰 요소들)
피벗 3은 자신의 올바른 위치에 있게 됩니다.

올바른 위치란 어려운게 아니라 이런식으로 피벗을 기준으로 작고 큰 요소들이 잘 배치되있으면 됩니다.
이렇게 분할된 두 부분 배열에 대해 재귀적으로 같은 과정을 반복하여 전체 배열을 정렬합니다.

정복: 

QUICKSORT에 대한 재귀 호출을 통해 두 개의 하위 배열을 정렬합니다.

결합: 

하위 배열은 제자리에 정렬되어 있으므로 결합하는 데 작업이 필요하지 않습니다.

파티션(피벗) 의사 코드

1. 피벗(x)으로 배열의 마지막 요소 선택
2. i는 작은 요소들의 경계를 추적
3. j로 배열을 순회하며:
   - A[j]가 피벗보다 작거나 같으면 i를 증가시키고 A[i]와 A[j]를 교환
4. 마지막으로 피벗을 올바른 위치로 이동
5. 피벗의 최종 위치 반환

이 과정을 통해 배열이 피벗을 기준으로 두 부분으로 나뉘게 됩니다.

왼쪽은 피벗보다 작거나 같은 요소들, 오른쪽은 큰 요소들로 구성됩니다.

그리고 이 피벗 코드를 활용한 퀵 정렬 코드입니다.

1. 기본 조건: p < r 일 때만 정렬 수행 (배열 길이가 2 이상일 때)
2. PARTITION (피벗) 함수 호출:
   - 배열을 두 부분으로 나누고 피벗의 위치 q를 반환
3. 재귀 호출:
   - 피벗 왼쪽 부분 정렬: QUICKSORT(A, p, q-1)
   - 피벗 오른쪽 부분 정렬: QUICKSORT(A, q+1, r)

이 알고리즘은 위에서 설명 드렸던 분할 정복 방식으로 작동합니다:
- 분할: PARTITION 함수로 배열을 나눔
- 정복: 나눠진 부분 배열을 재귀적으로 정렬
- 결합: 이미 정렬된 부분 배열들이 전체 정렬된 배열을 형성

이 과정을 반복하여 전체 배열이 정렬됩니다.

Worst Case 

퀵소트의 최악의 경우(Worst-Case) 
1. 불균형한 분할:
   - 퀵정렬이 가장 비효율적으로 작동하는 경우입니다.
   - 매 분할마다 한쪽 부분배열에 모든 요소가 몰리고, 다른 쪽은 비어있게 됩니다.

2. 구체적인 상황:
   - 한 부분배열에는 0개의 요소
   - 다른 부분배열에는 n-1개의 요소 (n은 전체 배열 크기)

3. 시간 복잡도 분석:
    * T(n) = T(n-1) + T(0) + Θ(n)

각 부분을 보자면
    * T(n-1): 큰 부분배열 처리 시간

최악의 경우, n-1개 요소가 한쪽 부분배열로 가게 됩니다. 그렇기 때문에 큰 부분배열인겁니다.

    * T(0): 빈 부분배열 처리 시간 (무시 가능)
    * Θ(n): 분할 과정의 시간
n개 요소를 모두 한 번씩 비교해야 하므로 Θ(n) 시간이 듭니다.

   - 결국 무시하는걸 제외하면 아래 재귀식이 나옵니다.

T(n) = T(n-1) + Θ(n)

이걸 수학적으로 풀어봅시다 

다시 말씀드리지만 지금 우리의 T(n)은 재귀식입니다.

배열을 계속 피벗을 정해서 정렬하고 쪼개기 때문에 재귀식입니다.

이 식은 모든 n에 대해 성립합니다. 따라서 n 대신 (n-1)을 넣어도 똑같이 성립합니다:

T(n-1) = T((n-1)-1) + Θ(n-1) = T(n-2) + Θ(n-1)

도 가능하다는거죠 

이는 마치 수학에서 x = 2x - 3 이라는 식이 있을 때, x 대신 (x-1)을 넣어
(x-1) = 2(x-1) - 3 이라고 쓸 수 있는 것과 같은 원리입니다.

T(n) = T(n-1) + Θ(n)
= (T(n-2) + Θ(n-1)) + Θ(n)
= ((T(n-3) + Θ(n-2)) + Θ(n-1)) + Θ(n)
...
= T(1) + Θ(2) + Θ(3) + ... + Θ(n-1) + Θ(n)

이런식으로 유도를 하다보면 어느순간 T(n-1)은 이미 다 풀어진걸 볼 수 있습니다.

이제 정리하면

Θ(1 + 2 + 3 + ... + n) = Θ(n(n+1)/2) = Θ(n²)

즉 재귀식을 풀면 T(n) = Θ(n²)가 됩니다.

이런 최악의 상황은 이미 정렬된 배열이나 역순으로 정렬된 배열에서 발생할 수 있습니다.

Best Case

최선의 상황에선 다음과 같습니다.

1. 균형 잡힌 분할:
   - 매 분할마다 배열이 거의 정확히 반으로 나뉩니다.
   - 이는 퀵소트가 가장 효율적으로 작동하는 경우입니다.

2. 부분배열의 크기:
   - 각 부분배열은 n/2 이하의 요소를 가집니다.
   - 이는 완벽한 균형을 의미합니다.

3. 시간 복잡도 분석:
   - T(n) = 2T(n/2) + Θ(n)

각 부분을 보자면
     * 2T(n/2): 두 개의 n/2 크기 부분배열을 정렬하는 시간
     * Θ(n): 분할 과정의 시간

   - 이 재귀식을 풀면 T(n) = Θ(n lg n)이 됩니다.
     (여기서 lg n은 log₂ n을 의미합니다)

결론적으로, 최선의 경우 퀵정렬의 시간 복잡도는 O(n log n)입니다.

이는 배열이 매번 거의 균등하게 분할될 때 달성됩니다. 이 경우, 대부분의 정렬 알고리즘 중에서 가장 빠른 성능을 보입니다.

평균 실행 시간

퀵 정렬의 평균 실행 시간은 최악의 경우보다 최상의 경우에 훨씬 더 가깝습니다.

한마디로 대부분의 경우에선 괜찮은 알고리즘이라는겁니다.
PARTITION이 항상 9:1 분할을 생성한다고 가정해봅시다.
이때의 재귀 식을 구합니다.

T(n) ≤ T(9n/10) + T(n/10) + Θ(n)

   - T(9n/10): 큰 부분배열(90%)을 정렬하는 시간
   - T(n/10): 작은 부분배열(10%)을 정렬하는 시간
   - Θ(n): 분할 과정의 시간

셋 다 합하면 O(n lg n)이 걸립니다. 이는 최선의 경우와 같은 시간 복잡도입니다.

결론적으로, 퀵정렬은 완벽하게 균형 잡히지 않은 분할에서도 여전히 효율적으로 작동합니다. 

9:1 정도의 불균형한 분할에서도 O(n lg n)의 시간 복잡도를 유지하며, 이는 퀵정렬이 실제 상황에서 왜 효과적인지를 보여줍니다.

사진으로 보면 이렇습니다.

불안정한 퀵 정렬

재귀 트리의 분할은 항상 일정하지 않습니다.
일반적으로 재귀 트리 전체에는 좋은 분할과 나쁜 분할이 혼합되어 있습니다.

그렇기 때문에 불안정한 정렬이라는것입니다.
이것이 퀵 정렬의 점근적 실행 시간에 영향을 미치지 않는다는 것을 확인하기 위해

수준이 최상의 경우와 최악의 경우 분할 간에 번갈아 나타난다고 가정합니다.

1. 두 그림 비교:
   - 왼쪽 그림: 불균형한 분할을 보여줍니다 (0과 n-1로 나뉨).
   - 오른쪽 그림: 균형 잡힌 분할을 보여줍니다 ((n-1)/2로 균등하게 나뉨).

2. 추가 레벨의 의미:
   - 왼쪽 그림의 추가 레벨(0에서 n-1로 가는 단계)은 단순히 상수 시간을 추가합니다.
   - 이는 빅오 표기법에서 숨겨진 상수에 영향을 줄 뿐, 전체적인 시간 복잡도에는 영향을 미치지 않습니다.

3. 부분배열의 수:
   - 두 경우 모두 최종적으로 정렬해야 할 부분배열의 수는 동일합니다.
   - 왼쪽 그림에서 추가 단계가 있지만, 결국 같은 크기의 부분배열로 나뉩니다.

4. 작업량:
   - 왼쪽 그림의 경우, 추가 단계로 인해 최종 분할에 도달하기까지 약 두 배의 작업이 필요합니다.
   - 하지만 이는 시간 복잡도의 차수(order)를 변경하지 않습니다.

결론적으로, 이 분석은 퀵소트의 평균적인 성능이 최악의 경우보다 최선의 경우에 더 가깝다는 것을 보여줍니다. 불균형한 분할이 발생하더라도, 전체적인 시간 복잡도는 여전히 O(n log n)에 가깝게 유지됩니다.

랜덤 퀵 정렬의 경우

그럼 항상 퀵 정렬은 최상의 경우일까요? 당연히 아닙니다.

이걸 보여주기 위해 랜덤 퀵 정렬을 예시를 들어봅시다.

시작에서도 말했지만 알고리즘의 주요 비용은 파티셔닝(피벗 정하기)입니다.
PARTITION은 매번 향후 고려 사항에서 피벗 요소를 제거합니다. 

따라서 PARTITION은 최대 n번 호출됩니다.

PARTITION에 대한 각 호출이 수행하는 작업량은 상수에 해당 for 루프에서 수행되는 비교 횟수를 더한 것입니다.
X = PARTITION에 대한 모든 호출에서 수행된 총 비교 수라고 합니다.

따라서 전체 실행에 걸쳐 수행된 총 작업은 O(n + X)입니다.

분석을 쉽게 하기 위해:
A의 요소 이름을 z1, z2, 로 바꿉니다. . . , zn, zi는 i번째로 작은 요소입니다.

위 집합은 Zi와 Zj 사이의 요소 집합입니다.

중요한 부분은 각 요소 쌍은 최대 한 번만 비교됩니다.

요소는 피벗 요소하고만 비교되고 피벗 요소는 나중에 PARTITION을 호출할 때 절대 사용되지 않기 때문입니다.

각 쌍은 최대 한 번 비교되므로 알고리즘에 의해 수행되는 총 비교 횟수는 다음과 같습니다.

각 왼쪽 오른쪽 배열 양측의 기대값은 다음과 같습니다.

[3, 7, 1, 9, 5] 라는 배열이 있다고 가정합시다.
이 중 하나를 피벗으로 선택합니다. 예를 들어 5를 선택했다고 합시다.
5를 기준으로 배열을 나누면: [3, 1] 5 [7, 9]
이제 3과 7은 절대 서로 비교되지 않을 것입니다. 

왜냐하면 3은 항상 5의 왼쪽에, 7은 항상 5의 오른쪽에 있을 것이기 때문입니다.

반면, 3과 1은 서로 비교될 가능성이 있습니다.

왜냐하면 둘 다 5보다 작은 부분에 속해 있기 때문입니다.

따라서, 두 요소가 비교될 확률은 그 두 요소 사이의 값이 피벗으로 선택되지 않을 확률과 관련이 있습니다. 

또한, 둘 중 하나가 먼저 피벗으로 선택될 경우, 그 요소는 다른 모든 요소와 비교됩니다.

이런 방식으로 퀵 정렬의 평균적인 비교 횟수를 계산할 수 있습니다.

1. j - i + 1개의 요소가 있고, 피벗은 무작위로 독립적으로 선택됩니다.
i는 부분 배열의 시작 인덱스
j는 부분 배열의 끝 인덱스라고 보시면 됩니다.

2. 특정 요소가 첫 번째로 선택될 확률은 1/(j-i+1)입니다.

3. Zi와 Zj가 비교될 확률은 둘 중 하나가 첫 번째 피벗으로 선택될 확률과 같습니다.

4. 이 확률은 다음과 같이 계산됩니다:
   Zi가 첫 피벗으로 선택될 확률 (1/(j-i+1))
   Zj가 첫 피벗으로 선택될 확률 (1/(j-i+1))
따라서 총 확률은 2/(j-i+1)이 됩니다.

결과적으로 이 분석을 통해 퀵 정렬의 평균 시간 복잡도가 O(n log n)임을 증명할 수 있습니다.

퀵 정렬의 평균 케이스에서 비교 횟수의 기댓값 E[X]를 계산하는 과정을 보여줍니다. 단계별로 설명하겠습니다:

1. 첫 번째 식:
   - 모든 가능한 (i, j) 쌍에 대해 비교 확률(2/(j-i+1))의 합을 구합니다.

2. 변환 (simple transformation):
   - j-i를 k로 치환하여 식을 단순화합니다.

3. 근사 (approximation):
   - k+1을 k로 근사하여 계산을 단순화합니다.

4. 조화수열 (Harmonic series):
   - 내부 합이 조화수열의 형태가 됩니다. (1/1 + 1/2 + 1/3 + ... + 1/n)

5. 최종 결과:
   - 조화수열의 합은 대략 O(lg n)입니다.
   - 외부 합으로 인해 n이 곱해져 최종적으로 O(n lg n)이 됩니다.

이 분석을 통해 퀵 정렬의 평균 시간 복잡도가 O(n lg n)임을 수학적으로 증명합니다. 

우선순위 큐(Priority queue)

1. 정의: 각 요소에 우선순위가 할당된 큐

2. 특징:
   - 높은 우선순위 요소가 먼저 처리됨
   - 동적으로 요소 추가/제거 가능

3. 주요 연산:
   - 삽입: 새 요소 추가
   - 최대값 추출: 최고 우선순위 요소 제거 및 반환
   - 우선순위 변경: 요소의 우선순위 수정

우선순위 기반 데이터 관리에 효과적이고 주로 큐로 구현합니다.

우선순위 큐 특징

1. 동적 집합 S를 유지합니다. 이는 요소들이 추가되거나 제거될 수 있음을 의미합니다.

초기 상태:
S = { }  (빈 집합)

요소 추가 후:
S = { 5, 3, 8 }

또 다른 요소 추가:
S = { 5, 3, 8, 1 }

요소 제거 후:
S = { 5, 8, 1 }

2. 각 집합의 요소는 키(key)라고 하는 연관된 값을 가집니다. 이 키는 요소의 우선순위를 결정합니다.

요소1: (데이터: "작업A", 키: 5)
요소2: (데이터: "작업B", 키: 3)
요소3: (데이터: "작업C", 키: 8)

요소3이 가장 우선순위(8)가 높으니 먼저 처리됩니다.

3. 최대 우선순위 큐는 다음과 같은 동적 집합 연산을 지원합니다:

   a. INSERT(S, x): 요소 x를 집합 S에 삽입합니다.
   
   b. MAXIMUM(S): S에서 가장 큰 키를 가진 요소를 반환합니다.
   
   c. EXTRACT-MAX(S): S에서 가장 큰 키를 가진 요소를 제거하고 반환합니다.
   
   d. INCREASE-KEY(S, x, k): 요소 x의 키 값을 k로 증가시킵니다. 단, k는 x의 현재 키 값보다 크거나 같아야 합니다.

이러한 연산들을 통해 우선순위 큐는 항상 가장 높은 우선순위(여기서는 가장 큰 키 값)를 가진 요소에 빠르게 접근하고 조작할 수 있습니다. 이는 다양한 알고리즘과 응용 프로그램에서 유용하게 사용됩니다.

우선순위 큐는 주로 힙(Heap) 자료구조를 사용하여 구현되며, 이를 통해 효율적인 연산이 가능합니다.

힙에대해서 모르겠다면 아래 포스트를 참고해주시기 바랍니다.

https://kimyir.tistory.com/106

힙으로 구현

HEAP-EXTRACT-MAX(S)

이제 우선 순위 큐의 힙 의사 코드를 봅시다.

단계적 설명

아까 EXTRACT-MAX(S)뜻이 "S에서 가장 큰 키를 가진 요소를 제거하고 반환합니다." 라고 했는데

코드를 보면 heap-size[A] 배열이 비어있지 않다면 루트 노드에 있는 최대값 A[1]을 저장해줍니다.

그리고 A[1]을 A[heap-size]번째, 즉 마지막 노드로 이동한 뒤, 힙 크기를 감소합니다.

이렇게 가장 우선순위(최대값) 노드를 얻었으면 MAX-HEAPIFY 작업을 하여 다시 최대힙으로 정렬해줍니다.

특징:

• 최대값 추출 후 힙 구조 유지
• 시간 복잡도: O(log n) (MAX-HEAPIFY 때문)

활용:

• 우선순위 큐 구현
• 힙 정렬 알고리즘의 일부

def heap_extract_max(A):
    if len(A) - 1 < 1:  # heap-size[A] < 1
        raise ValueError("힙 언더플로우")
    
    max_val = A[1]  # max ← A[1]
    A[1] = A[len(A) - 1]  # A[1] ← A[heap-size[A]]
    A[len(A) - 1] = None  # 마지막 요소를 None으로 설정
    A.heap_size -= 1  # heap-size[A] ← heap-size[A] - 1
    
    max_heapify(A, 1)  # MAX-HEAPIFY(A, 1)
    
    return max_val
    
# 사용 예
heap = [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]
print("원래 힙:", heap)
max_val = heap_extract_max(heap)

실제 예시 파이썬 코드입니다.

HEAP-INCREASE-KEY(A,i,key)

그 다음은 위에서 얘기한 INCREASE-KEY(S, x, k)의 의사코드입니다.

이 함수는 요소 x의 키 값을 k로 증가시킵니다.

단, k는 x의 현재 키 값보다 크거나 같아야 합니다. 최대 힙 속성을 유지 해야하기 때문입니다.

매개변수:

   - A: 힙 배열
   - i: 키를 증가시킬 노드의 인덱스
   - key: 새로운 키 값

단계별 설명:

   1) 새 키가 현재 키보다 작은지 확인
   2) 노드의 키 값을 새 값으로 업데이트
   3) 부모 노드와 비교하며 필요시 교환 (상향 이동)

값이 바뀌기 때문에 우선순위 큐에서 요소의 우선순위 변경할 수 있습니다.
또한 다익스트라 알고리즘 등에서 사용되는걸로 압니다.

MAX-HEAP-INSERT(A, key)

MAX-HEAP-INSERT(A, key), 위에서도 있었는데

INSERT(S, x) : 요소 x를 집합 S에 삽입합니다.

그럼 각각 S와 x를 A와 key로 대입하면 

   - A: 힙 배열
   - key: 삽입할 새로운 키 값
가 되겠습니다.

단계별 설명: 

   1) 힙 크기를 1 증가시킵니다.
   2) 새 노드를 힙의 마지막에 -∞ 값으로 추가합니다.
   3) HEAP-INCREASE-KEY 함수를 호출하여 새 노드의 키 값을 설정하고 적절한 위치로 이동시킵니다.

주요 특징:

   - 새 요소를 힙의 마지막에 추가한 후 상향식으로 조정
   - 시간 복잡도: O(log n) (HEAP-INCREASE-KEY의 복잡도와 동일)

활용:

   - 우선순위 큐에 새로운 요소 추가
   - 힙 정렬 알고리즘의 일부로 사용

저번 시간에 알고리즘의 뜻을 말했는데요. 대충 문제 해결 방식입니다.

그럼 자료구조는 뭘까요? 자료 구조는 이름 그대로 자료의 구조. 즉 자료를 담는 방법입니다.

그 중 힙은 정렬, 우선순위 큐 넘버 지정, 스케줄링 등에 활용되는 자료구조입니다. 

한번 힙에대해서 알아봅시다.

힙은 각 노드가 일부 값으로 구성되는 거의 완전한 이진 트리입니다.

이진 트리에 대해서는 아래 사진 참고하시면 됩니다.

루트 - 젤 위 부모 노드

리프 - 젤 아래 더이상 자식 노드가 없는 노드

정도만 유의하시면 될것같네요

힙의 특징

힙의 이진 트리에서는 다음의 특징을 가집니다.

힙 속성 : 일부 노드 N의 값(수치)은 N의 두 하위 노드 값(수치)보다 크거나 같습니다.

사진에서는 큰 부모노드 1의 값 16은 자식 노드 2 3의 각각 14와 10보다 크거나 같습니다.
노드의 높이 = 노드에서 리프까지 내려가는 길중 가장 긴 단순한 가장자리의 길의 수입니다.

사진에서는 16 -> 14 -> 8 -> 2, 길의 간선이 3개니깐 높이가 3 되겠네요.
힙의 높이 = 루트 높이 = Θ(lg n), 여기서 n은 트리의 노드 수입니다.

루트(레벨0)~레벨3까지 총 높이가 3이 되겠네요.

힙에는 두가지 종류가 있습니다.

MAX-HEAPIFY 상태와 MIN-HEAPIFY 상태가 있습니다.

최대힙과 최소힙이라하는데 각각 루트노드가 젤 크냐 작냐의 차이입니다.

예시

MAX-HEAPIFY

MAX-HEAPIFY는 max-heap 속성을 만드는데 사용됩니다.
MAX-HEAPIFY 가 적용된 상태 이전에는 A[i]가 자식보다 작을 수 있습니다.

즉 최대힙 상태로 정렬이 안된상태죠. 이걸 정렬해봅시다.

i는 지금 현재 처리중인 노드 인덱스입니다.

i를 루트로하는 왼쪽 및 오른쪽 하위 트리가 최대 힙이라고 가정합니다.

MAX_HEAPIFY를 한 뒤에도 i를 루트로 하는 하위 트리는 최대 힙이어야합니다.

그럼 MAX_HEAPIFY를 해봅시다.

A[i ], A[LEFT(i )] 및 A[RIGHT(i )]를 비교합니다.

만약 비교했을 때 A[i]가 하위 항목 둘 중 하나보다 더 작다면 A[i ]를 두 하위 항목 중 더 큰 항목으로 교환하여 힙 속성을 유지합니다.
i에 루트가 있는 하위 트리가 최대 힙이 될 때까지 힙을 비교하고 교체하는 이 프로세스를 계속합니다. 

리프에 도달하면 리프에 뿌리를 둔 하위 트리는 간단하게 최대 힙입니다.

의사 코드로 보면 위와같이 되겠습니다.

최대 힙 만드는 법 Build-Max-HEAP

앞선 MAX-HEAP으로 최대힙을 만드는게 우리의 목표입니다.

나중에 이 최대힙으로 힙 정렬을 할 것이기 때문에 중요합니다.

최대힙 만드는 과정이 올바르려면 다음의 전제가 있어야합니다.

위에서 다뤘던 MAX-HEAPIFY에서 잠깐 얘기 나온 i의 성질 등 그런겁니다.

1. 루프 불변식 (Loop invariant):
매 반복 시작 시, i+1부터 n까지의 모든 노드가 최대 힙의 루트입니다.
이는 i 이후의 모든 노드가 이미 최대 힙 속성을 만족한다는 의미입니다.

2. 초기화 (Initialization):
[n/2]+1부터 n까지의 노드는 모두 리프 노드입니다.
리프 노드는 자식이 없으므로 자체로 사소한(trivial) 최대 힙입니다.
첫 반복 전 i=[n/2]이므로, 초기 상태에서 불변식이 성립합니다.

3. 유지 (Maintenance):
i 노드의 자식들은 i보다 큰 인덱스를 가집니다.
불변식에 따라, i의 자식들은 이미 최대 힙의 루트입니다.
MAX-HEAPIFY는 i 노드를 최대 힙의 루트로 만듭니다.
i를 감소시키면 다음 반복에서도 불변식이 유지됩니다.

4. 종료 (Termination):
i가 0이 되면 루프가 종료됩니다.
이때 불변식에 의해 모든 노드(특히 루트인 1번 노드)가 최대 힙의 루트가 됩니다.

이제 이 MAX-HEAPIFY로 최대 힙을 만들어봅시다.

MAX-HEAPIFY 시행하기 전부터 이미 최대힙으로 정렬되어있는 힙 노드들을 Primitive Max-heaps라고 합니다.

나머질 정렬해야하니 빨간색 선 순서대로 MAX-HEAPIFY가 진행되는데요.

이렇게 위에서부터 i가 하위 항목보다 작다면 내려가서 하나씩 정렬되고 반복해서 다 정렬될까지 최대힙을 만듭니다.

힙 정렬 HEAP SORT

이제 잘 정렬된 최대힙을 통해 힙 정렬을 해봅시다.

힙 정렬은 결국 힙 자료구조를 이용해서 배열을 정렬하는 알고리즘입니다.

루트 노드와 마지막 노드를 교환해서 루트 노드를 하나씩 배열에 넣어줍니다.

그럼 정렬된 배열이 나오겠죠?

그리고 교환하고 나면 트리가 최대힙이 성립 안될 수도 있습니다.

이 경우 다시 최대힙이 되도록 MAX-HEAPIFY를 해줘야합니다.  

사진을 천천히 둘러보며 집중하시기 바랍니다.

처음 (a)에서 가장 큰 루트노드는 16이고 리프노드는 2 4 1이렇게 있습니다.

이중 가장 마지막 노드인 리프노드 1와 루트노드 16을 교환해주면 됩니다.

교환했을 때 1이 루트노드인데 최대힙이 성립 안되므로 다시 최대힙이 되도록 MAX-HEAPIFY를 해주면

(b)가 나오게 됩니다. 이과정을 반복하는 것이죠

배열로 보면 이렇게 왼쪽 배열이 오른쪽으로 최대힙으로 정렬된 결과를 볼 수 있습니다.

이렇게 MAX-HEAPIFY 정렬되어있는 최대힙을 계속 정렬하면 큰 수 부터 순서대로 정렬된 배열을 얻게됩니다. 

오늘 배운걸 한번 사진으로 정리해보았습니다. 도움이 되셨으면 좋겠네요.

비공식적으로, 알고리즘이란 입력값을 받아 정해진 계산 과정을 통해 원하는 출력값을 얻는 명확하고 체계적인 문제 해결 방법입니다. 컴퓨터가 수행할 수 있는 명확한 단계로 구성되며, 항상 종료되는 특성을 가집니다.

알고리즘은 명확히 정의된 계산 문제를 해결하는 도구로도 볼 수 있습니다. 

문제의 설명은 일반적인 용어로 원하는 입력/출력 관계를 명시합니다. 

알고리즘은 그 입력/출력 관계를 달성하기 위한 구체적인 계산 절차를 설명합니다.

이러한 알고리즘을 이해하기 위해 숫자 정렬 알고리즘을 알아봅시다.

숫자 정렬 알고리즘을 다루는데 두가지 개념이 필요합니다.

• 분할 정복 알고리즘 (Divide-and-Conquer strategy) (젤 마지막에 다룰 예정)
• 함수의 증가 / 점근적 표기법 빅 오 O(n) (Growth of functions / asymptotic notation)

또한 숫자 정렬알고리즘에서의 입력과 출력은 다음과 같습니다.

입력 : n개 숫자의 시퀀스 [a1, a2,..., an]
출력 : a'1, a'2... , a'n과 같은 입력 시퀀스의 순열(재정렬) [a'1, a'2,..., a'n]

손에 있는 카드들을 정렬하기 (삽입 정렬)

우선 카드를 정렬하려면 삽입을 계속 반복적으로 해야됩니다.

이 삽입의 반복에는 한가지 보장해야하는 조건이 있습니다.

바로 루프 불변성입니다.

루프 불변성은 알고리즘의 정확성을 증명하는 중요한 도구입니다. 

이는 루프가 실행되는 동안 항상 참인 조건을 말합니다. 

좀 더 이해하기 쉽게 예시를 들겠습니다.

def sum_to_n(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total

이 코드에서 불변성은 "total이 1부터 i-1이 될 때 까지의 모든 정수와 같다" 입니다.

루프 불변성을 증명하기 위해서는 다음 세 가지 특성을 보여야 합니다:

1. 초기화 (Initialization):
루프가 처음 시작되기 전에 불변성이 참이어야 합니다.
즉, 루프의 첫 번째 반복이 시작되기 전 초기 상태에서 불변성이 성립해야 합니다.

위의 예시에선 total = 0 부분이 되겠네요.

2. 유지 (Maintenance):
루프의 각 반복이 불변성을 유지해야 합니다.
만약 루프 시작 시점에 불변성이 참이라면, 루프 본문 실행 후에도 여전히 참이어야 합니다.
이는 모든 반복에 대해 성립해야 합니다.

위 예시의 각 반복에서 total += i는 total에 i를 더하므로 "total이 1부터 i-1 될때까지의 합"이 유지됩니다. 

3. 종료 (Termination):
루프가 종료될 때, 불변성은 알고리즘의 정확성을 증명하는 데 도움이 되는 유용한 속성을 제공해야 합니다.
루프 종료 조건과 불변성을 결합하여 알고리즘이 원하는 결과를 올바르게 계산했음을 보여야 합니다.

위 예시에서 보면 i가 n이 될 때입니다.

이 세 가지 속성을 모두 증명할 수 있다면, 해당 루프를 포함한 알고리즘이 정확하게 동작한다는 것을 논리적으로 보장할 수 있습니다. 루프 불변성은 특히 복잡한 알고리즘의 정확성을 형식적으로 증명하는 데 매우 유용한 기법입니다.

다시 아까의 카드 삽입 정렬 코드를 봅시다.

1-8행의 for 루프가 반복될 때마다 하위 배열 A[1..j-1]은 원래 A[1..j-1]에 있던 요소들로 구성되지만 정렬된 순서로 구성됩니다.
이 때의 입력 크기는 정렬할 항목 수와 같습니다.

입력 크기 = 정렬할 항목 수(숫자)

우리는 이제 비교 횟수를 계산 해야합니다
젤 좋은 상황에서 가정해봅시다.
Best Case의 경우(입력 시퀀스가 ​​이미 정렬되어 있음) 삽입 정렬에는 n-1 비교가 필요합니다.

어차피 다 정렬되어있으니까 정렬된 부분들이랑 비교할 필요없이 삽입할 요소의 앞, 즉 맨 뒤의 요소랑 비교한번이면 됩니다.

역순정렬

그럼 입력 시퀀스가 역순으로 정렬되어있으면 어떻게 될까요?
다 순서대로 정렬되어있지 않으니 삽입할 때 마다 앞의 요소들이랑 다 비교해야합니다.
맨 앞에 삽입하면 순서대로 되지않겠냐 싶지만 우린 무조건 맨 뒤에 삽입해야합니다.

어쨋든 이로 인해 걸리는 횟수를 공식으로 쓴다면

이런 식을 얻을 수 있습니다.

O(n(n - 1) / 2)는 O(n^2)이라 봐도 되므로 worst case에서 O(n^2)만큼 걸립니다.

점근적 표기법

점근적 표기법에 대해선 아래 포스트가 잘 정리되어있습니다.

https://chayan-memorias.tistory.com/100

시험 문제 풀 때 각 점근적 표기법을 true/false 증명해야할 때 그냥 공식만 외워서 증명하면 됩니다.

점근적 상한 upper bound 빅 오

점근적 하한 lower bound 오메가

점근적 근접선 tight bound 세타

병합 정렬 (Merge Sort)

글의 젤 처음에 분할 정복 알고리즘을 얘기했었습니다.

큰 문제를 작은 하위 문제로 나누고, 각 하위 문제를 해결한 후 결과를 합쳐 문제의 답을 얻습니다.

이 분할 정복 방식을 바탕으로 구현한게 바로 병합 정렬입니다.

뭔가 많이 복잡해보이는데 자세히 집중해서 보면 간단합니다.

배열 A가 L(left)와 R(right)의 작은 배열로 나눠지고

두 배열을 비교해서 작은 값부터 배열 A에 채워줍니다.

i와 j는 각각 L와 R 배열의 비교 위치고,

k는 A에서 값을 채워놓을 위치입니다.

예를 들어 L[1]값 2와 R[1]값 1 비교해서

1이 먼저 A에 들어갑니다.

A = 1

그다음 L[1]와 R[2]를 비교해서 R[2]이 먼저 들어갑니다.

A = 1, 2

그다음 L[1]와 R[3]를 비교해서 L[1]이 들어갑니다.

A = 1, 2, 2

이런식으로 계속 비교해서 A를 채워나가는 알고리즘입니다.

그럼 점근적 표기법을 한번 해볼까요?

느낌이 오셨겠지만 한 쪽이 다른 쪽보다 모두 크거나 작을경우 (Best Case)

n이 전체 배열 크기니깐 그 중 절반은 다 똑같이 정렬될거니 n/2만큼 걸립니다.

이번엔 최악의 경우를 생각해봅시다.

최악의 경우 다 비교해야하니 n - 1만큼 걸립니다.

-1 해주는 이유는 마지막 요소는 비교할 대상이 없으니 그냥 삽입되기 때문입니다. 

그럼 O(n - 1)걸릴테니 그냥 O(n)이라고 봐도 되겠네요.

이제 한번 전체적으로 봅시다.

우린 배열 A를 분할해서 이렇게 각각 삽입할 때 비교 횟수가 최악일 경우 O(n) 걸린다는걸 알게되었습니다.

그러나 전체적으로 보면 배열을 분할했으니 log n 만큼 걸립니다.

(각 비교 횟수 N) * (배열 분할해서 크기가 log N) = N * log N

총 O(n log n)만큼 걸린다는걸 알게되었네요

병합 정렬 재귀적으로 구현

어차피 분할해서 각각 반복적으로 실행될테니 for문이 아니라 재귀적으로 구현할 수 있지않을까요?

사진에서 보다시피 재귀적으로 호출해서 가장 아래부터 병합되는 모습을 볼 수 있습니다. 

분할을 했기 때문에 깊이가 log n만큼 사이즈가 되고 분할된 각 정렬에서 비교 횟수가 cN만큼 걸립니다.

c는 어차피 빅오에선 무시해도 되지만 그래도 가끔 정확한 분석을 위해 상수 c가 앞에 있어야 하는겁니다.

이런 재귀 함수는 시험 문제로 내기 진짜 좋아보이는데요.

재귀적으로 몇 번 호출되었는지 물어보는 문제가 진짜 많이 나옵니다.

트리의 깊이를 보면 log n입니다.

1레벨에선 한번 호출

2레벨에선 2번 호출

3레벨에선 4번 호출

이걸 공식화하면 k레벨에선 2^(k-1)번 호출한다는걸 알 수 있습니다.

그런데 깊이가 log n이므로 k가 log n이 되겠죠?

재귀 호출 횟수는 총 2^(log n - 1) = n - 1가 되겠습니다.

버블 정렬 (Bubble Sort)

지금까지 다룬 삽입 정렬과 병합 정렬 외에도 더욱 대중적인 정렬 알고리즘이 있습니다.

바로 버블 정렬입니다.

자세히 보면 알겠지만 진짜 간단합니다.

맨 뒤부터 앞의 요소보다 수가 작다면 위치를 바꿔서 작은 수부터 큰수까지 정렬되게 만듭니다.

지금까지 다룬 정렬들이 바로 숫자를 정렬하는 알고리즘들이었습니다.

이상입니다.