정렬의 핵심은 교환, 선택, 삽입이다.
버블 정렬
안정적(같은 값의 순서가 안바뀐다.) 뒤로 한칸씩 가면서 인접한 두개의 수를 비교해 정렬한다. 경우의 수는 n-1 + n-2.../2(바꾸거나, 안바꾸거나 평균) = n(n-1)/4 이다. 게다가 요소를 교환하는 swap 함수에서 3번의 이동이 발생하므로, 횟수 평균은 3n(n-1)/4이다.
개선(1) count 사용
i= 0 ~ n-1, j= n-1 ~ i 와 같은 식으로 for문을 사용할 때, j for문에서 교환이 한번도 이루어지지 않았다면 더이상 정렬을 할 필요가 없는 것이다. 따라서 j앞에서 count를 0으로 초기화 해주고 j for문에서 교환이 이루어졌을 경우 count++을 한다. 만약 j for문이 끝났는데도 count가 0일경우 정렬을 멈춰버린다.
개선(2) last 사용
위와 같이 정렬하되, j for문의 맨 뒤로부터 교환이 이루어지지 않은 부분은 이미 정렬되어 있다. 이는 사실 위의 개선 (1)을 세부적으로 나눈 것이다.
즉, j for문에서 마지막으로 교환이 이루어진 부분을 last에 저장한 다음 i for문에서는 last index부터 정렬을 시작하면 된다.
단순 선택 정렬
배열에서 가장 작은 요소를 배열의 맨 앞과 교환한 다음, 첫번째를 제외한 뒤 계속 반복한다. 서로 떨어져있는 요소를 비교하는 것이기때문에 안정적이지 않다. 버블 정렬과는 다르게 swap함수를 쓰지 않으므로 비교 횟수는 n(n-1)/2이다. 위와 다르게 바꾸거나 안바꾸거나 2가지 경우가 있는 것이 아니므로 평균을 구할 수 없다.
단순 삽입 정렬(shuttle sort)
배열을 정렬되지 않은 배열과 정렬된 배열로 나눈다. 정렬되지 않은 배열의 맨 앞 요소를 하나씩 빼서 정렬된 배열의 적절한 자리에 배치한다.
적절한 자리를 찾는 방법은 뺀 요소와 같은 요소거나 작은 요소가 나올때까지 또는 인덱스가 0일때까지 정렬된 배열의 인덱스를 줄여주면 된다.
순차적으로 채우므로 안정적인 정렬이다. 이도 위 정렬들과 같이 시간 복잡도는 O(n^2)이다.
셸 정렬
단순 삽입 정렬의 장점(정렬을 마친 상태와 비슷하면 일부 요소만 삽입하면 되므로 빠르다.)을 살리고 단점(삽입해야하는 자리가 멀리있으면 오래걸리다.)을 보완한 정렬이다.
8개의 요소를 정렬한다고 하면 4개의 그룹(index 0-4, 1-5, 2-6, 3-7 이렇게 짝지은 그룹들이다.)으로 나눠 각각의 요소를 4-정렬 하고, 이를 다시 2개의 그룹(index 0-2-4-6, 1-3-5-7)으로 나눠 각각의 요소를 2-정렬한다. 그리고 마지막으로 1개의 그룹으로써 1-정렬을 한다.
이렇게 각각의 과정에서 수행하는 정렬을 h-정렬이라고 하며, 위의 케이스는 4,2,1 총 7회의 정렬을 한 것이다.
얼핏보면 복잡해보이지만 삽입 정렬의 단점인 요소 이동 횟수를 줄여서 효율적이다.
여기서 h는 서로 배수가 되지 않는 것이 좋다.
- 여태 알아본 정렬은 시간복잡도가 O(N^2)이다.
퀵 정렬
가장 빠른 정렬이다. 처음에 피봇을 정한다(기준). index 0 값을 pl, index n-1 값을 pr로 정한다. pl은 뒤로, pr은 앞으로 이동하면서 각각 피봇보다 큰것, 작은것을 찾으면 멈춘다. pl pr모두 멈췄으면 index pl 값과 index pr 값을 교환한다.
계속 반복하다가 pl 또는 pr이 피봇값에 도달하면 도달한 그룹은 이동을 멈춘다.
예를 들어 pl만 멈췄는데, pr이 더 작은 값을 찾았으면 index pivot = index pl 과 교환하는 것이다. 이는 pl>=pr 일 때까지 반복한다. 다음 코드에서 x는 피봇이다.
do {
while(a[pl] < x) pl++;
while(a[pr] > x) pr--;
if(pl <= pr) {
swap(int, a[pl], a[pr]);
pl++;
pr--;
}
}
} while(pl <= pr);일단 피봇을 기준으로 한번 정렬했다. 그럼 pr과 pl은 한칸차이로 pr, pl 순으로 있던가 같은 index에 있을 것이다.
그럼 0pr, pln-1 로 나눌 수 있는데, pr이 0 그리고 pl이 n-1과 같아질때까지(1개로 이루어진 그룹이 될 때까지) 재귀함수를 계속 돌리면 된다. 즉, void quick(int a[], int left, int right) 과 같은 함수라고 정의 했을때,
if(left < pr) quick(a, left, pr);
if(pl < right) quick(a, pl, right);를 추가해주면 되는 것이다.
재귀를 쓰지 않을 수도 있다. stack을 이용해 정렬할 범위를 계속 저장해뒀다가 stack이 0이 될때까지 정렬하는 것이다. 한번에 이해가 되지 않았으므로 코드 전체를 넣겠다.
void quick (int a[], int left, int right)
{
IntStack lstack;
IntStack rstack;
Initialize(&lstack, right - left + 1);
Initialize(&rstack, right - left + 1);
Push(&lstack, left);
Push(&rstack, right);
while(!IsEmpty(&lstack)) {
int pl = (Pop(&lstack, &left), left);
int pr = (Pop(&rstack, &right), right);
int x = a[(left + right) / 2];
do {
while(a[pl] < x) pl++;
while(a[pr] > x) pr--;
if(pl <= pr) {
swap(int, a[pl], a[pr]);
pl++;
pr--;
}
} while(pl <= pr);
if(left < pr) {
Push(&lstack, left);
Push(&rstack, pr);
}
if(pl < right) {
Push(&lstack, pl);
Push(&rstack, right);
}
}
Terminate(&lstack);
Terminate(&rstack);
}-
이 때, 적절한 스택의 개수는 전체 요소 n의 log n 보다 적다. 따라서 100만개의 요소라도 최대 용량 20이면 충분하다.
-
다음 코드에서 int a = (1,2); 과 같은 형식이 있다.
이는 int a = 1; a = 2; 와 같다. 따라서 int pl = Pop(&lstack, left); 에서는 &lstack에서 Pop한 값이 left에 저장되고, left의 값이 pl에 저장된 것이다.이 정렬에서 피봇을 정할 때, 무작정 중간 index의 값으로 정한다 하자. 만약 피봇이 최대값이거나 최소값이면? 효율정인 정렬이 되기 힘들다. 그렇다고 중간값을 일일이 찾을 수는 없다.
따라서 이에 따른 절충안이 있는데, 이는 다음과 같다.
-잘 이해가 안돼서 이해하고 정리
이 정렬의 시간복잡도는 최소 O(n log n)이며, 최대 O(n^2)이다. 표준 라이브러리에도 존재하는데 다음과 같다.
qsort 함수
형식 - void qsort(void base, size_t nmmemb, size_t size, int( compar)(const void, const void))
구조체에서 사용할때의 형식 예시 - qsort(x, nx, sizeof(STRUCT), (int()(copnst void, const void*)) cmp)
병합 정렬
유래는 정렬을 마친 배열의 병합이다. 예를 들어 배열 a,b를 합쳐 c를 만든다고 할때, 커서를 각 pa, pb, pc라고 하자.
pa=pb=pc=0 으로 초기화 한 뒤, index pa와 pb를 비교해 더 작은 값을 index pc값에 대입한다. pa와 pb중 대입한 값과 pc는 1씩 더해지고 이를 계속 반복한다. 코드는 다음과 같다.
while(pa < na && pb < nb)
c[pc++] = (a[pa] <= b[pb) ? a[pa++] : b[pb++];
while(pa < na)
c[pc++] = a[pa++];
while(pb < nb)
c[pc++] = b[pb++];두번째 세번째 while문은 대입하고 배열 a,b에 남은 요소들을 배열 c에 넣기 위함이다.
이제 병합 정렬을 알아보자. 병합 정렬은 이런 배열의 병합을 응용하여 분할 정복법에 따라 정렬하는 알고리즘이다.
단계는 다음과 같다.
1. 배열의 앞부분을 병합 정렬로 정렬한다.
2. 배열의 뒷부분을 병합 정렬로 정렬한다.
3. 배열의 앞부분과 뒷부분을 병합한다.
퀵 정렬과 같이 계속 반절로 나누는 것이다. 따라서 시간복잡도는 O(n log n)이다.
힙 정렬
힙이란 부모의 값이 자식의 값보다 항상 크다라는 조건을 만족하는 완전이진트리이다. 힙의 요소에서 부모와 자식의 index 관계는 다음과 같다. 힙의 index는 루트부터 지그재그로 매긴다.
1. 부모 = a[(i-1) / 2]
2. 왼쪽 자식 = a[i*2 + 1]
3. 오른쪽 자식 = a[i*2 + 2]
힙 정렬은 가장 큰 값이 루트에 있다는 점을 이요한 알고리즘이다. 풀어서 쓰면 힙에서 계속 루트를 꺼내 늘어놓은 것이다.
과정은 다음과 같다.
1. 루트를 꺼낸다.
2. 마지막요소를 루트로 이동한다.
3. 자기(루트)보다 큰 값을 가지는 자식 요소중 큰 값과 자리를 바꾸는 과정을 반복한다. 이때, 자식의 값이 작거나 잎에 다다르면 작업을 종료한다.
코드에 적용하면
1. 변수 i의 값을 n-1로 초기화한다.
2. a[0]과 a[i]를 바꾼다.
3. a[0], a[1], ... , a[i-1]을 힙으로 만든다.
4. i의 값을 1씩 줄여 0이되면 break, 아니면 2번으로 돌아간다.
처음에 힙을 만들어야한다. 이것 역시 작은 부분부터 힙으로 만들고, 힙 위에 달린 루트를 맞는 자리에 넣어 더 큰 힙을 만드는 과정을 반복하며 만든다.
순서는 보통 가장 맨 오른쪽 아래 부분 힙부터 시작해 왼쪽으로, 위쪽으로 간다.
힙 정렬의 시간복잡도는 O(n log n)이다.
코드는 다음과 같다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
void swap(int* x, int* y) {
int t = *x;
*x = *y;
*y = t;
}
//a[left]~a[right]를 힙으로 만드는 함수
static void downheap(int a[], int left, int right)
{
int temp = a[left];
int child;
int parent;
for (parent = left; parent < (right + 1) / 2; parent = child) {
int cl = parent * 2 + 1; //왼쪽 자식
int cr = cl + 1; //오른쪽 자식
child = (cr <= right && a[cr] > a[cl]) ? cr : cl;
if (temp >= a[child]) break;
a[parent] = a[child];
}
a[parent] = temp;
}
//힙 정렬 함수
void heapsort(int a[], int n)
{
int i;
for (i = (n - 1) / 2; i >= 0; i--) {
downheap(a, i, n - 1);
}
for (i = n - 1; i > 0; i--) {
swap(a, a + i);
downheap(a, 0, i - 1);
}
}
int main() {
int arr[8] = { 6, 7, 5, 4, 3, 8, 2, 1 };
heapsort(arr, 8);
for (int i = 0; i < 8; i++)
printf("%d ", arr[i]);
return 0;
}반복문에서 왜 (n-1) / 2 부터만 힙으로 바꿀까? 그건 나머지 원소 반절은 자식이 없어, 힙으로 만들어줄 필요가 없기 때문이다.
증명은 다음과 같다. 원소의 개수 w개를 이진트리 방식으로 표현하면 1+2+4...n+(2n-x) 이다. 여기서 자식이 없는 원소는 맨 끝 라인의 (2n-x) 과 두번째 라인의 x/2이다. 더해보면 2n-x/2인데, w = 4n-x이다. 따라서 자식이 없는 원소의 개수 = w/2 이다.
도수 정렬
도수 정렬은 대소 관계를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘이다.
도수 정렬 알고리즘은
1. 도수분포표 작성
2. 누적도수분포표 작성
3. 목적 배열 만들기
4. 배열 복사
이 4단계로 구성한다.
- 도수 분포표는 새로운 배열 f를 하나 정의하는데, 이는 정렬해야할 배열의 값 = f의 index 이다.
- f[i] = f[i] + f[i-1] 을 하면된다.
- 작업용 배열 b를 만들고 배열 a를 f와 대조하며 b를 채운다.
- 작업용 배열 b를 a에 복사한다.
코드는 다음과 같다. 특징은 if문 없이 for문으로만 구현할 수 있다는 것이다.
void fsort(int a[], int n, int max) {
int i;
int* f = calloc(max+1, sizeof(int));
int* b = calloc(n, sizeof(int));
for(i=0; i <= max; i++) f[i] = 0;
for(i=0; i < n; i++) f[a[i]]++;
for(i=1; i <= max; i++) f[i] += f[i-1];
for(i=n-1; i >= 0; i--) b[--f[a[i]]] = a[i];
for(i=0; i < n; i++) a[i] = b[i];
free(b);
free(f);
}- 전제 : 모든 요솟값이 0이상 max이하이다.
- 네번째 for문에서 n-1 서부터 배열b를 채우는 이유는 원래 있떤 순서 그대로 채우기 위함이다. 만약 0에서부터 채우면 동일값의 순서는 반대로 바뀐다.
