숫자 정렬 알고리즘 Sorting of Numbers

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

 

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

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

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

 

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

 

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

• 분할 정복 알고리즘 (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

알고리즘 이론 2강. 점근적 표기법(Asymptotic notation)

 

시험 문제 풀 때 각 점근적 표기법을 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)

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

바로 버블 정렬입니다.

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

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

 

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

이상입니다.