굳건하게

안녕하세요, 여행벌입니다.

오늘은 합병정렬(Merge sort)에 대해서 포스팅해보겠습니다.

합병 정렬의 원리

 합병 정렬은 존 폰 노이만이 개발한 정렬 알고리즘입니다.

 합병 정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법으로 분할 정복에 바탕을 두고 있습니다. 즉, 주어진 리스트를 크기가 1이 될 때까지 분할한 후 각각의 부분 리스트들을 정렬하면서 합병해나가 최종적으로 정렬된 리스트를 얻는 방법입니다.

 합병 정렬에서 실제로 정렬이 이루어지는 시점은 2개의 리스트를 합병하는 단계입니다. 이때, 새로운 리스트를 추가로 필요로 합니다. 합병 알고리즘은 2개의 리스트의 요소들을 처음부터 하나씩 비교하여 두 개의 리스트의 요소 중에서 더 작은 요소를 새로운 리스트로 옮깁니다. 둘 중에서 하나가 끝날 때까지 이 과정을 되풀이하고 만약 둘 중에서 하나의 리스트 순회가 먼저 끝나게 되면 나머지 리스트의 요소들을 전부 새로운 리스트로 복사해 정렬된 합병 리스트를 얻습니다.

 합병 정렬은 분할 → 정렬 → 합병 의 과정을 반복하며 배열을 정렬해나가는 알고리즘입니다.

합병 정렬 예시

[ 5 3 8 4 1 6 2 7 ] 리스트를 합병 정렬을 통해 정렬해보겠습니다.

 먼저, 주어진 리스트를 크기를 동일하게 균등 분열하는 과정을 반복해 크기가 1인 부분 배열들을 얻어냅니다.

 그 후, 이 부분 배열들을 정렬하며 합병해 최종적으로 정렬된 배열을 얻습니다.

 (2) 배열 A와 배열 B를 정렬하며 합병하면 [ 3 5 ] 로 이루어진 배열 AB를 얻을 수 있고, 같은 방법으로 배열 CD, EF, GH 를 얻을 수 있습니다.

 (3) 배열 AB와 배열 CD를 정렬하며 합병하면 [ 3 4 5 8 ] 로 이루어진 배열 ABCD를 얻을 수 있고, 같은 방법으로 배열 EFGH를 얻을 수 있습니다.

 (4) 마지막으로 배열 ABCD와 배열 EFGH를 정렬하며 합병하면 정렬된 전체 배열을 얻을 수 있습니다.

 2개의 부분 배열이 어떻게 정렬되고 합병되는지 자세히 다뤄보도록 하겠습니다.

 배열 A [ 3 4 5 8 ] 과 배열 B [ 1 2 6 7 ] 을 합병 정렬 알고리즘을 이용해 합병해보겠습니다.

 합병 정렬은 새로운 리스트가 필요하므로 새로운 리스트를 배열 C라고 하겠습니다. 배열 A와 배열 B의 요소들을 순회하며 더 작은 값인 '1' 을 배열 C에 저장합니다.

  배열 A와 배열 B의 요소들을 순회하며 더 작은 값인 '2' 를 배열 C에 저장합니다.

 배열 A와 배열 B의 요소들을 순회하며 더 작은 값인 '3' 을 배열 C에 저장합니다.

 같은 과정을 반복하면 다음과 같이 정렬된 합병 배열 C를 얻을 수 있습니다.

합병 정렬 코드

int sorted[MAX_SIZE]; // 새로운 배열 C

void merge(int list[], int left, int mid, int right) {
	int i, j, k, l;
	i = left; j = mid + 1; k = left;

	while (i <= mid && j <= right) {
		if (list[i] <= list[j])
			sorted[k++] = list[i++];
		else
			sorted[k++] = list[j++];
	}
	if (i > mid)
		for (l = j; l <= right; l++)
			sorted[k++] = list[l];
	else
		for (l = i; l <= mid; l++)
			sorted[k++] = list[l];
	// 새로운 배열 C를 다시 원래 배열로 옮긴다.
	for (l = left; l <= right; l++)
		list[l] = sorted[l];
	return;
}

void merge_sort(int list[], int left, int right) {
	int mid = (left + right) / 2;
	if (left < right) {
		merge_sort(list, left, mid);
		merge_sort(list, mid + 1, right);
		merge(list, left, mid, right);
	}
	return;
}

merge_sort로 배열을 계속 반으로 분할해주고 분할이 완료되면 merge 함수를 호출해 정렬과 합병을 진행합니다.

합병 정렬의 복잡도 분석

 합병 정렬은 퀵 정렬과 마찬가지로 레코드의 개수가 n 이라고 한다면 절반씩 나눠지며 분할하므로 log(n) 번의 분할 연산이 진행됩니다. 그 후 merge 함수에서 비교 연산과 이동 연산이 수행되는데 비교 연산은 최대 n 번 발생하고, 이동 연산은 2n번 발생하는 것을 알 수 있습니다. 즉, O( nlogn ) 시간 복잡도를 가지게 됩니다.

 단점으로는 임시 배열이 필요하므로 추가적인 메모리가 요구됩니다. 또,  이동 횟수가 많으므로 레코드들의 크기가 큰 경우에는 매우 큰 시간 장비를 초래하게 됩니다. 하지만 연결리스트를 활용해 구현한다면 레코드의 크기가 큰 경우도 문제가 되지 않는다. 퀵 정렬과 다르게 항상 균등하게 분할되므로 최악의 경우에 퀵 정렬보다 더 잘 작동합니다.

합병 정렬의 안정성

 합병 정렬은 같은 값이 있는 경우에도 같은 값들의 정렬 순서가 변하지 않는 안정 정렬에 해당합니다.

이상으로 합병 정렬 포스팅을 마치겠습니다.

안녕하세요, 여행벌입니다.

오늘은 퀵정렬(Quick sort)에 대해서 포스팅해보겠습니다.

퀵 정렬의 원리

 퀵 정렬은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘입니다.

 퀵 정렬은 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방식으로 전체 리스트를 2개의 부분 리스트로 분할하고, 각각의 부분 리스트를 다시 퀵 정렬하는 분할 정복 방법을 사용합니다.

 먼저 리스트 안에 있는 한 요소를 피벗(Pivot)으로 선택합니다. 우리는 리스트의 첫 번째 요소를 피벗으로 선택하고 퀵 정렬을 진행하겠습니다. 물론, 다른 요소를 피벗으로 선택해도 무관합니다. 그 후, 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮기고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮깁니다. 결과적으로 피벗을 중심으로 왼쪽은 피벗보다 작은 요소들로 구성된 부분 리스트, 오른쪽은 피벗보다 큰 요소들로 구성된 부분 리스트가 생깁니다. 그 후 각각 부분 리스트에 대해서 같은 과정을 반복합니다.

퀵 정렬 예시

( 5 3 8 4 9 1 6 2 7 ) 리스트를 퀵 정렬을 이용해 정렬해보겠습니다.

 처음에는 전체 리스트에 대해서 퀵 정렬을 진행합니다.

 첫 번째 요소를 피벗으로 선택하므로 피벗은 5가 되고 left 는 전체 리스트의 가장 왼쪽, right 는 전체 리스트의 가장 오른쪽을 지칭합니다.

 low 는 피벗을 제외한 리스트의 왼쪽부터 피벗보다 큰 값을 찾아나가고, high 는 리스트의 오른쪽부터 피벗보다 작은 값을 찾아나갑니다.

(2) low 는 피벗 5보다 큰 8에서 멈추고 high 는 피벗 5보다 작은 2에서 멈춥니다. 그 후 둘을 SWAP 합니다.

(3) low 는 피벗 5보다 큰 9에서 멈추고 high 는 피벗 5보다 작은 1에서 멈춥니다. 그 후 둘을 SWAP 합니다.

(4) low 는 피벗 5보다 큰 9에서 멈추고 high 는 피벗 5보다 작은 1에서 멈춥니다. 하지만, low 와 high 가 뒤바뀐 것을 확인할 수 있습니다. 따라서, 더 이상 퀵 정렬을 진행하지 않고 high 와 pivot 을 SWAP 합니다.

(5) 피벗을 기준으로 왼쪽 리스트에는 피벗보다 작은 값, 오른쪽 리스트에는 피벗보다 큰 값들이 모여있는 것을 확인할 수 있습니다.

이제 두 개의 부분 리스트 [ 1 3 2 4 ] 와 [ 9 6 8 7 ] 에 대해서 각각 퀵 정렬을 진행합니다.

왼쪽 리스트의 피벗은 1로 오른쪽 리스트의 피벗은 9로 지정합니다.

같은 작업을 진행해 최종적으로 [ 1 3 2 4 ] 리스트는 [ 1 ] / [ 3 2 4 ] 2개의 부분 리스트로 나눠지고,

[ 9 6 8 7 ] 리스트는 [ 7 6 8 ] / [ 9 ] 2개의 부분 리스트로 나눠집니다.

크기가 1인 리스트는 이미 정렬이 되어있으므로 [ 3 2 4 ] / [ 7 6 8 ] 리스트에 대해서 퀵 정렬을 진행합니다.

왼쪽 리스트의 피벗은 3으로 오른쪽 리스트의 피벗은 7로 지정합니다.

같은 작업을 진행해 최종적으로 [ 2 ] / [ 3 ] / [ 4 ] 와 [ 6 ] / [ 7 ] / [ 8 ]  6개의 부분 리스트로 나눠집니다.

모든 리스트의 크기가 1이므로 정렬이 완료됩니다.

퀵 정렬은 전형적인 분할 정복 기법을 활용한 정렬 방식입니다.

요약하면 퀵 정렬은 아래 그림과 같이 움직인다고 볼 수 있습니다.

퀵 정렬 코드

int partition(int list[], int left, int right) {
	int pivot, temp, low, high;
	low = left;
	high = right + 1;
	pivot = list[left];
	do {
		do {
			low++;
		} while (low <= right && list[low] < pivot);
		do {
			high--;
		} while (high >= left && list[high] > pivot);
		if (low < high) { //SWAP진행.
			temp = list[low];
			list[low] = list[high];
			list[high] = temp;
		}
	} while (low < high);

	temp = list[left];
	list[left] = list[high];
	list[high] = temp;
	return high;
}

void quick_sort(int list[], int left, int right) {
	if (left < right) {
		int q = partition(list, left, right);
		quick_sort(list, left, q - 1);
		quick_sort(list, q + 1, right);
	}
}

퀵 정렬 복잡도

퀵 정렬의 복잡도는 리스트 상태에 따라 크게 바뀝니다.

만약 퀵 정렬에서의 리스트 분할이 항상 그림과 같이 리스트의 가운데에서 이루어진다고 가정하면 n 개의 레코드를 가지는 리스트가 n / 2, n / 4 와 같이 반으로 계속 분할될 것이고, 따라서 log(n) 번 분할이 발생합니다. 또 각 분할마다 평균 n번 정도의 비교가 이루어지므로 퀵 정렬의 복잡도는 nlog(n) 이 됩니다.

 하지만 리스트가 계속 불균형하게 나누어지는 경우에는 최대 n 번의 분할이 발생하고, 각 분할마다 평균 n번 정도의 비교가 이루어지므로 퀵 정렬의 복잡도는 n^2 가 됩니다.

 그럼에도 불구하고 퀵 정렬은 평균적인 경우의 시간 복잡도가 O( nlogn ) 으로 나타나고 같은 O( nlogn ) 복잡도를 가지는 정렬 중에서도 가장 빠릅니다.

퀵 정렬 안정성

퀵 정렬은 같은 값이 있는 경우 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있는 불안정 정렬에 속합니다.

 [ 5-1 5-2 3 2 1 ] 를 퀵 정렬로 정렬해보겠습니다.

[ 5-1 5-2 3 2 1] → [ 1 2 3 5-2 5-1 ]

 위와 같이 퀵 정렬은 같은 값이 있는 경우에 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있습니다.

이상으로 퀵 정렬 포스팅을 마치겠습니다.

안녕하세요, 여행벌입니다.

오늘은 셸정렬(shell sort)에 대해서 포스팅해보겠습니다.

셸 정렬의 원리

 셸 정렬(shell sort)은 Donald L. Shell 이라는 사람이 제안한 방법으로 삽입 정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠르게 정렬한다는 사실에 착안한 방법입니다.

 삽입 정렬의 최대 문제점은 요소들이 삽입될 때, 이웃한 위치로만 이동하기 때문에 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 많은 이동을 해야 합니다. 셸 정렬에서는 바로 이웃한 위치로만 이동하는 게 아니라 멀리 떨어진 위치로도 이동을 할 수 있습니다. 

 삽입 정렬과는 다르게 셸 정렬은 전체의 리스트를 한 번에 정렬하지 않습니다. 대신에 먼저 정렬해야 할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬합니다. 모든 부분 리스트가 정렬되면 셸 정렬은 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후에 이 과정을 되풀이합니다.

 부분 리스트를 구성할 때는 주어진 리스트의 각 K 번째 요소를 추출하여 만들고, 이 K를 간격(gap)이라고 합니다.

이 K를 줄여가며 수행 과정을 반복합니다.

 셸 정렬은 삽입 정렬을 보완할 정렬로 삽입 정렬에 비해 2가지 장점이 있습니다.

 1. 연속적이지 않은 부분 리스트에서 자료의 교환이 일어나면 더 큰 거리를 이동하므로 교환되는 요소들이 삽입 정렬보다는 최종 위치에 더 가까이 있을 가능성이 높아진다.

 2. 부분 리스트는 어느 정도 정렬이 된 상태이기 때문에 부분 리스트의 개수가 1이 되었을 때, 삽입 정렬이 훨씬 빠르게 수행된다.

셸 정렬 예시

( 10 2 5 4 1 6 9 8 7 3 ) 리스트를 셸 정렬을 이용해서 정렬해보겠습니다.

처음의 K(gap) = N / 2 = 5 입니다.

K가 5이므로 5칸 떨어진 요소들과 부분 리스트를 이루게 됩니다.

10과 6이 같은 부분 리스트이므로 6과 10으로 삽입 정렬을 통해 정렬됩니다.

2와 9 / 5와 8 / 4 와 7 / 1 과 3도 각각 같은 부분 리스트에 속하지만 정렬이 되어있으므로 삽입 정렬을 수행하지 않습니다.

이제 K(gap)을 반으로 줄입니다.

K가 2이므로 2칸 떨어진 요소들과 부분 리스트를 이루게 됩니다.

6 - 5 - 1 - 9 - 7 / 2 - 4 - 10 - 8 - 3 이 각각 부분 리스트를 이루게 되고,

각각 삽입 정렬을 통해 정렬하게 됩니다.

또, K(gap)을 반으로 줄입니다.

K가 1이므로 1칸 떨어진 요소, 즉 전체 리스트에 대해서 삽입 정렬을 수행합니다.

모든 과정을 표로 표현하면 다음과 같습니다.

셸 정렬 코드

 간격은 처음에는 n / 2 로 하고 각 패스마다 간격을 절반으로 줄여 간격이 1이 될 때까지 셸 정렬을 수행하면 된다.

void inc_insertion_sort(int list[], int first, int last, int gap) {
	int i, j, key;
	for (i = first + gap; i <= last; i += gap) {
		key = list[i];
		for (j = i - gap; first <= j && key < list[j]; j -= gap)
			list[j + gap] = list[j];
		list[j + gap] = key;
	}
	return;
}

void shell_sort(int list[], int n) {
	int i, gap;
	for (gap = n / 2; gap > 0; gap /= 2) {
		if (gap % 2 == 0)
			gap++;
		for (i = 0; i < gap; i++)
			inc_insertion_sort(list, i, n - 1, gap);
	}
}

셸 정렬 복잡도

 셸 정렬의 동작 원리는 삽입 정렬을 이용해서 정렬합니다. 따라서, 최악의 경우 , 최선의 경우가 삽입 정렬과 동일한 복잡도를 가집니다. 하지만 실험적인 연구를 통해서 셸 정렬의 평균 시간 복잡도는 삽입 정렬과 다르게 n^(1.5) 를 따른다고 합니다.

셸 정렬 안정성

 셸 정렬은 같은 값이 있는 경우 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있는 불안정 정렬에 속합니다.

 [ 5-1 5-2 3 2 1 ] 를 셸 정렬로 정렬해보겠습니다.

[ 5-1 5-2 3 2 1] → [ 1 2 3 5-2 5-1 ]

 위와 같이 셸 정렬은 같은 값이 있는 경우에 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있습니다.

이상으로 셸 정렬 포스팅을 마치겠습니다.

안녕하세요, 여행벌입니다.

오늘은 삽입 정렬(insertion sort)에 대해서 포스팅해보겠습니다.

삽입 정렬 이란

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여,

자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 정렬 방식입니다.

EX)

바로 예시를 통해서 익혀보도록 하겠습니다.

[ 3 1 2 5 4 8 7 6 ] 배열을 삽입 정렬을 통해서 정렬해보겠습니다.

STEP 

1은 현재 정렬되어 있는 부분 [ 3 ] 과 비교했을 때 맨 앞으로 가야 됩니다.

따라서, [ 1 3 ] 으로 정렬이 진행됩니다.

STEP 2]

2는 현재 정렬되어 있는 부분 [ 1 3 ] 에서 1 과 3 사이에 위치해야 합니다.

STEP 3]

5는 현재 정렬되어 있는 부분의 맨 뒤에 위치해야 하므로 다음 STEP을 진행한다.

STEP 4]

4는 현재 정렬되어 있는 부분의 3과 5 사이에 위치해야 합니다.

STEP 5]

8은 현재 정렬되어 있는 부분이 맨 뒤에 위치하면 되므로 다음 STEP으로 넘어간다.

STEP 6]

7은 현재 정렬되어 있는 부분이 5와 8 사이에 위치해야 합니다.

STEP 7]

마지막으로 6은 5와 7 사이에 위치해야 합니다.

예시를 통해 알 수 있듯이, 삽입 정렬은 해당 원소가 삽입되어야 하는 위치로 삽입을 진행하며 정렬하는 방식입니다.

그렇다면 해당 원소가 삽입되어야하는 위치로 어떻게 삽입할 수 있을까요??

정답은 해당 원소가 원하는 위치에 도달할 때까지 계속 옆의 원소와 교환(SWAP)을 진행하는 방법입니다.

예를 들어, [ 2 3 4 5 1 ] 과 같이 배열이 있을 때, 1은 [ 2 3 4 5 ] 배열 맨 앞으로 가야 합니다.

따라서, 5와 SWAP하고 4와 SWAP하고 3과 SWAP하고 2와 SWAP해 원하는 위치에 도달할 수 있습니다.

코드 구현

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

코드는 간단합니다.

i 번째 원소의 위치를 찾기 위해 i - 1 번 째 원소부터 차례대로 비교해나가며 자기 위치가 아니라면 SWAP을 진행합니다.

자기 위치를 찾았다면, while 문이 깨지고 찾은 위치 j + 1 번 째에 원소를 저장해줍니다.

복잡도 분석

N개의 원소가 있다고 가정하고 삽입 정렬의 복잡도를 분석해보겠습니다.

삽입 정렬은 버블 정렬, 선택 정렬과 다르게 최선의 경우, 최악의 경우 시간 복잡도가 다릅니다.

먼저, 최선의 경우(이미 배열이 정렬되어 있는 경우)에 대해서 생각해보겠습니다.

이미 자기 위치에 있는 원소는 옆에 있는 원소와 비교 연산 1회만 진행한 후 다음 STEP 으로 넘어가게 됩니다.

즉, 최선의 경우 N - 1 개의 원소에 대해서 비교 연산을 1번씩만 진행하면 되므로 O( N )의 복잡도를 가지게 됩니다.

그다음으로는 최악의 경우(배열이 역순으로 정렬되어 있는 경우)에 대해서 생각해보겠습니다.

모든 STEP마다 정렬되어 있는 배열의 모든 원소들과 비교 연산을 진행해야 하므로

총 ( N - 1 ) + ( N - 2 ) +  ⋯ + 1 번 비교 연산이 발생합니다.

등차수열의 합으로 O ( N ^ 2 ) 의 시간 복잡도를 가지는 것을 확인할 수 있습니다.

안정 정렬

삽입 정렬은 '안정 정렬' 입니다. 즉, 동일한 두 원소 간의 순서가 정렬 후에 바뀌지 않습니다.

삽입 정렬 작동 원리를 생각해보면 동일한 두 원소끼리는 이미 위치가 정해져 있으므로 순서가 바뀌지 않는 것을 쉽게 이해할 수 있습니다.

원활한 이해를 돕기 위해 [ 5-1  2  1  5-2 ] 를 삽입 정렬을 통해서 정렬해보겠습니다.

동일한 두 원소 5를 구분하기 위해 5-1 / 5-2 로 표현했습니다.

정렬 전 [ 5-1  2  1  5-2 ] → [ 2  5-1  1  5-2 ] → [ 1  2  5-1  5-2 ] 

다음과 같이 삽입 정렬은 안정 정렬인 것을 확인할 수 있습니다.

이상으로 삽입 정렬 포스팅을 마치겠습니다.