정렬 개념 정리 - 퀵 정렬(Quick Sort), 합병 정렬(Merge Sort)

퀵 정렬(Quick Sort)

분할 정복(divide and conquer) 방법 을 통해 주어진 배열을 정렬한다.

1. 배열 가운데서 하나의 원소를 고른다. 이를 피벗(pivot) 이라고 한다.
2. 가장 왼쪽에 있는 수에 left마커, 오른쪽에 있는 수에 right마커를 표시한다.
3. 마커를 사용하여 일련의 작업을 재귀적으로 반복한다.
   left 마커를 오른쪽으로 이동 - 피벗 수 이상인 수에 도착하면 멈춤
   right 마커를 왼쪽으로 이동 - 피벗보다 작은 숫자에 도달하면 멈춤
   좌우 마커가 멈춘 시점에서 마커의 숫자를 교체함
   (right 마커가 움직여서 두 마커가 만날 때는 해당 원소와 피벗을 교체)
   두 마커가 있는 원소를 정렬 완료 상태로 둠
   피벗양쪽으로 같은 작업을 반복

 

퀵 정렬은 다음의 단계들로 이루어진다.

• 정복 (Conquer)

부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다.

public void quickSort(int[] array, int left, int right) {
    if(left >= right) return;
    
    // 분할 
    int pivot = partition(); 
    
    // 피벗은 제외한 2개의 부분 배열을 대상으로 순환 호출
    quickSort(array, left, pivot-1);  // 정복(Conquer)
    quickSort(array, pivot+1, right); // 정복(Conquer)
}

 

• 분할 (Divide)

입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열 (피벗을 중심으로 왼쪽 : 피벗보다 작은 요소들, 오른쪽 : 피벗보다 큰 요소들) 로 분할한다.

public int partition(int[] array, int left, int right) {
    /**
    // 최악의 경우, 개선 방법
    int mid = (left + right) / 2;
    swap(array, left, mid);
    */
    
    int pivot = array[left]; // 가장 왼쪽값을 피벗으로 설정
    int i = left, j = right;
    
    while(i < j) {
        while(pivot < array[j]) {
            j--;
        }
        while(i < j && pivot >= array[i]){
            i++;
        }
        swap(array, i, j);
    }
    array[left] = array[i];
    array[i] = pivot;
    
    return i;
}

 

시간복잡도 : O(n^2) (최악) O(nlog₂n) (평균, 최선)

공간복잡도 : O(n)

장점: 

• 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환할 뿐만 아니라, 한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문에, 시간 복잡도가 O(nlog₂n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
• 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않는다.

단점: 

• 불안정 정렬(Unstable Sort) 이다.
• 정렬된 배열에 대해서는 Quick Sort의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.(오름차순/내림차순)

 

---

 

합병 정렬(Merge Sort)

큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식

요소를 쪼갠 후, 다시 합병시키면서 정렬해나가는 방식으로, 쪼개는 방식은 퀵정렬과 유사

 

• ‘존 폰 노이만(John von Neumann)’이 제안한 방법
  일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다.
  분할 정복(divide and conquer) 방법
  문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
  분할 정복 방법은 대개 순환 호출을 이용하여 구현한다.
• 과정 설명
  리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 
  그렇지 않은 경우에는 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.
  각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.
  두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.
  

 

• mergeSort

public void mergeSort(int[] array, int left, int right) {
    
    if(left < right) {
        int mid = (left + right) / 2;
        
        mergeSort(array, left, mid);
        mergeSort(array, mid+1, right);
        merge(array, left, mid, right);
    }
    
}

정렬 로직에 있어서 merge() 메소드가 핵심

 

• merge()

public static void merge(int[] array, int left, int mid, int right) {
    int[] L = Arrays.copyOfRange(array, left, mid + 1);
    int[] R = Arrays.copyOfRange(array, mid + 1, right + 1);
    
    int i = 0, j = 0, k = left;
    int ll = L.length, rl = R.length;
    
    while(i < ll && j < rl) {
        if(L[i] <= R[j]) {
            array[k] = L[i++];
        }
        else {
            array[k] = R[j++];
        }
        k++;
    }
    
    // remain
    while(i < ll) {
        array[k++] = L[i++];
    }
    while(j < rl) {
        array[k++] = R[j++];
    }
}

이미 합병의 대상이 되는 두 영역이 각 영역에 대해서 정렬이 되어있기 때문에 단순히 두 배열을 순차적으로 비교하면서 정렬할 수가 있다.

 

시간복잡도 : O(nlog_2 n) 

공간복잡도 : O (n )

장점 : 

• 안정 정렬 방법
  데이터의 분포에 영향을 덜 받는다. 즉, 입력 데이터가 무엇이든 간에 정렬되는 시간은 동일하다. (O(nlog₂n)로 동일)
• 순차적인 비교로 정렬을 진행하므로, 만약 레코드를 연결 리스트(Linked List)로 구성하면, 링크 인덱스만 변경되므로 데이터의 이동은 무시할 수 있을 정도로 작아진다.
  제자리 정렬(in-place sorting)로 구현할 수 있다.
• 따라서 크기가 큰 레코드를 정렬할 경우에 연결 리스트를 사용한다면, 합병 정렬은 퀵 정렬을 포함한 다른 어떤 졍렬 방법보다 효율적이다.

단점 :

• 만약 레코드를 배열(Array)로 구성하면, 임시 배열이 필요하다.
  제자리 정렬(in-place sorting)이 아니다.
• 레코드들의 크기가 큰 경우에는 이동 횟수가 많으므로 매우 큰 시간 낭비를 초래한다.

 

 

퀵소트와의 차이점

퀵정렬 : 우선 피벗을 통해 정렬(partition) → 영역을 쪼갬(quickSort)

합병정렬 : 영역을 쪼갤 수 있을 만큼 쪼갬(mergeSort) → 정렬(merge)

 

 

 

출처:

https://gmlwjd9405.github.io/2018/05/08/algorithm-merge-sort.html

https://gyoogle.dev/blog/