[Algorithm]향상된 정렬

📚퀵 정렬

📄기본 개념

특정 데이터를 기준으로 배열을 두 개의 부분배열로 분할하고, 각 부분배열에 대해 퀵정렬을 순환적으로 적용하는 방식이다.

📄피벗

배열을 두 개의 부분배열로 분할할 때 기준이 되는 특정 데이터를 말한다.

보통 주어진 배열의 첫 번째 데이터를 피벗으로 지정한다.

📄원리

피벗이 제자리를 잡도록 하는 정렬 방식이다.

퀵 정렬을 수행하면 왼쪽 부분배열의 값들은 피벗보다 작고 오른쪽 부분배열의 값들은 피벗보다 크다.

피벗 위치를 분할함수로 결정하고 왼쪽 부분배열과 오른쪽 부분배열에 대해 퀵 정렬을 순환적으로 처리한다.

📄퀵 정렬 알고리듬

QuickSort(array[], n)
{
	if(n > 1)
	{
		// 피벗 기준으로 두 개의 부분배열로 분할
		// 피벗은 제자리를 잡은 피벗의 위치(인덱스)를 표시
		pivot = Partition(array[0,...,n-1], n);

		// 왼쪽 부분배열에 대한 퀵 정렬 순환 호출
		QuickSort(array[0,...,pivot-1], pivot);
		// 오른쪽 부분배열에 대한 퀵 정렬 순환 호출
		QuickSort(array[pivot+1,...,n-1], n-pivot-1)
	}
}

📄부분배열 분할 과정

피벗이 되는 배열의 첫 번째 원소를 제외하고 배열의 양 끝에서부터 중앙 쪽으로 동시에 검색하면서 각각 피벗보다 큰 데이터와 작은 데이터를 찾는다.

int Partition(array[], n)
{
	left = 1, right = n -1;

	while(left < right)
	{
		while(left < n && array[left] < array[0])
		{
			left++;
		}
		while(right > 0 && array[right] >= array[0])
		{
			right--;
		}

		if(left < right)
		{
			array[left]와 array[right] 위치 교환
		}
		else
		{
			피벗과 array[right] 위치 교환
		}
	}

	return right;
}

📄성능과 특징

• 분할 함수 Partition()의 성능: Θ(n)

피벗과의 비교 횟수

각 데이터는 피벗과 1회 또는 많아야 2회씩 비교(비교 횟수는 데이터 크기에 비례)

• 퀵 정렬 QuickSort()의 성능

퀵 정렬의 수행시간은 분할되는 두 부분배열의 크기에 따라 달라진다.

QuickSort(A[], n)
{
	pivot = Partition(A[0...n-1], n);		// Θ(n)
	QuickSort(A[0..pivot-1], pivot);		// T(nL)
	QuickSort(A[pivot+1..n-1], n-pivot-1);	// T(nR)
}

T(n) = T(n_L) + T(n_R) + Θ(n)

배열이 어떤 크기의 두 부분배열로 분할되는냐에 따라 Partition() 함수 호출 횟수가 달라지고, 퀵 정렬 전체 성능 T(n)을 결정한다. 퀵 정렬 시간 복잡도는 최악의 경우, 최선의 경우, 평균적인 경우로 구분해서 살펴봐야 한다.

• 최악의 경우

배열이 항상 0:n-1 또는 n-1:0으로 분할되는 경우 -> 배열이 이미 정렬되어 있는 경우

피벗만 제자리를 잡고 나머지 모든 원소가 하나의 부분배열이 되는 경우이다.

피벗이 항상 부분배열의 최솟값 도는 최댓값이 되는 경우이다.

입력 데이터가 정렬된 경우와 피벗을 배열의 첫 번째 원소로 정한 경우 최악의 경우가 발생할 수 있다.

T(n) = T(n-1) + T(0) + Θ(n) (n > 1), T(1) = 1

T(n) = T(n-1) + Θ(n)

T(n) = O(n²)

• 최선의 경우

배열이 항상 n/2:n/2로 분할되는 경우

피벗을 중심으로 항상 동일한 크기의 두 부분배열로 분할되는 경우

피벗이 항상 배열의 중간값이 되는 경우

T(n) = T(n/2) + T(n/2) + Θ(n)

T(n) = 2T(n/2) + Θ(n)

T(n) = O(nlogn)

• 퀵 정렬의 평균 수행시간

부분배열의 모든 분할 비율에 따른 수행시간의 평균

피벗은 동일한 확률을 가지고 분할 후 배열의 어느 곳에나 위치 가능

T(n) = O(nlogn)

퀵 정렬은 피벗 선택의 임의성만 보장되면 평균 수행시간을 보장한다.

최악의 수행시간이 일어나는 경우는 피벗을 배열의 첫 번째 원소로 지정하는 경우와 배열이 정렬된 경우 일어난다. 주어진 배열이 정렬되어 있는지 아닌지 알 수 없기 때문에 우리는 피벗을 조절하여 최악의 수행시간이 일어나는 경우를 피할 수 있다.

배열에서 임의의 값을 선택한 후, 배열의 첫 번째 원소와 서로 교환하고 정렬을 수행하는 방식이다.

• 제자리 정렬 알고리듬

입력 배열 이외에 추가적인 저장 공간을 상수 개만 사용한다.

• 안정적이지 않은 정렬 알고리듬

• 분할정복 방법이 적용된 알고리듬

분할: 피벗을 기준으로 주어진 배열을 두 부분배열로 분할 -> 두 부분배열의 크기는 일정하지 않다.

정복: 두 부분배열에 대해 퀵 정렬을 순환적으로 적용하여 각 부분배열을 정렬한다.

결합: 필요 없음

📚합병 정렬

📄기본 개념

주어진 배열을 동일한 크기의 두 부분배열로 분할하고, 각 부분배열에 순환적으로 합병 정렬을 적용하여 정렬시킨 후, 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만든다.

📄알고리듬

• 합병 정렬 알고리듬

MergeSort(A[], n)
{
	if(n > 1)
	{
		// 배열 A[] 중앙 인덱스
		Mid = n/2;
		// 왼쪽 부분배열의 순환 호출 -> 크기 n/2인 정렬된 배열 B[] 반환
		B[0..Mid-1] = MergeSort(A[0..Mid-1], Mid);
		// 오른쪽 부분배열의 순환 호출 -> 크기 n/2인 정렬된 배열 C[] 반환
		C[0..n-Mid-1] = MergeSort(A[Mid..n-1], n-Mid);
		// 정렬된 두 부분배열 B[]와 C[]의 합병: A[] = B[] + C[]
		A[0..n-1] = Merge(B[0..Mid-1], C[0..n-Mid-1], Mid, n-Mid);
	}

	return(A);
}

• 합병 함수

Merge(B[], C[], n, m)
{
	i = j = k = 0;
	while(i < n && j < m)
	{
		// 부분배열 B[]와 C[] 비교해서 작은 데이터 선택
		if(B[i] <= C[j])
		{
			A[k++] = B[i++];
		}
		else
		{
			A[k++] = C[j++];
		}
	}

	// 부분배열 B[]에 남아 있는 모든 데이터 A[]로 이동
	for(; i < n; i++)
	{
		A[k++] = B[i];
	}
	// 부분배열 C[]에 남아 있는 모든 데이터 A[]로 이동
	for(; j < m; j++)
	{
		A[k++] = C[j];
	}

	return(A[0..n+m+1])
}

📄성능과 특징

• 합병 함수 Merge()의 수행시간: Θ(n)

두 부분배열 B[]와 C[]간의 비교 횟수(데이터 크기에 비례)

• 합병 정렬 MergeSort()의 수행시간: O(nlogn)

T(n) = T(n/2) + T(n/2) + Θ(n) (n > 1), T(1) = 0

T(n) = 2T(n/2) + Θ(n)

T(n) = O(nlogn)

• 안정적인 정렬 알고리듬

합병 과정에서 동일한 두 데이터에 대해 항상 왼쪽 데이터를 먼저 선택

• 제자리 정렬 알고리듬이 아님

입력 크기 n만큼의 추가적인 공간을 요구

• 분할정복 방법이 적용된 알고리듬

분할: 주어진 배열을 동일한 크기의 2개의 부분배열로 분할

정복: 각 부분배열에 대해 합병 정렬을 순환적으로 적용하여 정렬

결합: 정렬된 두 부분배열을 합병하여 하나의 정렬된 배열을 만듦

• 비순환적 방식으로도 구현 가능

반복문을 사용한 비순환적 방식으로 구현 가능하다. 분할 과정 없이 단순하게 합병하는 과정만으로 정렬한다.