고급정렬 알고리즘(4) - 병합, 힙, 퀵 정렬 비교분석

기초적인 정렬(선택, 버블, 삽입)외에 고급정렬인 병합, 힙, 퀵 정렬에 대해서 알아보았다.

이제 이 3개의 고급정렬의 각 수행시간을 최선, 평균, 최악의 경우에 따라서 어떠한 특징이 있는지 살펴보자.

먼저, 3가지 정렬의 특징은

1) 병합정렬 : 분할, 합병인 분할정복을 이용한 정렬방식

▶ 주어진 값에 상관없이 분할하고 합병하므로 항상 일정한 수행시간이 소요된다.

2) 힙 정렬 : 히프 구조를 이용한 정렬방식

▶ (1)히프를 만든 뒤, (2)루트노드인 제일 작은값을 맨 뒤의 값과 교환을 하는 반복을 통해서 정렬이 되어간다. 여기서 "이미 히프구조로 되어있다면 최선의 경우가 아닐까?" 라고 생각할 수 있지만, (2)정렬과정(루트 노드와 맨 뒤의 값과 교환하는 것)에서 히프구조가 깨져서 재귀를 통해 히프를 재구성하는 과정이 전체 수행시간에 더 큰 부분을 차지하므로 (1)처음에 히프를 만들어 주는 과정은 수행시간에 크게 영향을 주지는 않는다. 그러므로 항상 일정한 수행시간이 소요되는 것을 알 수 있다.

3) 퀵 정렬 : 맨 끝의 값을 기준원소로 전체와의 비교를 반복을 통한 정렬방식

▶ 기준원소를 잡고 전체원소와 크기비교를 통해 전반, 후반부로 나누고 또 다시 기준원소를 각 부의 끝을 기준원소로 각 부의 전체와 크기비교를 통해 전반, 후반으로 나누는 과정으 을 반복해서 정렬이 된다. 이 과정에서 두 가지 경우가 수행시간에 영향을 줄 수 있다.

 (1) 맨 끝의 기준원소가 가장 큰 값일 경우 : 후반부는 하나도 존재하지 않으며 단 하나의 원소, 기준원소만 정렬이 된 상태이다. 

 (2) 맨 끝의 기준원소가 가장 작은 값일 경우 : 전반부는 하나도 없으며 단 하나의 원소, 기

준원소만 정렬이 된 상태이다.  

ex) 5, 4, 2, 1, 7의 경우를 살펴보자 

1) 기준원소 7일 때 :

7 : 가장 큰 수

2) 기준원소 1일 때 :

1 : 가장 작은 수

3) 기준원소 5일 때 :

5 : 가장 큰 수

4) 기준원소 2일 때 :

2 : 가장 작은 수

5) 기준원소 4일 때 : 

전반/후반 부의 갯수 : 0

      
6) 정렬 완료. 

정렬완료.

이처럼 각 기준 원소들이 가장 작은 값 혹은 가장 큰 값이 될 경우 변화가 거의 없으며, 전반/후반 부 또한 나눌 수 없다. 이러면 퀵 정렬의 특징이 거의 사라졌다 봐도 무방하다.

즉, 퀵 정렬의 최악의 경우는 기준원소가 가장 큰값 혹은 가장 작은 값이 되는 경우이다.



고급정렬 수행시간은, 다음과 같이 정리 할 수 있다.