정렬은 무엇인가? 데이터를 오름차순 혹은 내림차순 등으로 가지런히 나열하는 것이다. 정렬의 목적은 무엇인가? 우리가 찾고자 하는 데이터를 빠르고 쉽게 찾을 수 있게 하는 것이 목적이다. 정렬에는 여러 가지 종류가 있고 각각 장단점이 있다.
버블 정렬
버블 정렬(Bubble Sort)은 알고리즘이 데이터를 정렬하는 과정이 마치 물 속 깊은 곳에서 일어난 거품이 수면을 향해 올라오는 모습과 같다고 해서 붙여진 이름이다.(생각 참 특이하네) 버블 정렬은 데이터 집합을 순회하면서 이웃 요소끼리 비교하며 정렬을 수행한다. 다음과 같은 집합이 있다고 하자.
이를 버블 정렬을 통해 오름차순으로 정리해보자. 먼저 0,1 원소를 비교한다.
5가 1보다 크므로 5가 오른쪽으로 가게 교환한다. 그 다음에는 1,2 원소를 비교한다.
6이 5보다 크므로 교환하지 않는다. 그 다음에는....
계속 이런식으로 가다보면 이렇게 될 것이다.
오름차순인가? 아니다. 대신 이 집합에서 제일 큰 원소인 6이 제일 오른쪽으로 갔다. 그 다음부터는 다시 제0 원소부터 비교한다.
이렇게 또 계속한다. 어디까지? 굳이 마지막 6까지 할 필요가 없다. 어차피 현재는 맨 오른쪽이 제일 크기 때문이다. 맨 마지막 - 1까지 한다. 그럼 그 다음은 제3 원소부터 시작해서 맨 마지막 - 2까지 한다. 이렇게 반복한다.
버블 정렬은 얼마나 빠를까? 맨 처음에 원소가 n개 있다면, n - 1번의 비교를 한다. 그 다음은 원소 n - 1개에서 비교가 들어가므로 n - 2번을 한다. 그 다음은 n - 3번... 이런식으로 하면 (n - 1) + (n - 2) + (n - 3) + ... + 1 식으로 하게 되고, 이는 이다. 다른 정렬과 비교해보면 알겠지만 이는 빠른 편은 아니다. 그래도 코드를 작성해보자.
void BubbleSort(int dataSet[], int length)
{
for (int i = 0; i < length - 1; i++)
{
for (int j = 0; j < length - 1 - i; j++)
{
if (dataSet[j] > dataSet[j + 1])
{
int temp = dataSet[j];
dataSet[j] = dataSet[j + 1];
dataSet[j + 1] = temp;
}
}
}
}
int main()
{
int dataSet[] = { 6,4,2,3,1,5 };
int length = sizeof(dataSet) / sizeof(dataSet[0]);
BubbleSort(dataSet, length);
for (int i = 0; i < length; i++)
cout << dataSet[i] << " , ";
}실행 결과.
삽입 정렬
삽입 정렬(Insertion Sort)는 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내어 이를 다시 적당한 곳에 삽입해 나가는 알고리즘이다. 이것은 마치 카드를 섞을 때, 한 장씩 뽑아서 적절한 위치에 다시 끼워 넣으면 결국 모든 카드가 순서대로 되는거나 마찬가지다. 삽입 정렬은 버블 정렬과 비슷하다.
다음과 같은 배열이 있다고 하자. 처음에는 0,1 원소를 비교한다. 그러면 1이 5보다 작다. 그럼 1을 뺀다. 마치 카드 덱에서 하나를 빼는 것처럼.
5가 1보다 크니 5 왼쪽에다 넣는다. 그 다음에는 1,2 원소를 비교한다. 근데 6이 5보다 크니 바꾸지 않는다.
그 다음에는 2,3 원소를 비교한다. 4가 6보다 작으므로 4를 뽑는다.
왼쪽이랑 차차 비교해나가다 보니까 5 왼쪽에 넣는 게 좋겠다.
이런식으로 계속 해나간다.
삽입 정렬 코드
void InsertionSort(int dataSet[], int length)
{
for (int i = 1; i < length; i++)
{
if (dataSet[i - 1] <= dataSet[i])
continue;
int value = dataSet[i];
for (int j = 0; j < i; j++)
{
if (dataSet[j] > value)
{
memmove(&dataSet[j + 1], &dataSet[j], sizeof(dataSet[0]) * (i - j));
dataSet[j] = value;
break;
}
}
}
}버블 정렬은 데이터가 정렬돼있어도 모든 비교를 하는 반면, 삽입 정렬은 데이터가 정렬돼있으면 한번도 비교를 하지 않는다. 그런 점에서 삽입 정렬이더 낫다고 할 수 있다.
퀵 정렬
퀵 정렬이 모든 정렬 알고리즘 중에 제일 빠른 알고리즘이다. 퀵 정렬은 다음과 같은 과정으로 정렬을 수행한다. 그림으로 보자.
먼저 맨 처음 원소 인덱스를 기준 피봇(pivot)으로 잡고, 그 바로 오른쪽 인덱스를 left, 집합의 마지막 원소 인덱스를 right이라 한다.
left 인덱스는, pivot값 기준으로 left 인덱스 값이 더 클 때까지 오른쪽으로 간다. right 인덱스는, pivot값 기준으로 right 인덱스 값이 더 작을 때까지 왼쪽으로 간다.
이제 left와 right을 바꾼다. 만약 left와 right가 엇갈렸다면 right과 pivot을 바꾼다.
이 과정을 계속 한다. 언제까지? left와 right가 엇갈릴 때까지!
엇갈렸다. 이제 right과 pivot을 바꾼다.
pivot 기준으로 왼쪽, 오른쪽을 재귀로 다시 실행한다.
코드는 이렇다.
void QuickSort(int dataSet[], int start, int end)
{
int pivot = dataSet[start];
int left = start + 1;
int right = end;
while (left <= right)
{
while (dataSet[left] <= pivot && left < right)
left++;
while (dataSet[right] > pivot && left <= right)
right--;
if (left < right)
Swap(&dataSet[left], &dataSet[right]);
else
break;
}
if (start < end)
{
Swap(&dataSet[start], &dataSet[right]);
QuickSort(dataSet, start, right - 1);
QuickSort(dataSet, right + 1, end);
}
}퀵 소트는 이미 배열이 정렬돼있거나, 역순으로 정렬돼있는 경우는 최악의 성능을 보인다. 하지만 그 외에는 최고의 성능을 자랑한다. 이상적인 경우, 퀵 소트의 성능은 다음과 같다.
이상적인 경우의 퀵 정렬의 비교 횟수
= 재귀 호출의 깊이 * 각 재귀 호출 단계에서의 비교 횟수
=
반면 최악의 경우는 이다. 버블 정렬이나 삽입 정렬과 비슷해지는 것이다.
qsort() 함수
qsort() 함수는 stdlib.h 표준 라이브러리에 내장되어 있는 함수다. 원형은 다음과 같다.
void qsort(
void *base, // 데이터 집합 배열의 주소.
size_t num, // 데이터 요소의 개수.
size_t width, // 한 데이터 요소 크기.
int (__cdecl *compare)(const void *, const void *) // 비교 함수에 대한 포인터.제4 매개변수만 주의하면 된다. 이는 함수 포인터이다. 함수 포인터의 제1 매개변수와 제2 매개변수를 비교해서 리턴값을 다르게 하면 된다. 다음은 그 예시다.
int CompareScore(const void* _elem1, const void* _elem2)
{
int* elem1 = (int*)_elem1;
int* elem2 = (int*)_elem2;
if (*elem1 > *elem2)
return 1;
else if (*elem1 < *elem2)
return -1;
else
return 0;
}
int main()
{
int dataSet[] = { 5,1,6,4,2,3 };
int length = sizeof(dataSet) / sizeof(dataSet[0]);
qsort((void*)dataSet, length, sizeof(int), CompareScore);
for (int i = 0; i < length; i++)
cout << dataSet[i] << " , ";
}