승섭 7/26

섭승이·2023년 7월 26일
개발일기자료구조
0

자료구조

목록 보기
10/12
post-custom-banner

Chapter 10. 정렬(Sorting)

복잡하지만 효율적인 정렬 알고리즘

힙 정렬(Heap Sort) : 이해와 구현

힙 정렬이란 “힙의 루트 노드에 저장된 값이 가장 커야 한다.” 라는 특성을 활용하여 정렬하는 알고리즘으로 최대 힙의 특성을 사용하여 정렬한다.

#include <stdio.h>
#include "UsefulHeap.h"

// 오름차순 정렬을 위한 함수
int PriComp(int n1, int n2)
{
	return n2-n1;
//	return n1-n2;
}

// 앞서 정리했던 힙을 이용해서 힙에 넣고 삭제하면서 정렬하면서 배열에 넣어준다.
void HeapSort(int arr[], int n, PriorityComp pc)
{
	Heap heap;
	int i;

	HeapInit(&heap, pc);

	// 정렬 대상을 가지고 힙을 구성한다.
	for(i=0; i<n; i++)
		HInsert(&heap, arr[i]);

	// 순서대로 하나씩 꺼내서 정렬을 완성한다.
	for(i=0; i<n; i++)
		arr[i] = HDelete(&heap);
}

int main(void)
{
	int arr[4] = {3, 4, 2, 1};
	int i;

	HeapSort(arr, sizeof(arr)/sizeof(int), PriComp);

	for(i=0; i<4; i++)
		printf("%d ", arr[i]);

	printf("\n");
	return 0;
}

코드에서 보이는 것 처럼 정렬의 대상인 데이터들을 힙에 넣었다가 꺼내는 것이 전부인데 정렬이 완료되는 이유는, 꺼낼 때 힙의 루트 노드에 저장된 데이터가 반환되기 때문이다.

힙의 데이터 저장 및 삭제의 시간 복잡도는 O(log2n) 으로 성능이 좋은 편에 속하며, 정렬 과정에 대한 시간 복잡도는 정렬대상의 수가 n개일때, 총 n개의 데이터를 삽입 및 삭제해야 하므로 위의 빅-오에 n을 곱해야한다. 따라서 O(nlog2n) 이 된다.

이는 O(n^2) 의 성능을 보이는 알고리즘을 O(nlog2n)의 성능을 보이도록 개선한다면, 활용이 가능한 수준으로 개선했다고 평가 받을 수 있다.

병합 정렬(Merge Sort) : 이해와 구현

병합 정렬은 “분할 정복(Devide and conquer)” 이라는 알고리즘 디자인 기법에 근거하여 만들어진 정렬 방법이다.

“8개의 데이터를 동시에 정렬하는 것보다, 이를 둘로 나눠서 4개의 데이터를 정렬하는 것이 쉽고, 또 이들 각각을 다시 한번 둘로 나눠서 2개의 데이터를 정렬하는 것이 더 쉽다.”

위에 그림에서 보이듯이 우선 분할의 과정을 거치고, 병합을 진행하는 과정에서 정렬을 진행한다.

#include <stdio.h>
#include <stdlib.h>

// 두 번의 MergeSort 함수호출의 결과로 정렬된 두 영역을 하나로 묶기 위한 함수
void MergeTwoArea(int arr[], int left, int mid, int right)
{
	int fIdx = left;
	int rIdx = mid+1;
	int i;

	// 병합한 결과를 담을 배열 sortArr의 동적 할당
	int * sortArr = (int*)malloc(sizeof(int)*(right+1));
	int sIdx = left;
	
	// 병합할 두 영역의 데이터를 비교하여, 정렬 순서대로 sortArr에 옮겨 담음
	while(fIdx<=mid && rIdx<=right)
	{
		if(arr[fIdx] <= arr[rIdx]) 
			sortArr[sIdx] = arr[fIdx++];
		else
			sortArr[sIdx] = arr[rIdx++];

		sIdx++;
	}

	// 배열의 앞부분이 모두 sortArr에 옮겨졌다면
	if(fIdx > mid)
	{
		for(i=rIdx; i<=right; i++, sIdx++)
			sortArr[sIdx] = arr[i]; // 배열의 뒷부분에 남은 데이터들을 sortArr에 그대로 옮긴다.
	}

	// 배열의 뒷부분이 모두 sortArr에 옮겨졌다면
	else
	{
		for(i=fIdx; i<=mid; i++, sIdx++)
			sortArr[sIdx] = arr[i]; // 배열의 앞부분에 남은 데이터들을 sortArr에 그대로 옮긴다.
	}

	for(i=left; i<=right; i++)
		arr[i] = sortArr[i];
	
	free(sortArr);
}

// 분할하는 함수
void MergeSort(int arr[], int left, int right)
{
	int mid;

	if(left < right)
	{
		// 중간 지점을 계산한다.
		mid = (left+right) / 2;

		// 둘로 나눠서 각각을 정렬한다.
		MergeSort(arr, left, mid);
		MergeSort(arr, mid+1, right);

		// 정렬된 두 배열을 병합한다.
		MergeTwoArea(arr, left, mid, right);
	}
}

int main(void)
{
	int arr[7] = {3, 2, 4, 1, 7, 6, 5};
	int i;

	// 배열 arr의 전체 영역 정렬
	MergeSort(arr, 0, sizeof(arr)/sizeof(int)-1);

	for(i=0; i<7; i++)
		printf("%d ", arr[i]);

	printf("\n");
	return 0;
}


여기서 중요한 코드는 MergeTwoArea 함수 안에 있는 while문인데 위의 그림에서 3번째 부분을 예로 들면

  • 3과 1 비교 ⇒ 비교연산 후 1을 sortArr로 이동, 그리고 rIdx의 값 1증가
  • 3과 4 비교 ⇒ 비교연산 후 3을 sortArr로 이동, 그리고 fIdx의 값 1증가
  • 5와 4 비교 ⇒ 비교연산 후 4를 sortArr로 이동, 그리고 rIdx의 값 1증가
  • 5와 7 비교 ⇒ 비교연산 후 5를 sortArr로 이동, 그리고 fldx의 값 1증가
  • 8과 7 비교 ⇒ 비교연산 후 7을 sortArr로 이동, 그리고 rIdx의 값 1증가
  • 8과 12 비교 ⇒ 비교연산 후 8을 sortArr로 이동, 그리고 fIdx의 값 1증가
  • 10과 12 비교 ⇒ 비교연산 후 10을 sortArr로 이동, 그리고 fIdx의 값 1증가

이러한 과정을 거친 후, fIdx는 mid를 넘어서는 위치를 가리키게 되어 비교가 무의미해지고 따라서 오른쪽 배열에 12가 남아 있으므로 12를 그대로 sortArr로 이동해준다.

병합 정렬 : 성능 평가

비교연산의 횟수는 MergeSort 함수가 아닌 MergeTwoArea 함수를 기준으로 계산해야 한다. while문의 비교연산의 횟수는 “정렬의 대상인 데이터 수가 n개 일 때, 각 병합의 단게마다 최대 n번의 비교연산이 진행된다” 따라서 최대 비교연산의 횟수는 O(nlog2n)이 된다.

이동연산의 횟수를 따지기 위해 이동이 발생하는 이유를 따진다.

  • 임시 배열에 데이터를 병합하는 과정에서 한 번
  • 임시 배열에 저장된 데이터 전부를 원위치로 옮기는 과정에서 한 번

따라서 2nlog2n이 되는데 빅-오에서 숫자 2는 무시할 수 있으므로 O(nlog2n)이 된다.

퀵 정렬(Quick Sort) : 이해와 구현!

위의 그림에서 볼 수 있듯이 퀵 정렬은 배열의 4개 지점에 이름을 부여해야한다.

  • left - 정렬대상의 가장 왼쪽 지점을 가리키는 이름
  • right - 정렬대상의 가장 오른쪽 지점을 가리키는 이름
  • pivot - 피벗이라 발음하고 중심점, 중심축의 의미를 담고 있다.
  • low - 피벗을 제외한 가장 왼쪽에 위치한 지점을 가리키는 이름
  • high - 피벗을 제외한 가장 오른쪽에 위치한 지점을 가리키는 이름

또한 퀵 정렬의 정렬 과정으로는

  • low 의 오른쪽 방향 이동 ⇒ 피벗보다 정렬의 우선순위가 낮은 데이터를 만날 때까지
  • high의 왼쪽 방향 이동 ⇒ 피벗보다 정렬의 우선순위가 높은 데이터를 만날 때까지
  • high와 low가 가리키는 위치가 교차되는 상황 발생
  • 피벗과 high의 위치를 바꿔줌

이 과정을 재귀적으로 진행

#include <stdio.h>

// 위치를 바꾸어주는 함수
void Swap(int arr[], int idx1, int idx2)
{
	int temp = arr[idx1];
	arr[idx1] = arr[idx2];
	arr[idx2] = temp;
}	

// 분할해서 정렬해주는 함수
int Partition(int arr[], int left, int right)
{
	int pivot = arr[left];    // 피벗의 위치는 가장 왼쪽
	int low = left+1;
	int high = right;

	while(low <= high)    // 교차되지 않을 때까지 반복
	{	
		
		// 피벗보다 큰 값을 찾는 과정
		while(pivot >= arr[low] && low <= right)
			low++; // low를 오른쪽으로 이동
		
		// 피벗보다 작은 값을 찾는 과정
		while(pivot <= arr[high] && high >= (left+1))
			high--; // high 를 왼쪽으로 이동
		
		// 교차되지 않은 상태라면 swap 실행
		if(low <= high)    //
			Swap(arr, low, high);    
	}

	Swap(arr, left, high);    // 피벗과 high가 가리키는 대상 교환
	return high;    // 옮겨진 피벗의 위치정보 반환
}

void QuickSort(int arr[], int left, int right)
{
	if(left <= right)
	{
		int pivot = Partition(arr, left, right);    // 둘로 나눠서
		QuickSort(arr, left, pivot-1);    // 왼쪽 영역을 정렬
		QuickSort(arr, pivot+1, right);    // 오른쪽 영역을 정렬
	}
}

int main(void)
{
  int arr[7] = {3, 2, 4, 1, 7, 6, 5};

	int len = sizeof(arr) / sizeof(int);
	int i;

	QuickSort(arr, 0, sizeof(arr)/sizeof(int)-1);

	for(i=0; i<len; i++)
		printf("%d ", arr[i]);

	printf("\n");
	return 0;
}

마지막으로 피벗을 선택해줄 때 피벗이 중간값에 해당할 경우 정렬대상은 균등하게 나뉘고 이 때 가장 효율이 좋다.

“정렬 대상에서 세 개의 데이터를 추출한다. 그리고 그 중에서 중간 값에 해당하는 것을 피벗으로 선택한다.”

가 가장 좋은 방법이 된다.

퀵 정렬 : 성능 평가

비교연산의 횟수로는 2가지로 단계를 나누어 계산한다.

  1. 하나의 피벗이 제 자리를 찾아가는 과정에서 발생하는 비교연산의 횟수
  2. 분할이 몇 단계에 걸쳐서 진행되는지

1번의 경우 데이터의 수에 해당하는 n-1이라고 할 수 있다.

2번의 경우 예를 들면 31개의 데이터를 대상으로 퀵 정렬을 진행한다고 가정해보면

  • 31개의 데이터는 15개씩 둘로 나뉘어 총 2조각이 된다. - 1차 나뉨
  • 이어서 각각 7개씩 둘로 나뉘어 총 4조각이 된다. - 2차 나뉨
  • 이어서 각각 3개씩 둘로 나뉘어 총 8조각이 된다. - 3차 나뉨
  • 이어서 각각 1개씩 둘로 나뉘어 총 16조각이 된다. - 4차 나뉨

즉 log2n이라고 할 수 있다. 따라서 2개의 비교연산 횟수를 곱하면 빅-오는 O(nlog2n)이 됨을 알 수 있다.

퀵 정렬의 시간 복잡도는 최선의 경우에 가까운 성능을 평균적으로 보이기 때문에 최선의 경우를 시간복잡도로 계산한다.

최악의 경우 비교연산의 빅-오는 O(n^2)가 되므로 힙 정렬, 병합 정렬보다 안좋은 성능을 가진다고 생각할 수 있는데, 실제로 퀵 정렬은 위의 2개의 정렬보다 평균적으로 제일 빠른 것으로 알려져 있다. 그 이유로는 이동횟수가 상대적으로 적고, 메모리 공간을 요구하지 않는 다는 점에서 찾을 수 있다.

정리하면, 퀵 정렬은 시간복잡도가 O(nlog2n)인 알고리즘이며, 데이터의 이동이 데이터의 비교에 비해 현저히 적게 일어나고, 별도의 메모리 공간을 요구하지 않으므로 동일한 빅-오를 갖는 다른 정렬 알고리즘 중에서 평균적으로 가장 빠른 정렬속도를 보이는 알고리즘이다.

기수 정렬(Radix Sort) : 이해와 구현

기수 정렬은 정렬순서상 앞서고 뒤섬의 판단을 위한 비교연산을 하지 않는다.

기수 정렬의 장점으로는 비교연산을 하지 않고 정렬을 하며 시간복잡도 빅-오가 O(n) 으로 정렬 알고리즘 중에서 가장 좋은 성능을 가진다.

기수 정렬의 단점으로는 “적용할 수 있는 범위가 제한적”이라는 것이다.

위 그림은 기수정렬을 그림으로서 표현한 것이고, 위의 방법은 LSD 기수 정렬(덜 중요한 자릿수에서부터 정렬을 진행해 나감) 으로 표현된 방식이다.

우선 10진수이므로 배열을 10개 만들어주고 일의 자리부터 정렬하고 10의 자리를 정렬해줌으로서 정렬이 완성되는 구조이다.

기수정렬에는 MSD 기수 정렬 방식도 있지만, MSD 기수 정렬 방식은 중간의 데이터를 계속 점검해주어야한다.

점검해주지 않으면 예상치 못한 결과를 반환하기 때문이다. 따라서 기수정렬에는 LSD방식을 보통 많이 사용한다.

#include <stdio.h>
#include "ListBaseQueue.h"

#define BUCKET_NUM		10

// 매개변수 maxLen에는 정렬대상 중 가장 긴 데이터의 길이 정보가 전달
void RadixSort(int arr[], int num, int maxLen)   
{
	Queue buckets[BUCKET_NUM];
	int bi;
	int pos;
	int di;
	int divfac = 1;
	int radix;

	// 총 10개의 버킷 초기화
	for(bi=0; bi<BUCKET_NUM; bi++)
		QueueInit(&buckets[bi]);

	// 가장 긴 데이터의 길이만큼 반복
	for(pos=0; pos<maxLen; pos++)
	{ 
		// 정렬대상의 수 만큼 반복
		for(di=0; di<num; di++)
		{
			// N번째 자리의 숫자 추출
			radix = (arr[di] / divfac) % 10;

			// 추출한 숫자를 근거로 버킷에 데이터 저장
			Enqueue(&buckets[radix], arr[di]);
		}

		// 버킷의 수만큼 반복
		for(bi=0, di=0; bi<BUCKET_NUM; bi++)
		{
			// 버킷에 저장된 것 순서대로 다 꺼내어 다시 arr에 저장
			while(!QIsEmpty(&buckets[bi]))
				arr[di++] = Dequeue(&buckets[bi]);
		}

		// N번째 자리의 숫자 추출을 위한 피제수의 증가 
		divfac *= 10;
	}	
}

int main(void)
{
	int arr[7] = {13, 212, 14, 7141, 10987, 6, 15};

	int len = sizeof(arr) / sizeof(int);
	int i;

	RadixSort(arr, len, 5);

	for(i=0; i<len; i++)
		printf("%d ", arr[i]);

	printf("\n");
	return 0;
}

기수 정렬(radix sort) : 성능 평가

기수 정렬은 비교연산이 핵심이 아니라 버킷으로의 데이터 삽입과 추출이 핵심이다. 따라서 이 정렬의 시간 복잡도는 삽입과 추출의 빈도수를 대상으로 결정해야 한다.

2개의 포문이 바로 시간 복잡도를 계산해야하는 코드이며 한 쌍의 연산이 수행되는 횟수는 다음과 같다.

“maxLen * num” 따라서 정렬대상의 수가 n이고 모든 정렬대상의 길이가 l이라 할때 시간복잡도 빅-오는 O(n)이 된다. 따라서 정렬 알고리즘 중 가장 빠르지만 적용 가능한 대상이 제한적이라는 단점이 있음을 확인할 수 있다.

profile
섭승이
초보개발자입니당
이전 포스트

승섭 7/25

다음 포스트

승섭 8/1

post-custom-banner

0개의 댓글