[정렬] 퀵 vs 머지

1. 퀵 정렬

퀵 정렬(Quick Sort)은 기준값(피봇; Pivot)을 중심으로 자료의 왼쪽 부분집합과 오른쪽 부분집합으로 분할한다. 왼쪽 부분집합으로 기준값보다 작은 원소를 이동시키고, 오른쪽 부분집합으로 기준값보다 큰 원소를 이동시킨다.

 

(1) 왼쪽 끝에서 오른쪽으로 움직이면서 피봇보다 크거나 같은 원소를 찾아 L로 표시

(2) 오른쪽 끝에서 왼쪽으로 움직이며 피봇보다 작은 원소를 찾아 R로 표시

(3) L과 R을 서로 교환하고 (1)과 (2)를 반복 수행

(4) L과 R이 만나는 경우 멈추고 R과 피봇의 원소를 교환

(5) 피봇을 다시 정하고 (1) ~ (2) 반복

(6) 모든 부분집합의 크기가 1 이하가 되면 퀵 정렬 종료

 

## Pseudo Code
quickSort(a[], begin, end){
	if(m < n) then{
    	p <- partition(a, begin, end);
        quickSort(a[], begin, p-1);
        quickSort(a[], p+1, end);
    }
 }
 end quickSort()
 
 partition(a[], begin, end){
 	pivot <- (begin + end) / 2;
    L <- begin;
    R <- end;
    while(L<R) do {
    	while (a[L] < a[pivot] and L<R) do L++;
        while (a[R] >= a[pivot] and L<R) do R--;
        if (L < R) then {
        	temp <- a[L];
            a[L] <- a[R];
            a[R] <- temp;
        }
    }
    temp <- a[pivot];
    a[pivot] <- a[R];
    a[R] <- temp;
    return R;
}
end partition()

 

시간 복잡도

최선의 경우

• 피봇에 의한 원소들의 부분집합이 정확히 n/2개씩 2등분 되는 경우가 반복되는 경우
• 시간 복잡도 : O(nlogn)

최악의 경우

• 피봇에 의한 원소들의 부분집합이 1개와 n-1개로 분할되는 경우가 반복되는 경우
• 시간 복잡도 : O(n^2)

공간 복잡도

주어진 배열 내에서 교환을 하며 수행하므로 O(n) 이다.

 

---

 

2. 병합 정렬

 병합 정렬(Merge Sort) 은 여러 개의 정렬된 집합을 병합하여 하나의 정렬된 집합으로 만드는 정렬 방법이다. 자료를 부분집합으로 분할하고 부분집합에 대해 작업을 정복 하고 부분집합들을 다시 결합하는 분할과 정복(Divide and Conquer) 방법을 사용한다.

 

## Pseudo Code
mergeSort(a[], m, n){
	if (a[m:n]의 원소 수 > 1) then {
    	전체 집합을 부분집합 두 개로 분할;
    }
    mergeSort(a[], m, middle);
    mergeSort(a[], middle+1, n);
    merge(a[m:middle], a[middle+1:n]);
}
end mergeSort();

merge(a[m:middle], a[middle+1:n){
	j <- m;
    j <- middle + 1;
    k <- m;
    
    while(i<=middle and j<=n) do {
    	if(a[i] <= a[j]) then {
        	sorted[k] <- a[i];
            i <- i + 1;
        }
       	else {
        	sorted[k] <- a[j];
            j <- j + 1;
        }
        k <- k + 1;
    }
    if (i > middle) 두 번째 부분집합에 남아 있는 원소를 sorted에 복사;
    else 첫 번째 부분집합에 남아 있는 원소를 sorted에 복사;
}
end merge()

 

시간 복잡도

O(nlogn)

 

공간 복잡도

원래 자료 n개에 대해 정렬할 원소를 저장할 2*n개의 추가 공간 필요

 

---

퀵 소트 vs 머지 소트

퀵 소트 활용 케이스

• 메모리가 부족한 경우
• 배열이 이미 정렬/역정렬되어 있을 가능성이 없는 경우(퀵소트 최악의 경우)

머지 소트 활용 케이스

• 배열이 이미 정렬되어있을 가능성이 있는 경우
• 메모리가 충분한 경우

---

Reference

퀵 소트 시각화 : 퀵소트(quick sort) 알고리즘 (tistory.com)

퀵소트(quick sort) 알고리즘

퀵 소트 vs 머지 소트 : [자료구조] 퀵정렬 VS 병합정렬 (tistory.com)