[알고리즘] 병합 정렬과 퀵 정렬

4. 병합 정렬

 

병합 정렬은 분할 정복법에 해당하며, 하나의 큰 문제를 여러 개의 작은 문제로 쪼개 각각 해결 후 결과를 모아 원래의 문제를 해결하는 방법입니다.

 

public class MergeSort {

	private static int[] sorted; // 합치는 과정에서 정렬하여 원소를 담을 임시 배열
    
    public static void mergeSort(int[] a) {
    	sorted = new int[a.length];
        mergeSort(a, 0, a.length-1);
        sorted = null;
    }

	private static void mergeSort(int[] a, int left, int right) {
    	if(left == right) return;
        
        int mid = (left + right) / 2;
        
        mergeSort(a, left, mid);
        mergeSort(a, mid+1, right);
        
        merge(a, left, mid, right); // 병합 작업
    }
    
    /**
    *
    * @param a 정렬할 배열
    * @param left 배열의 시작점
    * @param mid 배열의 중간점
    * @param right 배열의 끝 점
    */
    private static void merge(int[] a, int left, int mid, int right) {
    	int l = left;
        int r = mid+1;
        int idx = left;
        
        while(l <= mid && r <= right) {
        	// 왼쪽 부분 리스트 l번째 원소가 오른쪽 부분 리스트 r번째 원소보다 작거나 같은 경우
            // 왼쪽 l번째 원소를 새 배열에 넣고 l과 idx를 1 증가시킨다.
            if(a[l] <= a[r]) {
            	sorted[idx] = a[l];
                l++;
                idx++;
            }
            // 오른쪽 부분 리스트 r번째 원소가 왼쪽 부분 리스트 l번째보다 작거나 같은 경우
            // 오른쪽 r번째 원소를 새 배열에 넣고 r과 idx를 1 증가시킨다.
            else {
            	sorted[idx] = a[r];
                r++;
                idx++;
            }
        }
        
        // 왼쪽 부분 리스트가 먼저 모두 새 배열에 채워졌을 경우 (l > mid)
        // 오른쪽 부분 리스트의 나머지 원소들을 새 배열에 채운다.
        if(l > mid) {
        	while (r <= right) {
            	sorted[idx] = a[r];
                r++;
                idx++;
            }
        }
        // 오른쪽 부분 리스트가 먼저 모두 새 배열에 채워졌을 경우 (r > right)
        // 왼쪽 부분 리스트의 나머지 원소들을 새 배열에 채운다.
        else {
        	while (l <= mid) {
            	sorted[idx] = a[l];
                l++;
                idx++;
            }
        }
        
        for(int i = left; i <= right; i++) {
        	a[i] = sorted[i];
        }
    }
}

 

같은 방식으로 계속 반복하여 병합하고 있기 때문에 병합 정렬은 보통 재귀함수로 구현합니다. 또한 병합 정렬은 항상 O(n log n)의 시간 복잡도를 가지기 때문에 효율적입니다. 그러나 원소의 개수만큼 리스트를 쪼개고 따로 저장해야 하기 때문에 O(n)의 공간 복잡도를 가집니다. 즉, 메모리를 소모해 수행 속도를 높이는 경우라고 볼 수 있습니다.

---

5. 퀵 정렬

 

퀵 정렬 또한 병합 정렬과 마찬가지로 분할 정복을 사용하는 정렬 방법입니다. 병합 정렬이 분할 단계에서 아무것도 하지 않고 병합 단계에서 정렬을 수행한다면, 퀵 정렬은 분할 단계에서 중요한 작업들을 수행하고 병합 시에는 아무 것도 하지 않는다는 점입니다.

 

퀵 정렬의 메커니즘은 다음과 같습니다.

 

하나의 리스트를 피벗(pivot)을 기준으로 두 개의 부분리스트로 나누어 하나는 피벗보다 작은 값들의 부분 리스트, 다른 하나는 피벗보다 큰 값들의 부분 리스트로 정렬한 다음, 각 부분 리스트에 대해 다시 재귀적으로 수행하여 정렬하는 방법입니다.

 

[ 중간 피벗 선택 방식 ]

public class QuckSort {

	public static void sort(int[] a) {
    	m_pivot_sort(a, 
    }

	/**
    * 중간 피벗 선택 방식
    * @param a 정렬할 배열
    * @param lo 현재 부분 배열의 왼쪽
    * @param hi 현재 부분 배열의 오른쪽
    */
    private static void m_pivot_sort(int[] a, int lo, int hi) {
    	// lo가 hi보다 크거나 같다면 정렬할 원소가
        // 1개 이하이므로 정렬하지 않고 return 한다.
    	if(lo >= hi) {
        	return;
        }
        
        int pivot = partition(a, lo, hi);
        
        m_pivot_sort(a, lo, pivot);
        m_pivot_sort(a, pivot + 1, hi);
    }
	
    /**
    * pivot을 기준으로 파티션을 나누기 위한 약한 정렬 메서드
    *
    * @param a 정렬할 배열
    * @param left 현재 배열의 가장 왼쪽
    * @param right 현재 배열의 가장 오른쪽
    * @return 최종적으로 위치할 피벗의 위치(hi)를 반환
    */
    private static int partition(int[] a, int left, int right) {
    	
        int lo = left - 1;
        int hi = right + 1;
        int pivot = a[(left + right) / 2];
        
        while(true) {
        
        	// 1 증가시킨 lo 위치의 요소가 pivot보다 큰 요소를 찾을 때까지 반복
        	do {
            	lo++;
            } while (a[lo] < pivot);
            
            // 1 감소시킨 hi 위치가 lo보다 크거나 같은 위치이면서
            // hi 위치의 요소가 pivot보다 작은 요소를 찾을 때까지 반복
            do {
            	hi--;
            } while (a[hi] > pivot && lo <= hi);
            
            // 만약 hi가 lo보다 크지 않다면 swap 하지 않고 hi를 리턴한다.
            if (lo >= hi) {
            	return hi;
            }
            
            // 교환될 두 요소를 찾으면 두 요소를 바꾼다.
            swap(a, lo, hi);
        }
    }
    
    private static void swap(int[] a, int i, int j) {
    	int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}

 

퀵 정렬은 읽어보고 직접 코드를 작성해봐도 난해한 점이 많아 조금 더 시간을 들여 이해해봐야겠다...

---

참고 출처

• https://st-lab.tistory.com/233
• https://evan-moon.github.io/2018/10/13/sort-algorithm/#%EC%84%A0%ED%83%9D%EC%A0%95%EB%A0%ACselection-sort
• https://st-lab.tistory.com/250