알고리즘 공부 <5> - 퀵 정렬

퀵 정렬

이번 글에서는 퀵 정렬에 대해서 알아 봅시다. 앞서 우리는 병합 정렬에 대해서 공부했다. (http://history1994.tistory.com/28?category=670299) 

퀵 정렬은 이와 비슷하면서 다르다

한 번 살펴보면

Divide , Conquer  과정에서 이미 정렬 되어져 생기기 때문에 따로 Combine 과정은 필요로 하지 않는다.

그리고 PARTITION 과정을 통해 DIVIDE 과정을 수행하게 된다.

즉,

이러한 순서대로 퀵 정렬은 이루어진다. PARTITION 과정부터 한번 살펴 보자.

PARTITION과정으로 인해 부분 배열로 재구성 되어지고  'PIVOT' 이라는 인덱스가 리턴 되어진다.

과정을 보면

이러한 과정을 거치게 된다.

이를 예로 들자면

a ~ i 과정을 거쳐 pivot의 위치를 찾는 것이다. 즉 이 과정을 도중을 살펴보면 나눠지는 4가지 영역을 확인할 수 있는데,

이러한 PARTITION 과정을 재귀적으로 반복하게 된다.

---

퀵 정렬의 대략적인 과정을 알았으니 이 과정의 시간 복잡도와 빅오를 구해보자.

파티션은 사실 직관적으로 o(n) 인 것을 알 수 있다. 처음부터 마지막 인덱스를 확인 하며 마지막 인덱스 - 1  까지 가기 때문이다.

그렇다면 퀵정렬은 어떻게 될지 한번 따져보자

퀵정렬의 시간 복잡도는 위의 식을 보면 알 수 있듯이 PARTITION 과정에 의존적이다. 이 과정을 거쳐 PIVOT의 위치가 어디에 놓이는지에 따라 다르다.

PARTITION 과정을 거친후 나뉘어진 두 서브배열이  '불균형' 상태일 때 WORST CASE가 된다. 불균형 상태란  한쪽은 서브배열의 개수가 0개 이고 나머지 서브 배열이 N-1 개가 되는것을 말한다.

이런 상황에서 시간 복잡도 는 

이 된다.

그리고 뷸균형 상태가 아닐 떄는

이 된다.

이는 반 (N/2) 으로 나뉘어지지  않는 상황에서도 빅오는 같다

오늘은 퀵정렬에 대해서 간단하게 공부 해보았다. 

다음에 또 다른 정렬과정을 가져와서 공부 해보자