알고리즘 1-1강. 정렬
[알고리즘 강좌]
데이터를 빠르고 쉽게
정렬 알고리즘(sorting algorithm)
정렬의 사전적 의미는 '데이터를 특정한 조건에 따라 일정한 순서가 되도록 다시 배열하는 일'를 말하는 것으로 예를들자면 학교에서 각 반 학생들을 키 순으로 세우는 것, 제목 순으로 정리하는 것 등 이것 모두가 '정렬'입니다.
지금부터 소개하고자 하는 '정렬 알고리즘(sorting algorithm)'을 사용하면 편하게 데이터를 찾을 수 있게됩니다.
1. 버블 정렬(Bubble Sort) 뽀글뽀글 뽀글뽀글!
지금부터 소개하고자 하는 버블 정렬은 정렬 알고리즘 중 활용도가 높은 알고리즘이며, 구현도 쉽게 가능하여 많은 프로그래머들이 즐겨 쓰는 알고리즘 입니다. 버블 정렬은 데이터를 차례대로 정렬하는 과정이 수중 거품의 움직임과 유사하여 거품 정렬이라고도 부릅니다.
[버블 정렬(Bubble sort)의 예]
버블 정렬은 자신과 인접한 데이터와 비교하여 정렬하는 방식입니다. 위의 예를 보시면 첫번째로 84와 69를 비교하여 84가 더 큰걸 확인하고 위치를 바꾸었습니다. 또다시 84와 76을 비교하여 84가 더 큰걸 확인하고 위치를 바꾸고, 84와 86을 비교하여 84가 작으므로 데이터의 위치를 바꾸지 않고 다음으로 넘어갑니다.
이렇게 정렬을 하다, 더이상 위치 교환이 일어나지 않게되면 루프를 빠져나옵니다. 그렇다면 이 버블 정렬은 얼마나 빠른것일까요? 한번 순회를 할때마다 교환이 일어나는 범위가 하나씩 줄어듭니다. 만약 어느 데이터 집합에 데이터가 n개 존재한다면 n-1만큼 반복해야 정렬이 끝납니다. 이 정렬의 비교 횟수를 알아볼까요?
버블 정렬의 비교 횟수 = (n-1)+(n-2)+(n-3)+...+(n-(n-2))+(n-(n-1)) = (n-1)+(n-2)+(n-3)+...+3+2+1 = n(n-1)/2
이 식을 이용하여 10000개의 데이터가 존재한다면 49,995,000번의 데이터 교환이 일어납니다. 버블 정렬 알고리즘의 시간 복잡도를 계산하면 O(n^2), n값이 증가하면 실행 시간이 기하급수적으로 늘어나게 됩니다. 여기서 시간 복잡도란 무엇일까? 시간 복잡도란 문제의 크기에 따라 걸리는 시간이며 보통 빅 O표기법을 사용합니다.
그럼 우리가 직접 버블 정렬을 구현해보도록 할까요?
#include <stdio.h>
#include <stdlib.h>
void BubbleSort(int DataArray[], int Length)
{
int i = 0, j = 0, temp = 0;
for (i=0; i<Length-1; i++)
{
for (j=0; j<Length-(i+1); j++)
{
if (DataArray[j]>DataArray[j+1]) {
temp = DataArray[j+1];
DataArray[j+1] = DataArray[j];
DataArray[j] = temp;
}
}
}
}
int main()
{
int * DataArray;
int i = 0;
int Length;
printf("배열의 크기를 선언하십시오: ");
scanf("%d", &Length);
DataArray = (int*) malloc (sizeof(int)*Length);
printf("\n");
printf("%d개의 배열 원소(정수)를 입력하십시오: ", Length);
for(i=0; i<Length; i++) scanf("%d", &DataArray[i]);
BubbleSort(DataArray, Length);
for (i=0; i<Length; i++) printf("%d", DataArray[i]);
printf("\n");
return 0;
}
이 예제를 컴파일 후 실행하면,
배열의 크기를 선언하십시오: 5
5개의 배열 원소(정수)를 입력하십시오: 7 5 4 3 2
2 3 4 5 7
와 같은 결과를 얻을 수 있습니다. 차례대로 정리해보면 7과 5를 비교하여 7이 더 크므로 위치 교환이 일어납니다. 그 후 7과 4를 비교하여 7이 더 크므로 다시 한번 위치 교환이 일어납니다. 그리고 3과 비교하여 다시 한번, 2와 비교하여 다시 한번이 일어나 5 4 3 2 7이 되며 하나하나씩 정렬이 되어가기 시작합니다.
5 4 3 2 7 -> 4 3 2 5 7 -> 3 2 4 5 7 -> 2 3 4 5 7
뒤에서 부터 차츰차츰 정렬되어 더이상 위치 교환이 일어나지 않으면 버블 정렬이 끝납니다.
[버블 정렬의 움직임]
2. 삽입 정렬(Insertion Sort) 카드가 왔다갔다!
앞에서 버블 정렬을 알아보았는데, 이번에는 삽입 정렬이라니! 삽입 정렬은 도대체 어떤 정렬 방식일까요? 간단히 말하면 삽입 정렬은 정렬할 새로운 데이터를 뽑아 적당한 새 위치에 삽입하는 알고리즘이라고 말할 수 있습니다. 삽입 정렬도 버블 정렬과 마찬가지로 구현이 간단하여 많이 사용이 되기도 합니다. 우선 인접한 데이터와 비교하여 정렬하는 방식인 버블 정렬과 어떠한 차이점을 보이는지 아래 과정을 보며 생각해보도록 합시다.
위 그림에서의 과정을 글로 나타내면 아래와 같습니다.
1. 3과 4를 뽑아 어느게 더 큰지 비교한다. -> 4가 크므로 변동이 없다.
2. 4와 6을 뽑아 어느게 더 큰지 비교한다. -> 6이 크므로 변동이 없다.
3. 6과 2를 뽑아 어느게 더 큰지 비교한다. -> 6이 더 크므로, 2를 뽑아 3 앞에 삽입한다.
4. 6과 8을 뽑아 어느게 더 큰지 비교한다. -> 8이 크므로 변동이 없다.
5. 8과 1을 뽑아 어느게 더 큰지 비교한다. -> 8이 더 크므로, 1을 뽑아 2 앞에 삽입한다.
이제 삽입 정렬이 어떤 정렬 방식인지 조금이라도 아셨나요? 정렬될 필요성이 있는 데이터를 뽑아 이 데이터를 적절한 위치에 삽입하는 것입니다. 삽입 정렬의 비교횟수는 버블 정렬보다 조금 더 나은면을 보입니다. 시간 복잡도는 최선의 경우 O(n)이며, 최악의 경우는 O(n^2)를 보입니다. 평균 시간 복잡도도 O(n^2) 입니다.
삽입 정렬의 비교 횟수 = 1+2+3+...+(n-3)+(n-2)+(n-1) = n(n-1)/2
(삽입 정렬의 평균 비교 횟수는 n(n-1)/4이며, 최선의 경우에는 n-1번의 정렬이 이루어집니다.)
이 삽입 정렬을 코드로 표현하자면 아래와 같습니다.
#include <stdio.h>
#include <string.h>
void PrintArray(int arrData[], int Length)
{
for (int i = 0; i < Length; i++)
printf("%d ", arrData[i]);
printf("\n");
}
void InsertionSort(int arrData[], int Length)
{
int value = 0;
for (int i = 1; i < Length; i++)
{
// 정렬할 필요성이 없다면 한 회 넘어간다.
if (arrData[i - 1] <= arrData[i]) continue;
value = arrData[i];
for(int j = 0; j < i; j++)
{
// value 보다 큰 요소를 찾아낸다.
if (arrData[j] > value)
{
// 여기서 memmove 함수는 메모리 블럭을 옮기는 함수입니다.
// 아래 문장을 해석하면, &arrData[j] 부터 sizeof(arrData[0]) * (i-j)만큼 &arrData[j+1]로 이동한다는 말입니다.
memmove(&arrData[j+1], &arrData[j], sizeof(arrData[0]) * (i-j));
arrData[j] = value;
break;
}
}
PrintArray(arrData, Length);
}
}
int main()
{
int arrData[] = {3, 4, 6, 2, 8, 1};
int Length = sizeof arrData / sizeof arrData[0];
PrintArray(arrData, Length);
InsertionSort(arrData, Length);
return 0;
}
결과:
3 4 6 2 8 1
2 3 4 6 8 1
1 2 3 4 6 8
계속하려면 아무 키나 누르십시오 . . .
코드를 먼저 보시면, 삽입 정렬 함수의 반복문 내에 continue문을 사용하여 정렬할 필요성이 없는 데이터는 그냥 넘어가게 두었습니다. 그리고 정렬될때마다 결과를 확인할 수 있도록 PrintArray 함수를 정렬이 일어날 때 마다 호출하도록 하였습니다. 이 삽입 정렬의 움직임을 살펴보시면 아래 애니메이션과 같습니다.
[삽입 정렬의 움직임]
3. 퀵 정렬(Quick Sort) 빠름~빠름!
퀵 정렬은 말 그대로 엄청나게 빠른 정렬 기법입니다. 이 퀵 정렬은 분할 정복(Divide and Conquer)에 근거하며, 퀵 정렬은 다른 정렬과는 달리 기준값을 하나 택하고 순회를 돌면서 기준값보다 작은 데이터는 좌측에, 기준값보다 큰 데이터는 우측으로 분할하고 다시 퀵 정렬을 적용합니다. 한번 퀵 정렬이 어떤식으로 정렬이 되는지 한번 그림으로 살펴보도록 합시다.
위 그림에서의 과정을 글로 나타내면 아래와 같습니다.
1. 5를 기준값으로 선택하고 5보다 작은 값은 좌측에, 큰 값은 우측에 모두 배치한다.
2. 4를 기준값으로 선택하고 4보다 작은 값은 좌측에, 큰 값은 우측에 모두 배치한다.
3. 8을 기준값으로 선택하고 8보다 작은 값은 좌측에, 큰 값은 우측에 모두 배치한다.
간략히 정리하자면, 맨 처음에 기준값을 택하고 작은 값은 좌측에 큰 값은 우측에 배치함으로써 작은 값과 큰 값으로 분할하고 분할된 두 영역이 A, B라고 한다면 A 영역에서 분할할 수 없을때까지 기준값을 택하고 분할되며 B 영역도 마찬가지로 B 영역에서 분할할 수 없을때까지 기준값을 택하고 분할되는 과정을 반복합니다. 이러한 퀵 정렬의 평균 복잡도는 아래와 같습니다.
퀵 정렬의 평균 복잡도:
최악의 경우 퀵 정렬의 복잡도:
이 퀵 정렬을 코드로 나타내면 아래와 같습니다.
#include <stdio.h>
void PrintArray(int arrData[], int Length)
{
for (int i = 0; i < Length; i++)
printf("%d ", arrData[i]);
printf("\n");
}
int Partition(int numbers[], int left, int right)
{
int first = left;
// 정렬 대상의 첫 번째 요소가 바로 기준값을 의미한다.
int pivot = numbers[first];
int temp = 0;
++left;
// left가 right보다 크다면 루프를 빠져나오게 되어있다.
while (left <= right)
{
// 배열을 순회하여 기준값(pivot)보다 크거나 같은 데이터를 찾을때까지 탐색하며 left의 값을 증가시킨다.
while(numbers[left] <= pivot && left < right) ++left;
// 배열을 순회하여 기준값(pivot)보다 작은 데이터를 찾을때까지 탐색하며 right의 값을 증가시킨다.
while(numbers[right] > pivot && left <= right) --right;
// right가 left보다 클 경우에(만나지 못했을 경우에)
if (left < right)
{
// 두 값을 교환한다.
temp = numbers[left];
numbers[left] = numbers[right];
numbers[right] = temp;
}
else break;
}
temp = numbers[first];
numbers[first] = numbers[right];
numbers[right] = temp;
return right;
}
void QuickSort(int numbers[], int left, int right)
{
if (left < right)
{
int index = Partition(numbers, left, right);
QuickSort(numbers, left, index - 1);
QuickSort(numbers, index + 1, right);
}
}
int main()
{
int arrData[] = {5, 4, 1, 2, 8, 7, 9};
int Length = sizeof arrData / sizeof arrData[0];
PrintArray(arrData, Length);
QuickSort(arrData, 0, Length - 1);
PrintArray(arrData, Length);
return 0;
}
결과:
5 4 1 2 8 7 9
1 2 4 5 7 8 9
계속하려면 아무 키나 누르십시오 . . .
코드에서 QuickSort 함수를 먼저 보시게 되면, QuickSort 내에서 다시 QuickSort 함수를 호출하는 재귀 호출을 하고 있는게 보입니다. (이 때, left가 right보다 크거나 같으면 만났다는 의미로 더이상 호출 하지 않습니다.) QuickSort 내의 첫번째 QuickSort 호출은 좌측 데이터 정렬이며, 두번째 호출은 우측 데이터 정렬을 의미합니다.
그리고 Partition 함수가 호출되면 정렬 데이터의 첫번째 요소를 기준값으로 택하고, while문으로 인해 분할이 되는 것입니다. 분할을 끝마치면 right의 값을 반환하게 되는 것입니다. 퀵 정렬의 움직임은 아래 애니메이션을 통해 참고를 하시기 바랍니다.
[퀵 정렬의 움직임]
'알고리즘, 자료구조' 카테고리의 다른 글
| 자료구조 4강. 트리(Tree) (4) | 2013.01.23 |
|---|---|
| 자료구조 3강. 큐(Queue) (4) | 2013.01.15 |
| 자료구조 2강. 스택(Stack) (8) | 2013.01.09 |
| 자료구조 1강. 리스트(List) (20) | 2013.01.01 |
| 비주얼베이직6 움직임에 관한 수학공식 정리 (4) | 2012.10.03 |