각종 정렬 알고리즘을 소개하고자 합니다. 알고르짐을 코드 레벨에서 분석만 한다면 지루할 수 있습니다. 이보다는 각각의 알고리즘이 갖는 특징에 관심을 두고 공부하는 것이 오래 남고 더 의미가 있을 것입니다.
버블 정렬 이해와 구현
버블 정렬은 정렬의 대명사로 알려져 있는, 여러분이 알고 있을만한 정렬방법입니다. 이해하기도 구현하기도 쉽습니다. 물론 이해와 구현이 쉬운 만큼 성능에는 아쉬움이 있습니다. 그럼 3, 2, 4, 1이 순서대로 저장된 다음 그림의 배열을 오름차순(값이 클수록 뒤에 위치시키는 방법)으로 정렬하는 과정을 보이면서 버블 정렬의 과정을 소개하겠습니다. 버블 정렬은 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식입니다. 두 데이터를 비교하여, 정렬순서상 위치가 바뀌어야 하는 경우에 두 데이터의 위치를 바꿔나갑니다. 즉, 위 그림에서 보이는 작업은 다음과 같이 말할 수 있습니다.
정렬의 우선순위가 가장 낮은, 제일 큰 값을 맨 뒤로 보냅니다. 따라서 위의 과정을 한차례 진행했다고 해서 정렬이 완료되는 것이 아닙니다. 두 번째로 큰 값을 맨 뒤에서 한 칸 앞으로 보내기를 해야 합니다. 배열의 끝에 위치한 데이터를 제외하고 나머지를 대상으로 비교와 교환을 진행하였습니다. 그 결과 두 번쨰의 큰 값이 맨 뒤에서 한 칸 앞에 위치하게 되었습니다. 이로써 두 개의 데이터만 더 정렬을 하면 완전히 정렬된 상태가 됩니다. 2와 1의 위치를 바꿈으로써 정렬이 완료되었습니다. 앞에서부터 순서대로 비교하고 교환하는 일련의 과정이 거품이 일어나는 모습에 비유되어 버블 정렬이라 이름 지어진 것입니다.
#include <stdio.h> void BubbleSort(int arr[], int n) { int i, j; int temp; for (i = 0; i < n - 1; i++) { for (j = 0; j < (n - i) - 1; j++) { if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } } int main(void) { int arr[4] = { 3, 2, 4, 1 }; int i; BubbleSort(arr, sizeof(arr) / sizeof(int)); for (i = 0; i < 4; i++) printf("%d ", arr[i]); printf("\n"); return 0; } |
버블 정렬을 구성하는 두 for문의 반복조건이 핵심입니다. 따라서 바깥쪽 for문의 반복조건과 안쪽 for문의 반복조건에 대해서 대략적인 이해가 아니라 정확한 이해가 필요합니다.
버블 정렬 성능 평가
정렬 알고리즘의 성능은 다음 두 가지를 근거로 판단하는 것이 일반적입니다. 비교연산과 데이터의 이동을 위한 대입연산이 정렬과정의 핵심연산이기 때문입니다. 비교의 횟수 두 데이터 간의 비교연산의 횟수, 이동의 횟수 위치의 변경을 위한 데이터의 이동 횟수. 실제로 시간 복잡도에 대한 빅오를 결정하는 기준은 비교의 횟수 입니다. 하지만 이동의 횟수까지 살펴보면 동일한 빅-오의 복잡도를 갖는 알고리즘간의 세밀한 비교가 가능합니다. 버블 정렬의 비교횟수는 다음 반복문 안에 위치한 if 문의 실행 횟수를 기준으로 계산할 수 있습니다. 등차 수열의 합에 해당하므로 다음과 같이 정리가 됩니다.
따라서 버블 정렬의 비교 연산에 대한 빅-오는 최악의 경우와 최선의 경우 구분 없이 다음과 같습니다. 단순히 보면 반복문이 중첩되어 있을 뿐인데, 이렇듯 실제 활용하기 부담스러운 정도의 성능을 보이비다. 그렇다면 데이터의 이동횟수는 어떨까요. 이는 최선의 경우와 최악의 경우가 구분이 됩니다.
선택 정렬 이해와 구현
이번에 소개하는 선택 정렬은 버블 정렬보다도 쉽고 간단한 알고리즘입니다. 1, 2, 4, 3이 나란히 저장된 배열의 오름차순 정렬과정을 보이는데, 이해할 수 있을 정도로 간단합니다. 선택 정렬은 정렬순서에 맞게 하나씩 선택해서 옮기는, 옮기면서 정렬이 되게 하는 알고리즘입니다. 선택 정렬은 정렬결과를 담을 별도의 메모리 공간이 필요합니다. 위 그림에서 보이는 대로 진행을 한다면 별도의 메모리 공간이 필요합니다. 데이터를 하나 옮길 때마다 공간이 하나씩 비게 된다는 사실을 기반으로, 정렬순서상 가장 앞서는 것을 선택해서 가장 왼쪽으로 이동시키고, 원래 그 자리에 있던 데이터는 빈자리에 가져다 놓는다. 빈 자리를 활용하는 과정에서 비롯된 교환이란 사실을 이해합니다.
#include <stdio.h> void SelSort(int arr[], int n) { int i, j; int maxIdx; int temp; for (i = 0; i < n - 1; i++) { maxIdx = i; for (j = i + 1; j < n; j++) { if(arr[j]<arr[maxIdx]) maxIdx = j; } temp = arr[i]; arr[i] = arr[maxIdx]; arr[maxIdx] = temp; } } int main(void) { int arr[4] = { 3, 4, 2, 1 }; int i; SelSort(arr, sizeof(arr) / sizeof(int)); for (i = 0; i < 4; i++) printf("%d ", arr[i]); printf("\n"); return 0; } |
선택 정렬 성능 평가
선택 정렬의 코드만 봐도 버블 정렬과 성능상 큰 차이가 없음을 알 수 있습니다. 그럼 비교횟수의 확인을 위해서 선택 정렬의 일부인 다음 반복문을 봅니다. 즉, 비교연산의 횟수는 다음과 같이 정리가 가능합니다. (n-1) + (n-2) + ... + 2 + 1 이는 버블 정렬의 경우와 똑같습니다. 따라서 선택 정렬의 빅-오 역시 최악의 경우와 최선의 경우 구분 없이 다음과 같습니다. 언뜻 생각하기에는 버블 정렬보다 나은 성능을 보장할 것처럼 보였는데, 비교횟수를 기준으로 보면 차이가 없음을 알 수 있습니다. 그렇다면 데이터의 이동횟수도 버블 정렬고 차이가 없을까요. 버블 정렬이나 선택 정렬이나 데이터의 교환을 위한 세 번의 대입 연산이 다음과 같은 유형으로 진행됩니다. 선택 정렬의 경우 n-1회의 교환이 이뤄지므로 데이터의 이동횟수는 이의 세 배인 3(n-1)이 됩니다. 따라서 선택 정렬의 데이터 이동연산에 대한 빅오는, 최악의 경우와 최선의 경우 구분 없이 다음과 같습니다.
최악의 경우를 놓고 보면 버블 정렬보다 선택 정렬에 좋은 성능을 기대할 수 있겠지만, 버블 정렬은 최선의 경우에 단 한 번의 데이터 이동도 발생하지 않는다는 점과, 실제로 데이터들이 늘 최악의 상황으로 배치되지는 않는다는 사실을 감안하면, 이 둘의 우여을 가리는 것은 무의미하다고 할 수 있습니다.
삽입 정렬 : 이해와 구현
배열은 정렬이 완료된 부분과 완료되지 않는 부분으로 나뉘어 있습니다. 이렇듯 삽입 정렬은 정렬 대상을 두 부분으로 나눠서, 정렬 안 된 부분에 있는 데이터를 정렬 된 부분의 특정 위치에 삽입해 가면서 정렬을 진행하는 알고리즘입니다. 첫 번째 데이터와 두 번째 데이터를 비교하여, 정렬이 완료된 영역의 다음에 위치한 데이터가 그 다음 정렬 대상입니다. 삽입할 위치를 발견하고 데이터를 한 칸씩 뒤로 밀수도 있지만, 데이터를 한 칸씩 뒤로 밀면서 삽입할 위치를 찾을 수도 있습니다. 삽입위치를 찾는 과정과 삽입을 위한 공간마련의 과정을 구분할 필요가 없습니다. 어차피 정렬된 영역에서 삽입의 위치를 찾는 것이니, 삽입 위치를 찾으면서 삽입을 위한 공간의 마련을 병행 할 수 있는 것이니다.
#include <stdio.h> void InserSort(int arr[], int n) { int i, j; int insData; for (i = 1; i < n; i++) { insData = arr[i]; for (j = i - 1; j >= 0; j--) { if (arr[j] > insData) arr[j + 1] = arr[j]; else break; } arr[j + 1] = insData; } } int main(void) { int arr[5] = { 5, 3, 2, 4, 1 }; int i; InserSort(arr, sizeof(arr)/sizeof(int)); for (i = 0; i < 5; i++) printf("%d ", arr[i]); printf("\n"); return 0; } |
복잡하지만 효율적인 정렬 알고리즘
단순한 정렬 알고리즘들도 정렬대상의 수가 적은 경우 효율적으로 사용할 수 있어서 나름의 의미를 집니다. 정렬대상의 수가 적지 않은 경우에는 보다 만족스러운 결과를 보자하는 알고리즘이 필요합니다.
힙 정렬: 이해와 구현
실제로 공부해보면 어려운 알고리즘은 아니라고 느낄 것입니다. 기발한 정렬 방식에 나름 재미를 느끼지 않을까, 필자 개인적으로 그렇게 생각합니다. 힙 정렬은 힙을 이용한 정렬 방식으로 여러분이 앞서 힙을 제대로 공부했다면 별도로 더 공부할 것이 없는 알고리즘입니다. 힙의 루트 노드에 저장된 값이 가장 커야 합니다. 최대 힙의 특징입니다. 힙의 루트 노드에 저장된 값이 정렬순서상 가장 앞섭니다. 힙의 루트 노드에 저장된 값이 정렬 순서상 가장 앞섭니다.
보시다시피 정렬의 대상인 데이터들을 힙에 넣었다가 꺼내는 것이 전부입니다. 그럼에도 불구하고 정렬이 완료되는 이유는, 꺼낼 때 힙의 루트 노드에 저장된 데이터가 반환되기 때문입니다. 힙은 저장의 목적 이외에 정렬의 도구로도 사용이 될 수 있습니다.
숫자 2는 빅오에서 무시할만한 수준이므로 삽입과 삭제를 하나의 연산으로 묶는다 해도, 이 연산에 대한 시간 복잡도는 여전히 다음과 같습니다.