정렬

with MK·2020년 10월 26일
0

자료구조

목록 보기
2/2

단순한 정렬 알고리즘

버블 정렬

버블 정렬은 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식이다.

#include <cstdio>
void BubbleSort(int arr[], int n){
    int temp;
    for(int i = 0; i < n - 1; i++){
    	for(int j = 0; j < (n - i) -1; j++){
            if(arr[j] > arr[j + 1]){
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}
int main(){
    int arr[4] = {3, 2, 4, 1};
    BubbleSort(arr, sizeof(arr) / sizeof(int));
    ....
}

버블 정렬 성능평가

O(n^2)의 성능을 갖는다.
네스티드 포문에서 포문을 돌 때 마다 맨 뒤쪽은 정렬이 된 상태이므로 - i 연산을 해준다.

선택정렬

선택 정렬은 정렬 순서에 맞게 하나씩 선택해서 옮기는, 옮기면서 정렬이 되게 하는 알고리즘이다. 개선 시킨 경우의 선택 정렬은 빈 자리를 활용하는 알고리즘을 사용한다. 교환이 핵심이다.

#include <cstdio>

void SelSort(int arr[], int n) {
	int maxIdx;
	int temp;

	for (int i = 0; i < n - 1; i++) {
		maxIdx = i;

		for (int j = i + 1; j < n; j++) { // 최솟값 탐색
			if (arr[j] < arr[maxIdx])
				maxIdx = j;
		}

		temp = arr[i];
		arr[i] = arr[maxIdx];
		arr[maxIdx] = temp;
	}
}
int main() {
	int arr[4] = { 3,4,2,1 };
	SelSort(arr, sizeof(arr) / sizeof(int));
	for (int i = 0; i < 4; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
	return 0;
}

해당 알고리즘의 성능은 O(n^2)이다.
데이터의 이동횟수의 기준에서 바라보면 버블정렬의 경우 최악의 경우 계속해서 데이터의 이동이 발생하지만, 선택정렬의 경우 포문 바깥쪽에 데이터 이동의 코드가 있기 때문에, 최악의 경우와 최선의 경우 구분 없이 O(n)이고, 버블 정렬의 경우 최악의 경우 O(n^2), 최선의 경우 데이터의 이동이 한 번도 일어나지 않는다.
두 알고리즘 모두 비교연산에서는 O(n^2)의 성능을 갖는다.

최악의 경우를 놓고 보면 버블 정렬보다 선택 정렬에 좋은 성능을 기대할 수 있겠지만, 버블 정렬은 최선의 경우에 단 한 번의 데이터 이동도 발생하지 않는다는 점과, 실제로 데이터들이 늘 최악의 상황으로 배치되지 않는다는 사실을 감안하면, 이 둘의 우열을 가리는 것은 무의미하다고 할 수 있다.

삽입 정렬

삽입 정렬은 정렬 대상을 두 부분으로 나눠서, 정렬이 안 된 부분에 있는 데이터를 정렬 된 부분의 특정 위치에 삽입해 가면서 정렬을 진행하는 알고리즘이다.
삽입위치를 찾는 과정과 삽입을 위한 공간마련의 과정을 구분할 필요가 없다. 정렬이 완료된 영역의 다음에 위치한 데이터가 다음 정렬 대상이므로 교환을 해가면서 앞으로 끌고나간다.

#include <cstdio>

void InserSort(int arr[], int n) {
	int insData;
	int i, j;
	for (i = 1; i < n; i++) {
		insData = arr[i];
		for (j = i - 1; 0 <= j; j--) {
			if (insData < arr[j]) // 비교대상 한 칸 뒤로 밀기
				arr[j + 1] = arr[j];
			else break; // 삽입 위치 찾았으니 탈출
		}
		arr[j + 1] = insData; // 찾은 위치에 정렬대상 삽입
	}
}

int main(void) {
	int arr[5] = { 5,3,2,4,1 };
	int i;
	InserSort(arr, sizeof(arr) / sizeof(int));
	for (i = 0; i < 5; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
	return 0;
}

삽입 정렬은 정렬대상의 대부분이 정렬되어 있는 경우 매우 빠르게 동작한다. 정렬이 완전한 상태라면 break를 타고 데이터 이동이 발생하지 않는다. 그러나 최악의 경우를 고려하면 break를 단 한번도 실행하지 않기 때문에 for문의 반복횟수만큼 비교연산과 이동연산이 진행된다.
따라서 O(n^2)의 성능을 갖는다.

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

병합 정렬

디바이드 앤 컨커 방식으로 문제를 해결하는 알고리즘이다.
실제 정렬은 나눈 것을 병합하는 과정에서 이루어지고, 데이터가 1개만 남을 때까지 분할을 해 나간다. 데이터가 2개만 남아도 정렬을 할 필요가 있지만, 데이터가 1개만 남으면 그 조차 불필요해지기 때문이다.

#include <cstdio>
#include <cstdlib>
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;
    
    // 병합 할 두 영역의 데이터들을 비교하여, 정렬 순서대로 옮겨 담는다.
	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];
	}
	else {
		for (i = fIdx; i <= mid; i++, sIdx++)
			sortArr[sIdx] = arr[i];
	}
    
	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;
	MergeSort(arr, 0, sizeof(arr) / sizeof(int) - 1);
	for (i = 0; i < 7; i++) {
		printf("%d ", arr[i]);
	}
	printf("\n");
	return 0;
}

MergeTwoArea의 구현이 관건이다.

병합 정렬의 성능은 MergeTwoArea 함수를 기준으로 계산해야 한다. 비교연산과 이동연산이 실제 정렬을 진행하는 해당 함수를 중심으로 진행되기 때문이다.

정렬의 대상인 데이터의 수가 n개일 때 각 병합의 단계마다 최대 n 번의 비교 연산이 진행된다.
비교 연산의 관점에서 O(nlog(2)n)이다.
이동의 관점에서 임시 배열에 데이터를 병합하는 과정에서 한 번
임시 배열에 저장된 데이터 전부를 옮기는 과정에서 한 번이므로
비교연산에 비해 두 배의 연산이 이루어진다. 따라서 빅오는 같다.

퀵 정렬

가장 왼쪽에 있는 데이터를 퀵 정렬에 필요한 피벗으로 정한다.
low는 피벗을 제외한 가장 왼쪽에 위치한 지점을 가리키고, high는 피벗을 제외한 가장 오른쪽에 위치한 지점을 가리킨다.
low는 피벗보다 큰 값을 만날 때까지 오른쪽으로 이동하고, high는 피벗보다 작은 값을 만날 때까지 왼쪽으로 이동한다.
이동이 끝나면 그 둘 데이터의 위치를 교환한다.
교환이 끝나면 다시 그자리부터 이동을 시작한다.
low와 high의 위치가 교차되는 상황이 발생하는데 이때 피벗과 high가 가리키는 데이터를 서로 교환한다.
이것이 퀵 정렬의 핵심이다. 위의 수행이 모두 끝나면 피벗은 자신의 자리를 되찾게 된다. 즉 피벗보다 작은 것들은 피벗의 왼쪽에, 피벗보다 큰 것들은 피벗의 오른쪽에 자리한다.
처음 피벗이 자리를 잡으면 그 왼쪽 영역과 오른쪽 영역을 마치 병합정렬을 하듯 각각 위의 과정을 거친다.
left > right의 상황에서 더 이상 정렬할 대상이 없게 되므로 퀵 정렬은 끝나게 된다.

#include <cstdio>

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 (arr[low] <= pivot && low <= right) low++;
		while (pivot <= arr[high] && (left + 1) <= high) high--;
		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() {
	int arr[7] = { 3,2,4,1,7,6,5 };
	int len = sizeof(arr) / sizeof(int);
	QuickSort(arr, 0, len - 1);
	for (int i = 0; i < len; i++)
		printf("%d ", arr[i]);
	printf("\n");
	return 0;
}

비교 연산은 데이터의 수에 해당하는 n이고 데이터가 쪼개지므로 O(nlog(2)n)이다.
최악의 경우 n^2을 보이기는 하나, 중간에 가까운 피벗을 설정하는 연산을 더해 늘 최선에 가까운 결과를 보이고, 데이터의 이동이 데이터의 비교에 비해 현저히 적게 일어나고, 별도의 메모리 공간을 요구하지 않기 때문에 동일한 빅오를 갖는 다른 정렬 알고리즘 중에서 평균적으로 가장 빠른 정렬 속도를 보이는 알고리즘이다.

0개의 댓글