[모아 놓고 말해보자] 정렬알고리즘

 

정렬이 필요한 이유 = 탐색

데이터가 정렬되어 있다면 '이진 탐색'을 사용할 수 있다. 이진 탐색 알고리즘은 최악의 경우엔서 O(log n)의 성능을 보이기 때문에 강력하며, 이를 위해서는 정렬이 선행되어야한다.

 

대표적인 정렬 알고리즘

 

[Bubble Sort] 평균 실행 시간 : $O(n^2)$ / 최악 실행 시간 : $O(n^2)$ / 메모리 $O(1)$

 

한 번 iteration을 돌때마다 하나의 값을 정렬한다. 한 번의 iteration에서 첫번째, 두번째를 비교, 두번째와 세번째를 비교 ... 이런 형태로 $n-1$번째와 $n$번째를 비교함으로써 마지막 값을 정렬한 후 다시 앞에서부터 비교해서 $n-1$번째 값을 정렬하는 형태로 동작한다. 최악의 경우에 매 iteration마다 처음부터 끝까지 다 비교를 수행해야하므로 최대 $\frac{n(n-1)}{2}$ 번의 비교를 해야한다. 이해하기 쉽고 코드가 짧다는 장점이 있지만, 굉장히 비효율적이다.

 

for tgt_id in range(0, len(arr)-1):
	for id in range(tgt_id+1, len(arr)):
    	    if arr[tgt_id] > arr[id]:
        	# exchange each other
                arr[tgt_id], arr[id] = arr[id], arr[tgt_id]

 

 

[Selection Sort] 평균 실행 시간 : $O(n^2)$ / 최악 실행 시간 : $O(n^2)$ / 메모리 $O(1)$

버블 정렬이 비교 결과를 바탕으로 계속해서 값을 바꿔넣는대신 selection sort는 계속 바꾸지 않고, 제일 작은거를 찾아서 해당 위치에 가져다놓는 형태로 sorting한다. 결국 비교 횟수는 $\frac{n(n-1)}{2}$로 Bubble sort와 동일하지만, exchange 횟수가 적다는 점에서 버블 정렬보다 항상 우수하다.

 

 

[Insertion Sort] 평균 실행 시간:  $O(n^2)$ / 최악 실행 시간: $O(n^2)$ / 메모리 $O(1)$

k번째 값을 1~k-1까지의 값들과 비교하여 적절한 위치에 끼워넣는 형태로 동작하는 알고리즘이다. Bubble Sort나 Selection Sort가 뒤의 '정렬되지 않은 값'들과 비교하여 특정 위치의 값을 찾는 대신, Insertion sort 는 현재의 정렬 타겟이 앞에 이미 정렬된 값들과 비교하여 어느 위치에 넣을지 찾아서 끼워넣어준다. 이 때 '적절한 위치에 끼워 넣는다'는 행동은 해당 위치 이후의 값들을 뒤로 밀어내는 단계가 필요하기 때문에 자료 구조에 따라 뒤로 밀어내는 오버헤드가 클 수 있다는 단점이 있다. 하지만 배열의 크기가 작은 경우에서는 빠르기 때문에 배열의 크기가 작을때는 자주 사용되는 알고리즘이다.

 

 

[Merge Sort] 평균, 최악 실행시간: $O(n \log n)$ / 메모리 상황에따라 다름.

 

원소의 수가 0 또는 1이 될때까지 계속해서 그룹을 나누고, 나누어진 순의 역순으로 원소를 비교 후 병합하는 형태로 sorting을 수행한다.

아래 그림은 merge sort의 과정을 도식화한 그림이다.

 

그림 출처: 나무 위키

void MERGE_SORT(int &arr, beg, end){
	if(beg < end){
		auto mid = (beg + end) / 2
		MERGESORT(arr, beg, mid);
		MERGESORT(arr, mid+1, end);
		MERGE(arr, beg, mid, end);
	}
}

void MERGE(int &arr, int beg, int mid, int end){

	// copy the array value into helper
	int* helperArr = new int[arr.length];
	for(auto i = 0; i < arr.length; ++i){
		helperArr[i] = arr[i];
	}

	int helperLeft = beg;
	int helperRight = mid + 1;
	int curr = beg; // index for target arr

	while(helperLeft <= mid && helperRight <= end){
		
		// compare helperLeft and helperRight
		if(helperArr[helperLeft] < helperArr[helperRight]){
			arr[curr++] = helperArr[helperLeft++];
		}else{
			arr[curr++] = helperArr[helperRight++];
		}
	}

	// move remaining left part of Helper into target array
	for(auto i = 0; i <= mid - helperLeft; ++i){
		arr[curr+i] = helperArr[helperLeft+i];
	}
	
}

 

Heap Sort $O(n \log n)$

Heap 을 사용하여 정렬하는 방식으로 정렬하고자하는 원소들을 모두 heap에 넣는다. Heap의 최 상단에 있는 값은 최소 혹은 최댓값을 가지기 때문에 Heap 데이터 구조로부터 pop하는 형태로 정렬된 원소들을 얻을 수 있다.

추가적인 메모리를 전혀 필요하지 않고, 평균적으로 $O(n log n)$ 정렬의 성능을 발휘한다는 장점이 있다. 하지만 실제 구현에서는 힙의 동작 overhead로인해 quick 정렬이 더 빠르게 동작한다. (Heap 정렬의 경우 cache로 인한 이득을 얻기 힘든 경우가 많기 때문에 그렇다) 

 

[Quick Sort] 평균 실행 시간 $O(n \log n)$, 최악 실행 시간 $O(n^2)$, 메모리 요구량 $O(\log n)$

평균적인 상황에서 최고의 성능을 내는 알고리즘이다. 하나의 값을 pivot으로 삼아 그 보다 작은 것을 앞으로, pivot보다 큰 값을 뒤로 옮긴다. 그리고 pivot을 기준으로 앞쪽의 list와 뒷쪽의 list를 동일한 방식으로 각각 pivot을 삼고 정렬한다. 언뜻보면 Merge Sort와 비슷한 형태의 divide & conqure로 생각할 수 있다. 다만 Quick Sort는 Merge Sort와 달리 균등한 크기로 분할되지 않는다.

 

pivot을 기준으로 큰 값, 작은 값을 옮기는 방법은 다음과 같다. pivot을 제외한 값들에서 low와 high를 각각 제일 왼쪽, 제일 오른쪽의 index로 잡는다. 그리고 low는 오른쪽으로 traverse하면서 피벗보다 큰 데이터를 찾으면 멈춘다. 반대로 high는 왼쪽으로 traverse하다가 피벗보다 작은 데이터를 찾으면 멈춘다. 그리고 low와 high가 가르키는 두 데이터는 교환한다. 이 동작은 low와 high가 서로를 지나칠때까지 반복된다. 이 때 지나친 경우의 high 지점에 pivot을 삽입한다.

 

참고로 merge sort와 달리, 한 pivot에 대해 동작이 끝나면 좌 우의 list는 sorting되어있지 않다. 다시 말해 merge sort 는 divdie 한 후 merge해가면서 sorting하기때문에 각각의 merge 단계에서 sorting된 값이 반환되는 대신 Quick sort는 divide 단계 없이 진행된다.

 

장점:

- 속도가 빠르다 (시간 복잡도가 $O(n log n)$인 알고리즘 들 중에서 '평균적으로' 가장 빠른 속도를 보인다)

- 추가 메모리 공간을 필요로 하지 않는다

단점: 

- pivot을 잘못 고르는 경우 불균형한 분할에 의해 수행 시간이 더 걸리는 문제가 있다.

- 다시 말해, 이미 정렬된 리스트에 대해서 sorting되는 경우 불균형한 list로 인해 pivot 선택의 횟수가 n이 되고, 이에 따라 $O(n^2)$이 된다.

 

 

끝.