병합식 퀵 정렬

병합식 퀵 정렬 알고리즘에 대해 포스팅합니다.

이를 이해하려면 먼저 퀵 정렬이라는 알고리즘에 대해 이해할 필요가 있습니다.

우선 우리가 흔히 알고 있는 퀵 정렬은 버블 정렬처럼 데이터의 값을 서로 바꾸는 '교환 정렬' 방식입니다. 여기서는 교환식 퀵 정렬이라고 부르겠습니다.

먼저 교환식 퀵 정렬이 어떻게 돌아가는지 보자면,

[4, 6, 1, 7, 8, 2, 3, 5]

이렇게 뒤죽박죽이 된 배열이 있다고 했을 때, 맨 앞의 4를 기준값으로 잡은 후 한 번 돌려 봅시다.

[4, 6, 1, 7, 8, 2, 3, 5]
 P                 >

[3, 6, 1, 7, 8, 2, 4, 5]
    <              P

[3, 4, 1, 7, 8, 2, 6, 5]
    P           >

[3, 2, 1, 7, 8, 4, 6, 5]
          <     P

[3, 2, 1, 4, 8, 7, 6, 5]
          P

이와 같이 앞뒤로 하나씩 번갈아가며 기준값보다 작은 값이 뒤에 있다면 그 값과 기준값의 위치를 바꾸고 반대로 기준값보다 큰 값이 앞에 있다면 또 그 값과 기준값의 위치를 바꾸고 이렇게 계속 반복하다 보면 앞에는 기준값보다 작은 값만, 뒤에는 기준값보다 큰 값만 있게 됩니다. 그리고 기준값의 앞뒤로 재귀호출을 하면,

[3, 2, 1, 4, 8, 7, 6, 5]
 P     >  V

[1, 2, 3, 4, 8, 7, 6, 5]
       P  V

...

[1, 2, 3, 4, 8, 7, 6, 5]
 V  V  V  V  P        >

[1, 2, 3, 4, 5, 7, 6, 8]
 V  V  V  V           P

...

[1, 2, 3, 4, 5, 7, 6, 8]
 V  V  V  V  V  P  >  V

[1, 2, 3, 4, 5, 6, 7, 8]
 V  V  V  V  V     P  V

[1, 2, 3, 4, 5, 6, 7, 8]
 V  V  V  V  V  V  V  V

이렇게 종국에는 빠른 속도로 완전히 정렬됩니다.

그런데 이 방식에는 문제가 있습니다. 불안정 정렬이라는 것입니다. .sort 메소드로 안정 정렬 구현하기 포스트에 설명한 것처럼, 정렬 키 값이 같은 데이터끼리 정렬 후 순서가 서로 바뀔 가능성이 있는 정렬을 불안정 정렬이라고 합니다.

신비, 1998년생
예린, 1996년생
소원, 1995년생
은하, 1997년생
엄지, 1998년생
유주, 1997년생

이 데이터를 생년 순으로 정렬한다고 했을 때, 저 앞의 교환식 퀵 정렬 알고리즘을 적용하면,

소원, 1995년생
예린, 1996년생
유주, 1997년생
은하, 1997년생
엄지, 1998년생
신비, 1998년생

이런 결과가 나옵니다. 생년이 같은 은하와 유주, 신비와 엄지의 순서가 서로 뒤바뀌어 있습니다.

이렇듯 교환식 퀵 정렬은 불안정한 정렬입니다.

그런데, 퀵 정렬을 교환식이 아닌 병합 정렬처럼 병합식으로 구현하면 과연 어떻게 될까요? 저 맨 앞의 예시를 보면,

[4, 6, 1, 7, 8, 2, 3, 5]
 P

[1, 2, 3, 4, 6, 7, 8, 5]
 <  <  <  P  >  >  >  >

...

[1, 2, 3, 4, 6, 7, 8, 5]
 V  V  V  V  P

[1, 2, 3, 4, 5, 6, 7, 8]
 V  V  V  V  <  P  >  >

...

[1, 2, 3, 4, 5, 6, 7, 8]
 V  V  V  V  V  V  V  V

교환 없이 배열을 3개 만들어서 아예 처음부터 순서대로 훑으며 기준값보다 작은 값, 기준값과 같은 값, 기준값보다 큰 값 이렇게 분류해 놓고 합치는 과정에서 기준값보다 작은 값 배열과 기준값보다 큰 값 배열에 재귀호출을 합니다.

저 앞의 여자친구 멤버들을 생년 순으로 정렬할 때 병합식 퀵 정렬 알고리즘을 사용해 봅시다.

신비, 1998년생  P
예린, 1996년생  <
소원, 1995년생  <
은하, 1997년생  <
엄지, 1998년생  =
유주, 1997년생  <

예린, 1996년생  P
소원, 1995년생  <
은하, 1997년생  >
유주, 1997년생  >
신비, 1998년생  OK
엄지, 1998년생  OK

소원, 1995년생  pass
예린, 1996년생  OK
은하, 1997년생  P
유주, 1997년생  =
신비, 1998년생  OK
엄지, 1998년생  OK

소원, 1995년생  OK
예린, 1996년생  OK
은하, 1997년생  OK
유주, 1997년생  OK
신비, 1998년생  OK
엄지, 1998년생  OK

같은 생년의 멤버끼리 서로 순서가 바뀌지 않고 정렬되었습니다.

병합식 퀵 정렬을 쓰면 이와 같이 퀵 정렬의 불안정성을 해소할 수 있습니다.
또한, 병합식 퀵 정렬은 병합 정렬의 단점도 해소하였다고 볼 수 있습니다. 병합 정렬은 데이터들을 둘로 나눠나가는 특성상 정렬할 데이터의 수가 매우 많아지면 현저한 효율 저하가 발생하지만 퀵 정렬은 데이터의 수가 많아져도 심각한 효율 저하가 발생하지 않습니다.

다음에는 병합식 퀵 정렬을 실제로 코딩하여 구현해 보겠습니다.