해당 글은 시험 대비로 급하게 필기한 내용이다.
다음에 기회가 된다면 더 좋은 퀄리티의 글로 바꾸어 나갈 예정이다.
교재가 원서여서
키워드들은 대부분 영단어로 작성할 예정이다.
교재는 Richard E. Neapolitan의 Foundations of Algorithms이다.
세 가지 정렬의 공통된 규칙
시작에 앞서,
위의 세 가지 정렬은
왜 항상 같이 다루는지 알아보자.
위 세 정렬은 하나의 가장 중요한 규칙이 있다:
바로 loop를 한 번 탈출하면
원소 하나가 정확한 위치에 정렬된다는 것이다.
따라서 n개의 원소에 대해
n 번의 loop가 필요하므로
이 알고리즘들은 모두 이중 loop 문으로 나타난다.
결국, Every-Case Time Complexity가 존재하게 되며
그 시간 복잡도는 $\Theta(n^2)$로 나타나게 된다.
결국, 우리가 논의해야 할 것은 두 가지다:
1. 한 원소를 한 번의 loop로 정확한 위치에 정렬시키는 것
2. 처음과 마지막 결과를 통해 loop를 돌릴 control instruction을 고려하는 것
이 이외의 것들은 모델링에 전혀 필요가 없다.
개인적으로, 이 알고리즘의 논리는 매우 쉬워서
일러스트가 오히려 이해를 와해시킨다고 생각하므로
일러스트는 따로 삽입하지 않겠다.
모든 알고리즘은 오름차순 기준으로 설명한다.
Bubble Sort
버블 정렬은 나머지 두 정렬보다도
이해가 훨씬 쉽고 코드가 간결하다.
특히, n이 매우 크지 않다면
연산 속도도 보장되어 있으므로
코딩을 수월하게 할 수 있다.
일단, 이 정렬이 어떤 정렬일지 생각해보자.
버블 정렬이라는 이름이 붙은 이유는
loop문의 과정이 마치 비눗방울이 둥실 떠오르는 것 같기 때문이다.
즉, list S[1..n]에서 큰 값을 계속 뒤로 밀어내는 정렬이다.
구체적으로 말하면
S[i]와 S[i+1]를 비교해서 S[i]가 크면 뒤로 밀어내는 것이다.
그럼, 이것이 올바른 정렬을 이끌어낼 수 있는지
수학적 귀납법을 통해 확인해보자.
S[1]과 S[2]를 비교했을 때 큰 것을 S[2]로 삼으면
S[1..2]에서 최댓값이 된다.
즉, S[2] == max(S[1..2])이다.
그럼, 이 논리를 확장시켜서
S[i] == max(S[1..i])일 때, S[i+1]와 버블 정렬을 해보자.
그럼, S[i+1]은 S[1..i]의 어떤 원소보다 크고
기존의 S[i+1]와도 같거나 크므로
max(S[1..i+1])이 된다는 것은 자명하다.
따라서, loop를 한 번 빠져 나오면 S[i+1]의 값은 max(S[1..i+1])이다.
그럼, 처음 loop로 인하여
최댓값이 맨 끝으로 정렬되었으니
나머지 원소들은 모두 S[n]보다 작다.
그럼, 다시 max(S[1..n-1])를 생각해볼 수 있을 것이고
이는 S[1..n-1]만을 취하여 버블정렬하면 된다.
즉, i의 최댓값을 n부터 하나씩 줄여가면서 loop를 돌리는 것이다.
그럼, 마지막에는 S[1]과 S[2]를 비교하여서 정렬이 될 것이고
S[1]은 고려하지 않더라도 원소가 하나밖에 없으므로
자동으로 최솟값이 된다.
즉, i가 1일 때 loop는 완전히 종료된다.
Time Complexity Analysis
이제부터는 간단히 의사코드를 구현해보겠다.
i가 1부터 n - 1까지를 loop로 삼고
그 이후로 n 부분을 계속 1씩 줄여가다가
i가 1부터 1까지인 loop가 끝나면 버블정렬은 종료된다.
Bubble Sort:
for j from n-1 to 1
for i from 1 to j
if(S[i] > S[i+1]) // (1) excute time once: c1
exchange S[i] and S[i+1] // (2) excute time once: c2
사실상 연산 횟수는 n에만 비레하므로
(1) 연산은 Every-Case Time Complexity로 둘 수 있다.
그러나, (2) 연산은 실행될 수도 있고 아닐 수도 있으므로
최악 시간 복잡도만을 고려해보자.
최악 시간 복잡도는 list가 완전히 반대로 정렬된 경우가 된다.
계속해서 앞의 원소가 끝으로 가기만 할 뿐이므로
S[1..n-1]는 계속해서 반대로 정렬되어 있을 것이다.
따라서, (1)과 (2)의 계산량이 완전히 같아진다.
즉, for문이 $\sum\limits_{k=1}^{n-1}\sum\limits_1^k 1 = \sum\limits_{k=1}^{n-1} k=\cfrac{n(n-1)}{2}$번 실행되므로
총 실행시간은 $W(n) = (c_1+c_2)\cfrac{n(n-1)}{2} \in \Theta (n^2)$이다.
만약 (2)가 이보다 작게 실행되더라도
이미 (1)의 연산이 $\Theta(n^2)$의
고정적인 시간 복잡도를 이루므로
평균 시간 복잡도도 마찬가지로 $\Theta(n^2)$이다.
따라서, 최선, 평균, 최악 시간 복잡도가 모두 $\Theta(n^2)$이다.
이제 이를 C언어로 구현해보자.
#include <stdio.h>
void bubble_sort(int *S, int n) {
int i, j;
for(j = n-1; j > 0; j--) {
for(i = 0; i < j; i++) {
if(S[i] > S[i + 1]) {
// exchange S[i] and S[i+1]
int temp;
temp = S[i];
S[i] = S[i+1];
S[i+1] = temp;
}
}
}
}
인덱싱과 for문의 부등식을 고려하면 의사코드와 차이가 있지만,
코드가 매우 간결하고 깔끔한 것을 알 수 있다.
Insertion Sort
버블정렬은 대소 비교를 하는 두 원소가
계속해서 변하는 정렬이지만
삽입정렬은 오직 한 원소만을 기준으로
계속해서 비교해 나가는 정렬이다.
물론, 초기 연산은 버블 정렬과 비슷하다:
list S[1..n]을 입력받았을 때,
remember = S[i]로 대입하고
이 remember가 S[i-1]보다 작은지 비교하여
그렇다면 S[i-1]의 원소를 S[i]로 밀어내는 것이다.
(앞의 버블정렬과 구체적인 방식은 다르지만
개략적인 매커니즘은 같다.)
여기까지는 원소를 교환하지 않고 밀어내는 것만 제외하면
버블정렬의 원리와 크게 다른 것 같지 않아 보인다.
계속해서 삽입정렬이 진행되면서
버블 정렬과의 분기점이 발생하는데,
버블정렬에서는 S[i]가 S[i-1]보다 작지 않다면
아무것도 교환하지 않은 후,
S[i-1]과 S[i-2]를 비교할 것이다.
그러나, 삽입 정렬은
더이상 S[i]가 S[i-1]보다 작지 않다면
앞에서 S[i-1]들을 밀어내고 남는 자리에
remember를 삽입하고 한 loop가 끝이 난다.
왜냐하면 이 이후의 연산은
remember에 대한 비교를 수행할 수 없기 때문이다.
그럼, 순전히 버블정렬을 하다 만 것 아닌가 싶지만
이 정렬이 처음부터 작동하는 과정을 보면
삽입 정렬이 어떻게 list를 정렬하는지 확인할 수 있다.
우선, 첫번째 loop는 S[2]와 S[1]을 비교해야 한다.
이 중, 작은 것이 S[1]로 오므로
S[1]과 S[2]가 정렬된다.
S[3]을 정렬할 때는
S[1]과 S[2]와 S[3]의 대소관계가
$S[1] \leq S[2] \leq S[3]$가 되도록 정렬하게 된다.
왜냐하면 S[3]보다 작은 원소가 나올 때까지
S[3]는 계속 앞으로 이동되면
당연히 그 뒤의 원소는 S[3]보다 클 것이고
그 앞의 원소는 S[3]보다 작을 것이기 때문이다.
(참고로 S[1..3] 내에서만 그렇다.)
그 대소관계 순서를 S[1] S[2] S[3]으로 인덱싱하게 되면
S[1] S[2] S[3]은 오름차순으로 정렬된다.
그럼, $S[1..i]$까지가 정렬되었을 때
S[i+1]에 대해 삽입정렬을 시도하면 어떻게 될까?
이 말은, 원소들을 크기 순으로 나열하면
S[1] S[2] S[3] ... S[k] S[i+1] S[k+1] ... S[n]으로 두겠다는 의미이다.
그리고 여기서 인덱싱을 다시 S[1] S[2] ... S[n]으로 매기겠다는 의미이므로
다시 모든 j에 대해 S[j] <= S[j+1]의 관계가 된다.
즉, S[1..i+1]도 정렬된 list가 된다.
너무나도 당연한 결과인지라
버블정렬보다 더 원초적인 정렬이 아닌가 싶지만
조건문을 달아야 하므로
구현은 아주 조금 더 복잡해진다.
Time Complexity Analysis
이제 의사코드를 구현해보겠다.
일단, S[1..n]을 입력받는다고 하면
모든 원소에 대해 삽입정렬해야 하므로
i는 1부터 n까지 모두 대입될 것이다.
일단, remember = S[i]로 대입하고
S[i-1]부터 계속하여 인덱스를 감소시키며 remember와 비교한다.
remember라는 변수에 따로 저장하는 이유는 무엇일까?
당장 S[i-1]가 S[i]보다 크면
S[i-1]가 밀어져서 S[i]의 자리에 놓이게 된다.
따라서 remember는 언제든지 지워질 수 있는 처지이기 때문에
미리 변수에 따로 저장해야 한다.
S[i-1]가 remember보다 작다면
S[i-1]을 S[i]에 대입하고
S[i-2]와의 비교로 넘어간다.
그렇지 않다면 하나의 loop를 종료한다.
그리고 remember를
마지막으로 옮겨졌던 원소의 원래 자리에 넣는다.
간단하게 생각하면
remember보다 큰 원소를 다 한 칸 밀어냈다고 했는데,
그렇게 되면 remember 자리는 다른 원소로 덮어 씌워지고
loop를 탈출하기 전의 원소까지 한 칸 옆으로 옮겨진다.
그럼 탈출하기 전의 원소의 원래 자리는?
우리는 밀어내는 연산을
단지 옆 칸에 대입함으로써 수행하므로
그 원소가 그대로 존재하게 된다.
즉, 의미 없는 빈칸인 것이다.
그래서, 그 자리에 remember를 삽입하는 것이다.
그럼, 더이상 remember < S[i]를 만족하지 않는 i를 가지고
loop를 탈출하게 되는데
우리는 그 i가 필요한 게 아니고
그 이전의 i 자리가 필요한 것이므로
S[i+1]에 remeber를 대입하여야 한다는 점 주의하자.
이 알고리즘은
또 한 가지 맹점을 가지고 있는데,
i가 계속 줄어들면서 비교하므로
가장 말단인 S[1]까지만 비교하도록 하여야 한다.
따라서, S[1]까지 밀어지면
마찬가지로 반복문을 탈출하고 S[1]에 원소를 대입하여야 한다.
그럼 반복문 탈출 시, i = 0이 되도록 하면
S[i+1] == S[1]에 remember를 대입할 수 있다.
insertion_sort (ins *S, int n) {
for j from 2 to n // j=1에서는 이미 정렬된 상태로 간주
remember = S[j]
i = j - 1 // S[j]에 대해 비교하므로 i는 j-1부터 감소
while(i > 0, S[i] > remember) // c1
S[i+1] = S[i] // 한 칸씩 밀어내기, c2
S[i+1] = remember // 탈출 시 빈 자리에 remember 대입
}
확실히 버블정렬보다 구조가 조금 복잡하다.
그러나, 이 글 다음에 소개할 3개의 정렬에 비하면
꽤 단순한 구조라는 것만 알아두자.
일단 평균 시간 복잡도를 구하는 것이 어려우므로
일단 최선, 최악 시간 복잡도만 생각해보자.
그나마 다행인 건 버블정렬과는 달리
every-case time complexity가 $\Theta(n)$의 형태로 존재한다는 것이다.
(j에 대한 for문)
따라서, 리스트가 오름차순으로 정렬되어 있다면
S[i]를 비교할 때마다 항상 remember보다 작으므로
바로 loop를 빠져 나오면서 c2 연산이 한 번으로 끝난다.
즉, c2 연산 횟수는 c1 연산 횟수와 같다.
결국, $B(n)=(c_1+c_2)(n-1)\in \Theta(n)$이 되면서
최선의 경우, 버블정렬보다 우위에 서게 된다.
(그러나, 버블정렬도 최선의 경우에 선형시간의 시간 복잡도를 가지도록
개조하는 방법이 있다고 한다. 자세한 사항은 검색해보자.)
최악의 경우는
계속해서 remember를 원소를 S[1]까지 옮기는 케이스로,
내림차순으로 정렬된 list가 될 것이다.
그럼, c2의 초기 실행은 i = 1부터 시작할 것이고
S[n]을 S[n-(n-1)] = S[1]까지 옮기는 데 실행횟수는 n-1이므로
$\sum\limits_{k=1}^{n-1} k = \cfrac{n(n-1)}{2}$이다.
결국, j for문에 대한 Every-case time complexity는 무시되고
$W(n) \in\Theta (n^2)$이 된다.
평균 시간 복잡도를 구하는 것은 쉽지 않다.
버블정렬에서 사용하였던 Ever-case time complexity를 고려할 수 없기 때문이다.
그렇다 보니, 이 내용을 다루는 블로그 글이 잘 없어서
내가 직접 확률과 통계 지식으로 풀어보았다.
결국, 이 문제는 k-1번째 while까지 S[i] > remember이다가
k번째 while에서 S[i] <= remember이어야 한다는 것인데,
확률 통계 과목으로 고생을 좀 해봤다면
이는 기하 확률분포와 관련되어 있다는 것을 알 수 있다.
(내용이 조금 장황하므로, 관련 내용은 교재를 참조하자.)
우리의 목표는 그 기댓값을 구하는 것이므로
기하 분포의 기댓값 $E(x) = \cfrac{1}{p}$를 이용한다.
이때, $p$는 S[i] <= remember를 만족할 확률이다.
그런데, 우리가 이 $p$를 알기 위해서는
list 전체 원소에 대한 정보가 필요하므로
$p$는 정확히 알 수 없다.
결국, remember = S[i]에 대한 비교 연산 횟수를 $p_i$라 하고
그 list 내에서 S[i] <= remember가 성립할 수 있는 원소의 개수를 $n_i$라 하면
$\sum\limits_{i=2}^n \cfrac{1}{p_i} = \sum\limits_{i=2}^n \cfrac{i-1}{n_i}$
$\leq\sum\limits_{i=2}^n (i-1) =\cfrac{n(n+1)}{2}-1-(n-1)$이므로
평균 시간복잡도는 $O(n^2)$이 된다는 것을 알 수 있다.
($\Theta(n^2)$가 아니다!)
이제부터 삽입정렬을 C언어로 구현해보자.
#include <stdio.h>
void insertion_sort(int *S, int n) {
int i, j;
// 최소한 i의 while문의 overhead instruction으로
// i를 선언해야 함에 주의하자.
for (j = 1; j < n; j++) { // 의사코드와 인덱싱 차이
int remember = S[j];
i = j-1;
while(i > -1 && S[i] > remember) { // 의사코드와 인덱싱 차이
if( S[i] > remember) S[i+1] = S[i]; // S[i]을 밀어냄
i--;
}
S[i+1] = remember;
}
}
의사 코드를 잘 이해하였다면
이 코드를 구현하는 것이 그리 어렵지는 않았으리라 생각한다.
Selection Sort
남은 것은 선택 정렬인데
특이하게도 세 개의 정렬 방식 중
이해하기는 가장 쉽다.
원리는 굉장히 단순하다:
S[1..n] 중 최솟값을 찾아서 S[1]에 둔다.
S[i..n] 중 최솟값을 찾아서 S[i]에 둔다.
굉장히 직관적이다 보니
정렬이 되는지 확인해볼 필요가 딱히 없겠지만
일관성을 위해 설명은 하겠다.
S[1..n]에서 최솟값을 S[1]에 두면,
S[1..n]의 모든 원소에 $a$ 대해 S[1] $\leq a$를 만족한다.
그럼 S[i..n]에서 S[i]는 S[i..n]의
모든 원소보다 작거나 같을 것이라고 추론할 수 있다.
그러나, S[i-1]은 항상 S[i-1..n]의 모든 원소보다 작거나 같기 때문에
무슨 일이 있더라도 S[i-1] <= S[i]를 만족한다.
선택정렬이 한 번 시행될 때마다
S[1], S[2], S[3] ... 의 형태로 정렬되다가
S[n-1]이 정렬되면 자동으로 S[n]이 결정되므로
S[n-1..n]에 대한 비교가 마지막 비교이며,
전체 시행 횟수는 n-1회가 된다.
따라서, n-1회의 선택정렬 이후에는
모든 가능한 i에 대해 S[i] <= S[i+1]을 만족하게 되므로
S는 오름차순으로 정렬된다.
아무튼, 정렬된다는 것을 알았으므로
우리가 해야 할 것은
하나의 loop가 끝날 때
이 지점의 최솟값을 도출하는 것이다.
이에 대해서는 S[i..n]의 값을 모두 비교하면서
S[minimum] > S[k]이면 k를
minimum으로 갱신하는 방법이 주로 쓰인다.
굳이 minimum 자체를 S[i]와 비교하지 않고
S[minimum]으로 비교하는지에 대해 말하자면,
결국, minimum을 구하는 이유는
최솟값이 발생한 위치의 원소와
정해진 위치의 원소를 교환하기 위해서이다.
따라서, 값의 정보만을 담게 되는 minimum와의 비교는
선택정렬에 쓰기엔 부적절하다.
또한, 초기값으로 minimum = 0을 할당하게 되면
S의 원소가 모두 0보다 클 때, 논리 오류가 발생하게 되는 등
알고리즘에 여러 문제점을 남기게 된다.
Time Complexity Analysis
이제 의사코드를 구현해보겠다.
일단, S[1..n]부터 정렬하기 시작하면 된다.
S[i..n]에서 최솟값을 찾기 위해서는
초기값으로
일단 minimum = i를 대입하여
S[minimum] == S[i]으로 두고
j를 i부터 n까지 증가시켜가면서
S[minimum] > S[j]가 만족된다면
S[minimum] = S[j]으로 대입하는 방식을 취한다.
이렇게 만들어진 최솟값을 S[i]에 대입하면 된다.
selection_sort (int *S, int n) {
for j from 1 to n-1 // S[n]은 자동으로 정렬됨
minimum = j
for i from j+1 to n // S[j]가 이미 minimum이므로 S[j]와의 비교는 제외됨
do if S[i] < S[minimum] //c1
then minimum = i // 최솟값 갱신
exchange A[j] and A[minimum] // for 문 이탈 후, 정렬 :c2
}
이미 Every-case time complexity로
$\sum\limits_{j=1}^{n-1}\sum\limits^{j+(n-j)}_{j+1}1=\sum\limits_{j=1}^{n-1}(n-j)$
$=\cfrac{n(n-1)}{2}\in\Theta(n^2)$를 수반한다는 부분에서
최선, 평균, 최악 시간 복잡도가 모두 $\Theta(n^2)$임을 알 수 있다.
이제부터는 선택정렬을 C언어로 구현해보자.
#include <stdio.h>
void selection_sort(int *S, int n) {
int i, j;
for(j = 0; j < n - 1; j++) { // 의사코드와 인덱싱 차이
int temp;
int minimum = j; // 초기값 설정
for(i = j+1; i < n; i++) { // minimum 찾기
if(S[i] < S[minimum])
minimum = i;
}
temp = S[j]; // 최솟값을 S[j]와 교환
S[j] = S[minimum];
S[minimum] = temp;
}
}
삽입정렬과 비슷한 수준의 코드가 나왔음을 확인할 수 있다.
이번엔 평균 시간 복잡도가 모두 $O(n^2)$인
세 가지 정렬 방식에 대해 알아보았다.
다음 글부터는 $O(n\log n)$ 수준의 정렬 방식에 대해 알아볼 것이다.
여러 정렬을 한 글에 담는 건 너무 길어지는 것 같아서
다음 글부터는 정렬 방식을 하나씩만 올리겠다.
'컴퓨터 알고리즘 (학부)' 카테고리의 다른 글
| [알고리즘 필기] 2-3. 합병정렬 (0) | 2025.04.18 |
|---|---|
| [알고리즘 필기] 2-1. 분할정복 알고리즘, 이진 검색 (1) | 2025.04.16 |
| [알고리즘 필기] 1. 알고리즘과 시간 복잡도 (0) | 2025.04.16 |