[C로 쓴 자료구조] 정렬 (Sorting)

전 세계 컴퓨터의 70%는 정렬을 하는데 시간을 보내고 있다 할 정도로 중요하고, 값 비싼 연산인 정렬을 파헤쳐보자.

 

전 세계 컴퓨터 공학자들의 Bible로 불리는 C로 쓴 자료구조의 높은 퀄리티의 코드를 하나하나 씹어 먹어보자!

 

(Y 대학 Prof. Cho의 강의력과 학생들을 향한 헌신에 감사하며 작성하는 글입니다.)

 

 

---

 

Insertion Sort (삽입 정렬)

 

 

Time Complexity	최선	평균	최악	Space Complexity	Stable
Insertion	n	n^2	n^2	1	Yes

 

대부분의 데이터가 sorting 되어 있을 경우 효과적이다.

 

데이터가 역순으로 sorting 되었을 때 최악의 성능

 

데이터 수가 n개일 때 성능

	최선	최악
비교	n	n^2 / 2
교환	0	n^2 / 2

 

 

삽입 정렬의 변형

 

Binary Insertion Sort

이미 비교해야하는 데이터의 앞부분이 정렬되어 있기 때문에 이진 검색으로 비교를 O(n)으로 줄일 수 있지만 값을 삽입하기 위해 한 칸씩 미는 교환 연산은 줄일 수 없다.

 

List Insertion Sort

데이터의 위치를 변경하는 연산은 줄일 수 있지만 이진 검색으로 데이터를 비교하는 연산은 줄일 수 없다.

 

 

 

 

코드

 

#include <stdio.h>

void insertion_sort(int list[], int n) {

	int i, j;
	int next;
	for (i = 1; i < n; i++) {
		next = list[i];
		for (j = i - 1; j >= 0 && next < list[j]; j--)
			list[j + 1] = list[j];
		list[j + 1] = next;
	}
}

 

 

---

 

Quick Sort (퀵 정렬)

 

각 단계 마다 기준값(pivot) 보다 작은 부분과 큰 부분으로 데이터를 분할해 나가면서 정렬

현재 정렬 알고리즘 중에 평균 퍼포먼스가 가장 좋다.

 

Time Complexity	최선	평균	최악	Time Complexity	Stable
Quick	n log n	n log n	n^2	log n, or n	No

 

이미 오름차순으로 정렬되어 있는 배열에서 최악의 성능

 

 

로직

 

1. 배열의 가장 왼쪽 데이터 list [left]를 pivot으로 설정

2. left를 i, right+1을 j 로 설정

3. i를 증가시키면서 값이 pivot 보다 작으면 stop

4. j를 감소시키면서 값이 pivot 보다 크면 stop

5. 3,4가 충족되면 i와 j 값 swap

6. 3,4,5를 반복 후 i와 j가 cross 되면 list [left]와 list [j] 값 swap 

 

 

 

 

 

 

코드

 

#include <stdio.h>
#define SWAP(x,y,t) ((t)=(x),(x)=(y),(y)=(t))

void quicksort(int list[], int left, int right) {

	int pivot, i, j;
	int temp;
	
	if (left < right) {
		i = left;
		j = right + 1;
		pivot = list[left];

		do {
			do {
				i++;
			} while (list[i] < pivot);
			
			do {
				j--;
			} while (list[j] > pivot);

			if (i < j)
				SWAP(list[i], list[j], temp);
		
		} while (i < j);
		SWAP(list[left], list[j], temp);
		quicksort(list, left, j - 1);
		quicksort(list, j + 1, right);
	}
}

 

 

---

 

Merge Sort (병합 정렬)

 

크기가 n인 리스트를 합병하여 2n 크기 리스트를 생성해 나가며 정렬

 

Java에서 object 배열은 stable 해야 하기 때문에 Merge Sort를 사용함

 

Time Complexity	최선	평균	최악	Space Complexity	Stable
Merge	n long n	n log n	n^2	n	Yes

 

 

 

로직

 

1. 전체의 큰 리스트를 1개씩 쪼개어 두개씩 짝지어 각각 순서대로 정렬

2. 병합한 리스트를 다시 인접한 리스트와 병합 (즉 크기가 n인 리스트를 합병하여 2n 크기 리스트 생성)

3. 위 과정을 반복적을 거쳐 최종적으로 전체 리스트를 병합

 

 

첫 번째 리스트의 index i와 두 번째 리스트 index j가 동시에 출발하여 i와 j 값중 작은 값을 sorted에 저장

 

 

 

merge_pass 함수에서 사용되는 인덱스 범위

 

 

 

 

코드

 

void merge(int list[], int sorted[], int i, int m, int n) { //정렬 된 리스트를 병합

	int j = m + 1; //i: 첫 번째 리스트 index, j: 두 번째 리스트 index
	int k = i;	 //k: sorted[] index

	while (i <= m && j <= n) {
		if (list[i] <= list[j])
			sorted[k++] = sorted[i++];
		else
			sorted[k++] = list[j++];
	}

	if (i > m) //두 번째 리스트의 나머지를 sorted[]에 복사
		for (; j <= n; j++)
			sorted[k++] = list[j];
	else
		for (; i <= m; i++) //첫 번째 리스트의 나머지를 sorted[]에 복사
			sorted[k++] = list[i];
}

void merge_pass(int list[], int sorted[], int n, int length) {
	/* list[n] 배열에서 길이가 length인 인접한 한 쌍의 서브리스트를 병합하여 sorted[] 배열에 저장*/

	int i, j;
	for (i = 0; i + 2 * length - 1 < n; i += 2 * length)
		merge(list, sorted, i, i + length - 1, i + 2 * length - 1);

	//길이가 2*length 보다 적게 남아있는 서브 리스트들을 병합
	if (i + length < n)
		merge(list, sorted, i, i + length - 1, n - 1);
	else //하나의 서브리스트만 남아있는 경우
		for (j = i; j < n; j++)
			sorted[j] = list[j];
}


void merge_sort(int list[], int n) {

	int length = 1;
	int extra[11];

	while (length < n) {
		merge_pass(list, extra, n, length);
		length *= 2;
		merge_pass(extra, list, n, length);
		length *= 2;
	}
}