[알고리즘] 좋은 성능의 정렬 - 퀵, 병합 정렬

퀵 정렬

평균적으로 가장 좋은 성능을 가졌다. 기준 원소를 잡고 기준 원소를 기준으로 양쪽으로 재배치하면서 정렬한다. 퀵정렬 또한 Divide-and-conquer을 이용한다.

​

분할 : 배열 A [p.. r]을 두 개의 부분 배열 A [p.. q - 1], A [q + 1.. r]로 분할한다. 전자는 A [q]보다 작거나 같은 원소를, 후자는 A [q]보다 크거나 같은 원소를 배치한다.

​

정복 : 퀵 정렬을 재귀 호출해서 두 부분 배열을 퀵정렬한다.

​

결합 : 부분 배열이 이미 정렬되어 있으므로 저절로 합쳐져 있다.

 

기본적인 알고리즘은 이렇고 자세한 구현은 코드로 보자.

QuickSort(A, p, r){
  if(p < r)
  q = Partition(A, p, r)
  QUICKSORT(A, p, q-1)
  QUICKSORT(A, q+1, r)
}

이때PARTITION은 쉽게 말해 배열 A의 원소들을 A [r]을 기준으로 양쪽으로 재배치하고 A [r]의 위치를 리턴하는 함수이다.

Partition(A, p, r){
  x = A[r]
  i = p - 1
  for(j = p; j < r; j++){
    if(A[j] <= x){
      //기준원소보다 작으므로 p~i 구간에 들어가야한다. 따라서 기준원소보다 작은 배열이 한 칸 늘었으므로 i를 늘려준다.
      i++
      //A[i]는 기준원소보다 작은 배열의 마지막 부분인데, 위에서 ++을 해줬으므로 기준원소보다 큰 배열의 시작 부분이다.
      //A[j]는 p~i구간에 넣어야하는 원소이므로 둘이 바꿔준다.
      SWAP(A[i], A[j])
    }
  }
  //마지막으로 기준원소는 기준원소보다 작은 원소의 다음칸, 즉 i+1에 넣어준다.
  SWAP(A[i+1], A[r])
  return i + 1
}

x는 기준 원소이다. i는 x보다 작은 원소들을 분할한 배열의 끝을 가리키는 포인터이다. 즉, p~i까지는 x보다 작은 것들로 분할되어 있다.

또 j는 x보다 큰 원소들을 분할한 배열의 끝 다음칸을 가리키는 포인터이다. i~j는 x보다 큰 것들로 분할되어 있다. 따라서 j~r까지는 아직 분할하지 않은 공간이다.

​

시간복잡도는 분할하는 모습을 마치 트리처럼 생각하면 편하다.

​

평균 수행 시간 : 가장 이상적인 경우로, 분할이 항상 반반씩 균등될 때 분할되는 모습이 완전 이진트리이므로 θ(n log n)이다.

​

최악의 경우 수행 시간 : 이미 정렬이 되어 한 쪽에 다 몰리도록 분할될 때 한쪽으로 치우쳐진 트리의 모습이므로 θ(n^2)이다.

---

병합 정렬

배열을 원소를 하나씩만 가진 배열이 될 때까지 모두 분해하고 차례로 병합시켜 나가면서 정렬하는 방법이다.

mergeSort(A[], p, r){
  if(p<r){
  q = (p+r)/2
  mergeSort(A, p, q)
  mergeSort(A, q+1, r)
  //원소가 하나씩으로 잘게 조갠 후 다시 정렬하면서 병합한다.
  merge(p, r)
  }
}

merge는 정렬되어있는 배열 A [p... q]와 A [q+1... r]을 병합하여 A [p... r]을 만든다.

merge(start, end){
  mid = (start+end)/2
  i = left
  j = mid+1
  res_index = left
  while(i<=mid && j<=right){
    if(arr[i] > arr[j])
      //arr[i]가 더 크면 arr[j]를 먼저 결과에 넣는다.
      result[res_index++] = arr[j++]
    else
      result[res_index++] = arr[i++]
  }
  //배열을 일단 탐색후 왼쪽 리스트나 오른쪽 리스트에 남은 값이 있으면 그냥 넣어주면 끝이다.
  if(i > mid){
    while(j <= right){
      result[res_index++] = arr[j++]
    }
  }else{
    while(i <= mid){
    result[res_index++] = arr[i++]
    }
  }
}

i부터는 정렬되지않은 왼쪽 배열이고, j부터는 정렬되지 않은 오른쪽 배열이다. 그 둘을 병합하면 된다.

 

병합 정렬은 병합하는데 log n의 시간이 들고, 총 n번 병합하므로 시간 복잡도는 O(n log n)이다. 퀵정렬에 비해 평균적으로 더 좋은 성능을 자랑하지만 데이터의 크기가 큰 경우 이동에 많은 시간이 걸리고 추가 공간을 사용한다는 단점이 있다.