공부할 책 : 자료구조와 함께 배우는 알고리즘 입문 - C언어 편
정렬
이름,학번,키 등 핵심 항목의 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업을 말한다. 이 알고리즘을 이용해 데이터를 정렬하면 검색을 더 쉽게 할 수 있다. 만약 사전에 실린 수십만 개의 단어가 알파벳이나 가나다순으로 정렬되어 있지 않으면 원하는 단어를 찾기가 어려울 것이다.
정렬 알고리즘의 안정성
안정된 정렬이란 같은 값의 키를 가진 요소의 순서가 정렬 전후에도 유지되는 것을 말한다.
안정되지 않은 알고리즘은 같은 점수인 경우 반드시 순서대로 정렬되지 않는다.
내부 정렬과 외부 정렬
하나의 배열에서 작어업할 수 있는 경우에는 내부 정렬, 작업할 수 없는 경우 외부 정렬을 사용한다.
내부 정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘
외부 정렬 : 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘
외부 정렬은 내부 정렬을 응용한 것으로, 외부 정렬을 구현하려면 작업을 위한 파일 등이 필요하고 알고리즘도 복잡하다. 여기서 다루는 알고리즘은 모두 내부 정렬이다.
정렬 알고리즘의 핵심 요소
교환 선택 삽입
버블 정렬
이웃한 두 요소의 대소 관계를 비교하여 교환을 반복한다.
먼저 끝에 있는 두 요소부터 시작한다. 그런 다음 뒤쪽에서 2,3번째 요소를 비교한다. 이런 일련의 과정 (비교, 교환 작업)을 패스 라고 한다.
이어서 2번째 이후 요소에 대해 패스 작업을 수행한다.
#include <stdio.h>
int arr[] = { 6,4,3,7,1,9,8 };
void print() {
for (int i = 0;i < 7;i++) {
printf("%d ", arr[i]);
}
}
void arr_sort() {
for (int i = 0;i < sizeof(arr)/4-1;i++) {
for (int j = sizeof(arr)/4-1;j > i ;j--) {
if (arr[j] < arr[j - 1]) {
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
}
}
}
}
int main() {
arr_sort();
print();
}
알고리즘 개선 1.
어떤 패스에서 요소의 교환 횟수가 0이면 더 이상 정렬할 요소가 없다는 뜻이므로, 정렬 작업을 멈추면 된다.
int arr[] = { 6,4,3,7,1,9,8 };
void print() {
for (int i = 0;i < 7;i++) {
printf("%d ", arr[i]);
}
}
void arr_sort() {
for (int i = 0;i < sizeof(arr)/4-1;i++) {
int exflag = 0;
for (int j = sizeof(arr)/4-1;j > i ;j--) {
if (arr[j] < arr[j - 1]) {
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
exflag = 1;
}
}
if (exflag == 0) break;
}
}
int main() {
arr_sort();
print();
}알고리즘 개선 2.
비교, 교환을 하다가 어떤 시점 이후에 교환이 수행되지 않는다면 그보다 앞쪽의 요소는 이미 정렬을 마친 상태이다.
교환을 수행할 때마다 오른쪽 요소의 인덱스 값을 last에 저장한다. 하나의 패스를 마쳤을 때 last 값을 k에 대입하여 다음에 수행할 패스의 범위를 제한한다.
#include <stdio.h>
int arr[] = { 6,4,3,7,1,9,8 };
void print() {
for (int i = 0;i < 7;i++) {
printf("%d ", arr[i]);
}
}
void arr_sort() {
int k = 0;
while (k < 6) {
int j;
int last = 6;
for(j=6;j>k;j--)
if (arr[j - 1] > arr[j]) {
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
last = j;
}
k = last;
}
}
int main() {
arr_sort();
print();
}단순 선택 정렬
가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘.
아직 정렬하지 않은 부분에서 값이 가장 작은 요소를 선택하고 아직 정렬하지 않은 부분의 첫 번째 요소와 교환한다.
void selection(int a[], int n)
{
int i, j, min;
for (i = 0;i < n - 1;i++) {
min = i;
for(j = i+1;j < n;j++) {
if (a[min] > a[j]) {
min = j;
}
}
int temp = a[i];
a[i] = a[min];
a[min] = temp;
}
}
void print(int a[],int n) {
for (int i = 0;i < n;i++) {
printf("%d ", a[i]);
}
}
int main() {
int arr[] = { 10,7,3,5,2,1,8,9,6,4 };
selection(arr, 10);
print(arr,10); 그러나 이 정렬 알고리즘은 서로 떨어져 있는 요소를 교환하는 것이기 때문에 안정적이지 않다.
단순 삽입 정렬
선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 '삽입하는' 작업을 반복하여 정렬하는 알고리즘.
단순 선택 정렬과 비슷하게 보일 수 있지만 단순 선택 정렬은 값이 가장 작은 요소를 선택해 알맞은 위치로 옮긴다는 점이 다르다.
void insertion(int a[],int n) {
int i, j;
for (i = 1;i < n;i++) {
int tmp = a[i];
for (j = i;j > 0 && a[j - 1] > tmp;j--)
a[j] = a[j - 1];
a[j] = tmp;
}
}
int main() {
int arr[] = { 22, 5, 11, 32, 120, 68, 70 };
insertion(arr, 7);
for (int i = 0;i < 7;i++) {
printf("%d ", arr[i]);
}
}이 알고리즘은 단순선택 정렬과 달리 안정적이다.
지금까지 공부한 세 가지 단순 정렬(버블,선택,삽입)의 시간 복잡도는 모두 O(n²)이다(효율이 좋지 않다).
셸 정렬
단순 삽입 정렬의 특징은 다음과 같다.
장점 : 정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 매우 빨라진다.
단점 : 삽입할 위치가 멀리 떨어져 있으면 이동해야 하는 횟수가 많아진다.
단순 삽입 정렬의 장점은 살리고, 단점은 보완한 정렬 알고리즘이 셸 정렬 알고리즘이다.
퀵 정렬이 고안되기 전까지는 가장 빠른 알고리즘으로 알려져 있었다.
/* 셸 정렬 */
#include <stdio.h>
#include <stdlib.h>
/*--- 셸 정렬 함수 ---*/
void shell(int a[], int n)
{
int i, j, h;
for (h = n / 2; h > 0; h /= 2)
for (i = h; i < n; i++) {
int tmp = a[i];
for (j = i - h; j >= 0 && a[j] > tmp; j -= h)
a[j + h] = a[j];
a[j + h] = tmp;
}
}
int main(void)
{
int i, nx;
int *x; /* 배열의 첫 번째 요소에 대한 포인터 */
puts("셸 정렬");
printf("요소 개수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
for (i = 0; i < nx; i++) {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
shell(x, nx); /* 배열 x를 셸 정렬 */
puts("오름차순으로 정렬했습니다.");
for (i = 0; i < nx; i++)
printf("x[%d] = %d\n", i, x[i]);
free(x); /* 배열을 해제 */
return 0;
}퀵 정렬
가장 빠른 정렬 알고리즘 중의 하나로 널리 사용되고 있다.
학생 수가 8명인 그룹이 있으면, 먼저 어느 한 사람의 키를 선택한다. 학생 A를 선택한 경우 그 학생을 기준으로 학생 A의 키보다 작은 사람의 그룹과 큰 사람의 그룹으로 나눈다. 이때 학생 A를 피벗이라고 한다. 퀵 정렬은 각 그룹에 대해 피벗 설정과 그룹 나눔을 반복하여 모든 그룹이 1명이 되면 정렬을 마친다.
배열을 두 그룹으로 나누기
먼저 배열을 두 그룹으로 나누는 순서이다.
피벗은 x, 왼쪽 끝 요소의 인덱스 pl은 왼쪽 커서, 오른쪽 끝 요소의 인덱스 pr는 오른쪽 커서
- a[pl] >= x 가 성립하는 요소를 찾을 때까지 pl을 오른쪽으로 옮긴다.
- a[pr] <= x 가 성립하는 요소를 찾을 때까지 pr을 왼쪽으로 옮긴다.
이 과정을 거치면 pl은 a[1] , pr은 a[6] 에 위치하게 된다. 여기서 a[pl]과 a[pr] 을 교환한다.
이 과정을 반복한다.
pl과 pr이 교차하면 그룹을 나누는 과정이 끝나고 배열은 피벗 이하의 그룹과 피벗 이상의 그룹으로 나누어진다.
배열을 나누는 코드 :
#include <stdio.h>
#include <stdlib.h>
#define swap(type, x, y) do { type t = x; x = y; y = t;} while (0)
/*--- 배열을 나누는 함수 ---*/
void partition(int a[], int n)
{
int i;
int pl = 0;
int pr = n - 1;
int x = a[n / 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);
printf("피벗의 값 : %d\n", x);
printf("피벗 이하의 그룹 : ");
for (i = 0;i < pl - 1;i++) printf("%d ", a[i]);
printf("\n피벗 이상의 그룹 : ");
for (i = pr + 1;i < n;i++) printf("%d ", a[i]);
}
int main(void)
{
int i, nx;
int *x; /* 배열의 첫 번째 요소에 대한 포인터 */
puts("배열을 나눕니다.");
printf("요소 개수 : ");
scanf_s("%d", &nx);
x = calloc(nx, sizeof(int)); /* 요소의 개수가 nx인 int형 배열을 생성 */
for (i = 0; i < nx; i++) {
printf("x[%d] : ", i);
scanf_s("%d", &x[i]);
}
partition(x, nx); /* 배열 x를 분할 */
free(x); /* 배열을 해제 */
return 0;
}이 방법을 좀 더 발전시키면 퀵 정렬 알고리즘이 된다.
퀵 정렬 알고리즘
#include <stdio.h>
#include <stdlib.h>
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
void quick(int a[], int left, int right) {
int pl = left;
int pr = right;
int x = a[(pl + pr) / 2];
do {
while (a[pl] < x) pl++;
while (a[pr] > x) pr--;
if (pl <= pr) {
swap(&a[pl], &a[pr]);
pl++;
pr--;
}
}while (pl <= pr);
if (left < pr) quick(a, left, pr);
if (pl < right) quick(a, pl, right);
}
int main() {
int i, nx;
int* x;
printf("요소 개수 : ");
scanf_s("%d", &nx);
x = (int*)calloc(nx, sizeof(int));
for (i = 0;i < nx;i++) {
printf("x[%d] : ", i);
scanf_s("%d" ,&x[i]);
}
quick(x, 0, nx - 1);
printf("오름차순 정렬결과 : \n");
for (i = 0;i < nx;i++) {
printf("x[%d] = %d\n", i, x[i]);
}
}퀵 정렬의 시간 복잡도는 O(n log n)이다.
qsort 함수
bsearch 함수와 마찬가지로 표준 라이브러리에서 제공하는 함수이다.
int int_cmp(const int* a, const int* b) {
if (*a < *b) return -1;
else if (*a > *b) return 1;
else return 0;
}
int main() {
int i, nx;
int* x;
printf("요소 개수 : ");
scanf_s("%d", &nx);
x = (int*)calloc(nx, sizeof(int));
for (i = 0;i < nx;i++) {
printf("x[%d] : ", i);
scanf_s("%d" ,&x[i]);
}
qsort(x, nx, sizeof(int),
(int(*)(const void*, const void*)) int_cmp);
printf("오름차순 정렬결과 : \n");
for (i = 0;i < nx;i++) {
printf("x[%d] = %d\n", i, x[i]);
}
}병합 정렬
병합 정렬 알고리즘
static void __mergesort(int a[], int left, int right) {
if (left < right) {
int center = (left + right) / 2;
int p = 0;
int i;
int j = 0;
int k = left;
__mergesort(a, left, center);
__mergesort(a, center + 1, right);
for (i = left;i <= center;i++) buff[p++] = a[i];
while (i <= right && j < p) a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];
while (j < p) a[k++] = buff[j++];
}
}
int mergesort(int a[], int n) {
if ((buff = (int*)calloc(n, sizeof(int))) == NULL) return -1;
__mergesort(a, 0, n - 1);
return 0;
}
int main() {
int i, nx;
int* x;
printf("요소개수 : ");
scanf_s("%d", &nx);
x = (int*)calloc(nx,sizeof(int));
for (i = 0;i < nx;i++) {
printf("x[%d] : ", i);
scanf_s("%d", &x[i]);
}
mergesort(x, nx);
for (i = 0;i < nx;i++) {
printf("%d ",x[i]);
}
}병합 정렬의 시간 복잡도는 O(n log n) 이다. 병합 정렬은 서로 떨어져 있는 요소를 교환하는 것이 아니므로 안정적인 정렬 방법이라 할 수 있다.
힙 정렬
힙이란?
힙은 '부모의 값이 자식의 값보다 항상 크다'는 조건을 만족하는 완전이진트리이다.
이때 부모의 값이 자식보다 항상 작아도 힙이라고 한다.
완전이진트리
트리의 가장 윗부분을 루트라고 한다. 그리고 요소의 상하 관계를 부모와 자식이라고 한다.
그리고 자식간의 관계는 형제라고 한다.
완전이진트리의 특징은 '완전이진' 상태라는 것이다. 여기서 '완전' 이라는 말은 부모는 자식을 왼쪽부터 추가하는 모양을 유지하라는 뜻이다. 그리고 이진이라는 말은 '부모가 가질 수 있는 자식의 개수는 최대 2개다' 라는 의미이다.
아래는 힙이 아닌 완전이진트리이다.
힙
힙에서 부모와 자식 관계는 일정하지만 형제 사이의 대소 관계는 일정하지 않다.
예를 들어 아래 그림에서 형제 7과 8의 작은 쪽 7은 왼쪽에 있지만 6과 5의 작은 쪽 5는 오른쪽에 있다.
힙 요소와 배열 요소의 대응
힙의 요소를 배열에 저장하면 다음 사진과 같다.
힙 정렬
힙 정렬은 '가장 큰 값이 루트에 위치'하는 특징을 이용하는 정렬 알고리즘이다.
힙에서 가장 큰 값인 루트를 꺼내는 작업을 반복하고 그 값을 늘어놓으면 배열은 정렬을 마치게 된다. 즉 힙 정렬은 선택 정렬을 응용한 알고리즘이며 힙에서 가장 큰 값인 루트를 꺼내고 남은 요소에서 다시 가장 큰 값을 구해야 한다. 다시 말해 힙으로 구성된 10개의 요소에서 가장 큰 값을 없애면 나머지 9개의 요소에서 가장 큰 값을 루트로 정해야 한다. 따라서 나머지 9개의 요소로 만든 트리도 힙의 형태를 유지할 수 있도록 재구성 해야 한다.
루트를 없애고 힙 상태 유지하기
큰 값을 가지는 자식과 위치를 변경
이렇게 만든 트리는 힙 상태를 유지하게 된다. 하지만 요소를 항상 끝까지 옮겨야 하는 것은 아니다. 옮길 요소보다 왼쪽이나 오른쪽의 두 자식이 작으면 바꿀 수 없다.
루트를 없앤 다음 힙을 다시 만드는 순서를 순서는 다음과 같다.
1. 루트를 꺼낸다.
2. 마지막 요소를 루트로 이동한다.
3. 자기보다 큰 값을 가지는 자식 요소와 자리를 바꾸며 아래쪽으로 내려가는 작업을 반복한다. 이때 자식의 값이 작거나 잎에 다다르면 작업이 종료된다.
힙 정렬 알고리즘
이 힙을 사용하여 힙 정렬 알고리즘으로 확장하면 된다.
1. 힙의 루트(a[0]) 에 있는 가장 큰 값(10)을 꺼내 배열 마지막 요소(a[9])와 바꾼다.
2. 가장 큰 값을 a[9]로 옮기면 a[9]는 정렬을 마치게 된다. 앞에서 살펴본 순서대로 a[0] ~ a[8]의 요소를 힙으로 만든다. 그 결과 두 번째로 큰 요소인 9가 루트에 위치하게 된다. 힙의 루트 a[0]에 있는 가장 큰 값인 9를 꺼내 아직 정렬하지 않은 부분의 마지막 요소인 a[8]과 바꾼다.
3. 두 번째로 큰 값을 a[8]로 옮기면 a[8] ~ a[9]는 정렬을 마치게 된다. 그런 다음 a[0] ~ a[7]의 요소를 힙으로 만든다. 그 결과 세 번째로 큰 요소인 8이 루트에 위치하게 된다. 힙의 루트 a[0]에 있는 가장 큰 값인 8을 꺼내 아직 정렬하지 않은 부분의 마지막 요소인 a[7]과 바꾼다.
/* 힙 정렬 프로그램 */
#include <stdio.h>
#include <stdlib.h>
#define swap(type, x, y) do { type t = x; x = y; y = t; } while (0)
/*--- 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(int, a[0], a[i]);
downheap(a, 0, i - 1);
}
}
int main(void)
{
int i, nx;
int *x; /* 배열의 첫 번째 요소에 대한 포인터 */
puts("힙 정렬");
printf("요소 개수 : ");
scanf("%d", &nx);
x = calloc(nx, sizeof(int));
for (i = 0; i < nx; i++) {
printf("x[%d] : ", i);
scanf("%d", &x[i]);
}
heapsort(x, nx); /* 배열 x를 힙 정렬 */
puts("오름차순으로 정렬했습니다.");
for (i = 0; i < nx; i++)
printf("x[%d] = %d\n", i, x[i]);
free(x); /* 배열을 해제 */
return 0;
}단순 선택 정렬의 시간 복잡도는 O(n²) 이지만
단순 선택 정렬을 응용한 힙 정렬은 O(n log n) 이다.
도수 정렬
요소의 대소 관계를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘
지금까지 정렬 알고리즘은 두 요소의 키 값을 비교하는 정렬이다. 하지만 도수 정렬은 요소를 비교할 필요가 없다는 특징이 있다.
도수 정렬 알고리즘은 도수분포표 작성, 누적도수분포표 작성, 목적 배열 만들기, 배열 복사의 4단계로 이루어진다.
도수 정렬은 if문 대신 for문만을 사용해 정렬할 수 있는 매우 아름다운 알고리즘이다.
데이터의 비교, 교환 작업이 필요 없어 매우 빠르다. 단일 for문만 용해 재귀 호출, 이중for문이 없어 아주 효율적인 알고리즘이다. 하지만 도수분포표가 필요하기 때문에 데이터의 최솟값과 최댓값을 미리 알고 있는 경우에 사용할 수 있다.
이 정렬 알고리즘은 안정적이라고 할 수 있다.
그러나 3단계에서 배열 a를 스캔할 때 마지막 위치부터가 아닌 처음 위치부터 스캔을 하면 안정적이지 않다.
1. 도수분포표 만들기
먼저 배열 a를 바탕으로 '각 점수에 해당하는 학생이 몇 명인지를 나타내는 도수분포표' 를 작성한다. 도수분포표를 나타내기 위해 배열 f를 사용한다. 먼저 배열 f의 모든 요소의 값을 0으로 초기화한다. 그런 다음 배열 a를 처음부터 스캔하면서 도수분포표를 만들면 된다.
a[0]이 5 이면 f[5]를 1 증가
a[1]이 7 이면 f[7]를 1 증가
a[2]가 0 이면 f[0]를 1 증가..
2. 누적도수분포표 만들기
0부터 n까지 몇 명의 학생이 있는지 누적된 값을 나타내는 누적도수분포표를 만든다.
f[1]+=f[0],
f[2]+=f[1],
f[3]+=f[2] ...
3. 목적 배열 만들기
배열의 각 요솟값과 누적도수분포표 f를 대조하여 정렬을 마친 배열을 만드는 작업이다.
이 작업은 배열 a와 같은 요소의 개수를 갖는 작업용 배열 b가 필요하다. 그러면 배열 a의 요소를 마지막 위치부터 처음 위치까지 스캔하면서 배열 f와 대조하는 작업을 수행해 보자.
마지막 요소 (a[8]) 이 3이면, 배열 (f[3])의 값이 5 이므로 0~3점 사이에 5명이 있음을 알 수 있다. 목적 배열인 b[4]에 3을 저장한다. 이 작업을 할 때 f[3]의 값을 6에서 1만큼 감소시켜 4로 만든다. (나중에 배열 a에서 중복되는 값(3) 이 스캔되면 b[3]에 저장시키기 위해서)
4. 배열 복사하기
정렬은 끝났지만 정렬 결과를 저장한 곳은 작업 배열 (b)이다.
배열 b를 배열 a로 복사한다.
도수 정렬 알고리즘
