자료 구조 - 정렬

정렬이란?

• 정렬은 크기 순으로 오름차순(ascending order)이나 내림차순(descending order)으로 나열하는 것

안정성(stability)

• 입력 데이터에 동일한 키값을 갖는 레코드가 여러 존재할 경우, 이 데이터들의 상대적인 위치가 정렬 후에도 바뀌지 않는 특성
• 안전성을 충족하는 정렬에는 삽입 정렬, 버블 정렬, 합병 정렬 등이 있다.

선택 정렬(selection sort)

• 0 인덱스 부터 시작해서 정렬이 안된 부분의 최솟값을 찾아 바꿔주는 정렬이다.

void selectionSort(int* array, int size)
{
	for(int i=0; i<size-1; ++i) {
		int minIdx = i;
		for(int j=i+1; j<size; ++j) {
			if(array[j] < array[minIdx]) {
				minIdx = j;
			}
		}
		swap(array[i], array[minIdx]);
	}
}

• 반복문이 중첩되므로 시간 복잡도는 $O(n^2)$ 이다.
• 그리고 안정성을 만족시키지 않는다.
  • 1, 3, 3, 2 인 경우 생각하기.
    • 1, 2, 3, 3(원래 인덱스 1) 로 바뀐다.

삽입 정렬(insertion sort)

• 카드놀이에서 숫자 카드를 받을 떄 올바른 자리에 넣는 거를 생각하면 됨.
• 이것도 인덱스 0 에서 시작해 정렬안된 부분의 애들을 하나씩 가져와 올바른 자리에 넣으면 된다.
• 아래 구현한 것보다는 i위치에서 왼쪽이랑 비교해 나가며 스왑해 나가는게 더 간단하게 구현 가능하다..

void insertionSort(int* array, int size)
{
	for(int i=1; i<size; ++i) {
		int temp = array[i];
		for(int j=0; j<i; ++j) {
			if(temp < array[j]) {
				for(int k=i; k > j; --k) {
					array[k] = array[k-1];
				}
				array[j] = temp;
				break;
			}
		}
	}
}

• 반복문이 중첩되므로 시간 복잡도는 $O(n^2)$ 이다.
• 안정성을 만족한다.
• 대부분의 레코드가 이미 정렬되어 있는 경우 효율적일 수 있다.

함수 포인터를 이용한 정렬 알고리즘 구현 (해보기)

버블 정렬(bubble sort)

• 인접한 두 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 교환하는 방식
• 모든 레코드를 비교하고 나면 가장 큰 숫자가 마지막 인덱스로 가게 된다.

void bubbleSort(int* array, int size)
{
	for (int i=size-1; i >= 0; --i) {
		for(int j=0; j < i; ++j) {
			if(array[j] > array[j+1]) {
				swap(array[j], array[j+1]);
			}
		}
	}
}

• 최상, 최악, 평균 모두 비교횟수 동일하다.
• 반복문이 중첩되므로 $O(n^2)$ 시간복잡도를 가진다.
• 위치를 찾고 났을 때 그 뒤 정렬된 부분은 비교하지 않는 방식으로 약간 개선할 수 있다.

셸 정렬(shell sort)

• gma.’

합병 정렬(merge sort)

• 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분을 정렬한 다음 두 리스트를 합하여 전체가 정렬된 리스트를 만드는 방법.
• 분할 정복(divide and conquer) 기법에 바탕을 둔다.

void mergeSort(int* array, int left, int right)
{
	if(right - left == 0) return;
	int mid = (right - left) / 2 + left;
	mergeSort(array, left, mid);
	mergeSort(array, mid+1, right);
	int temp[right-left+1];
	int idx = 0, l = left, r = mid+1;
	while(l <= mid && r <= right) {
		if(array[l] <= array[r]) {
			temp[idx++] = array[l++];
		} else {
			temp[idx++] = array[r++];
		}
	}
	if (idx != right-left+1) {
		if(l != mid+1) {
			for(; l<=mid; ++l) {
				temp[idx++] = array[l];
			}
		} else {
			for(; r<=right; ++r) {
				temp[idx++] = array[r];
			}
		}
	}
	for(int i=0; i<right-left+1; ++i) {
		array[left+i] = temp[i];
	}
}

• 분할 과정에서 $log_2n$, 합병 과정에서 원소들을 비교해보고 복사하는 과정에서 각 $n$ 시간 복잡도가 필요하다.
• 총 시간 복잡도는 $nlog_2n$ 이다.
• 안정성 특징을 가지고 있다.
• 최악, 평균, 최선의 경우에 모두 동일한 시간에 정렬된다.
• 임시 배열이 필요하다는 단점이 있다.
• 레코드의 크기가 큰 경우 포인터(혹은 링크 인덱스)만 이동하는 방법이 좋다.

퀵 정렬(quick sort)

• 평균적으로 매운 빠른 정렬 속도를 가진다.
• 합병 정렬처럼 분할 정복법을 사용한다.
• 균등하게 분할하는 것이 아닌 피벗(pivot)을 기준으로 분할한다.
• 리스트의 첫 요소를 피벗으로 설정하는 방법으로 구현해 본다.
• 피벗을 기준으로 피벗보다 큰 요소들은 오른쪽으로 보내고 작은 요소들은 왼쪽으로 보낸다.
• 나뉜 두 구역을 대상으로 반복한다.

void quickSort(int* array, int size)
{
	if(size <= 1) return;
	int pivot = array[0];
	int left = 1, right = size-1;
	while(left <= right) {
		while(array[right] > pivot && left <= right) right--;
		while(array[left] <= pivot && left <= right) left++;
		if(left > right) break;
		swap(array[left], array[right]);
	}
	if(array[right] < pivot) swap(array[right], array[0]);
	quickSort(array, right);
	quickSort(array+right+1, size-right-1);
}

• 시간 복잡도는 $O(nlog_2n)$ 이다.
• 최악의 경우는 정렬된 상태인 리스트를 퀵 정렬 할 때인데, 이떄 시간 복잡도는 $O(n^2)$ 이다.
  • 피벗을 통해 파티션을 나누지 못하기 때문..
  • 이를 해결하기 위해 리스트 내 몇 개의 데이터 중 중위값(median)을 피벗으로 택하는 방법이 있음.
    • 리스트의 왼쪽, 중간, 오른쪽 값 중 중간 값을 선택하는 방법임.
• 속도가 빠르고 추가 메모리 공간을 필요로 하지 않는다는 장점이 있음
• 안정적이지 않다.

힙 정렬

• 힙에 모든 원소를 넣고 순서대로 빼는 방법.
• 시간 복잡도는 $O(nlog_2n)$ 이다.
• 전체 리스트 중 일부만 정렬할 필요가 있는 경우에 효율적이다.

기수 정렬(radix sort)

• 시간 복잡도는 $O(kn)$ 이지만 대부분 k의 값은 4이하이다.
• 10진수를 예를 들면 0에서 9까지 총 10개의 버킷(bucket)을 먼저 만든다.
• 각 자리수 마다 정렬을 해주면 된다.
• 안정성을 부여하기 위해
  • 1의 자리 먼저 시작해서 정렬을 먼저 하고,
  • 10의 자리로 넘어가서 정렬 하면 된다.