[Algorithm] Merge sort & Quick sort

Merge sort

Implementation

1. Divide
   1. 하나의 배열을 반으로 나눠 2개의 배열로 만든다.
2. Conquer
   1. Subarray가 충분히 작아졌다면, 정렬시킨다.
   2. Subarray가 충분히 작지 않다면, Recursion
3. Merge
   1. 정렬된 subarray를 합쳐서 하나의 배열로 만든다.

 

Pseudo code

// 위의 그림과 함께 보면 이해하기 쉽다.
public static void mergeSort(int n, keytype[] S) {
	if(n > 1) { // 1개일 때는 할 것이 없음.
		const int h = floor(n/2), m = n-h; // 반으로 나눔.
		keytype[] U = new keytype[1...h];
		keytype[] V = new keytype[1...m];
		
		// Divide
		copy S[1:h] to U[1:h]; // 1부터 h까지
		copy S[h+1:n] to V[1:m]; // h+1부터 n(원래 배열의 크기)까지
		
		// Conquer
		mergeSort(h,U); // recursion
		mergeSort(m,V);
		
		// Combine 		
		merge(h,m,U,V,S);
	}
}

public static void merge(int h, int m, keytype[] U, 
													keytype[] V, keytype[] S) {

	index i = 1, j = 1, k = 1; // 첫 번째라고 1로 설정함.
	
	// 앞에서부터 끝(h, m)까지 갈 것임. 
	// U, V 배열 중 하나라도 빈 배열이 될 때까지 반복함.
	while(i <= h && i <= m) {
		if(U[i] < V[j]) {       // 더 작은 값을 S배열에 넣음.
			S[k] = U[i];
			i++;
		} 
		else {
			S[k] = V[j];
			j++;
		} 
		k++; // 더 작은 값을 S배열에 넣었다면, 다음 S배열 index로 이동.
	}
	// i > h : U배열을 모두 비움. V배열에 있는 값들을 S배열에 넣어야 함.
	if(i > h)
		copy V[j:m] to S[k:h+m];
	else 
		copy U[i:h] to S[k:h+m];
}
	

 

Best case for Merge sort

위의 코드를 참고하면서 보세요.

• Basic Operation: U배열의 요소와 V배열의 요소의 비교연산

Best case: 비교를 했을 때, U배열이나 V배열이 한 번에 다 들어가는 것

그래야 나머지 배열을 비교없이 통으로 복사할 수 있음.

⇒ B(h,m) = min(h,m)

(U배열의 크기와 V배열의 크기 중 더 작은 값이 Best case of time complexity)

 

Worst case for Merge sort

Worst case: 마지막 요소(103)을 제외하고 모든 요소를 비교 후에 S에 할당할 때.

⇒ W(h,m) = h + m - 1

⇒ merge(h,m,U,V,S)에 해당함.

(U배열의 크기 + V배열의 크기 - 마지막 요소)

총 Worst Case Time Complexity for Merge Sort

W(n) = W(h) + W(m) + W(h,m)

(W(h) : mergeSort(h,U), W(m) : mergeSort(m, V))

---

Quick sort

• Quick sort는 merge sort와 유사함.
  • 배열을 두 개로 나눔(상황에 따라 크기가 다름)
  • Subarray가 충분히 작을 때까지 recursion
• Merge sort과 다르게 3가지 부분으로 나눠짐.
  • Subarray 1
  • Pivot
  • Subarray 2
• Combine 단계가 없음.

 

Pseudo code

public static void quickSort(index low, index high) {
	index pivotPoint;  // pivot 요소의 index

	if(high > low) {   // Subarray의 크기가 1이 아닐 때
		pivotPoint = partition(low,high);

		// Subarray들에 recursion 적용 -> 계속 나눔.
		quickSort(low, pivotPoint - 1);
		quickSort(pivotPoint + 1, high);
	}
}

 

Partition Algorithm

Pivot요소의 최종 index는 어떻게 찾을까?

1. Local array 사용

• 하나의 새로운 배열(L)을 생성 후, pivot과 하나씩 비교함.
  • pivot보다 작은 요소는 j 인덱스를 사용해서 0부터 L에 채움.
  • pivot보다 큰 요소는 k 인덱스를 사용해서 n-1부터 L에 채움.

⇒ 추가 메모리 사용 그로 인한 수행시간 증가

 

1. In-place partition

추가 배열을 생성하지 않음.

해당 배열에서 바로 작업함.

 

 

[원리]

• Pivot보다 크면 pass
• Pivot보다 작으면 j 인덱스를 키우고 i 인덱스에 있는 요소와 swap
  • j 변수 선언 → pivot보다 작을 때, swap하기 위한 장치

 

Pseudo code for Partition

public static index partition(index low, index high) {
	index i, j, pivotPoint;
	keytype pivotItem;
	
	pivotItem = S[low];
	j = low;
	
	for(i = low + 1;i <= high;i++)
		if(S[i] < pivotItem) {
			exchange S[i] and S[++j];
		}
	
	pivotPoint = j;
	exchange S[low] and S[pivotPoint];
	return pivotPoint;
}

 

Every Case Time Complexity of Partition

• Basic Operation: comparison of S[i] with pivotItem

⇒ T(m) = m - 1

 

Worst Case Time Complexity of Quick Sort

• Worst case : 오름차순으로 정렬되어 있을 때피봇보다 큰 값은 Pass하기로 했음.민규 피드백 확인 후 반영
  • 1번 정렬 완료 → 12부터 27까지 subarray에서 피봇이 12가 됨.
  • 계속 반복 → 그래서 모든 비교를 더한 값이 최악의 경우의 수

 

• 피봇에 위치에 따라 달라짐.
• 피봇이 가장 작음.
• 첫 번째 요소를 피봇으로 정하고 오름차순으로 되어 있다고 가정해보자.

 

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

• n - 1: partition
• **T(0): left subarray *****
• T(n - 1): right subarray