알고리즘> 고급> 분할정복법> 퀵정렬

분할정복법이란 위에서 아래로 진행하는 방법이다.

즉 재귀용법을 이용한 것.

퀵정렬은 기준점을 잡아서 그것보다 크면 오른쪽으로 작으면 아래로 배치하는 정렬법이다

이것을 반복하여 재귀호출하면 된다..

 

 

 

일반 버전

 

 

 

경량화 버전

 

 

 

시간복잡도는 

O(N)*O(logN) = O(NlogN) 이 되는데 왜그럴까??

 

이진트리로 나눈다고했을 때 처음에 처리를 하지 않은 상태는 한 덩어리이다.

1단계로 나누면 양 끝으로 나뉘어져서 두 개의 덩어리가 된다..

2단계로 넘어가면 4개의 덩어리가 생기게 된다...

3단계는 8개 덩어리..

이걸 반복해서 쪼개지지 않은 상태까지 가려면 몇 단계가 필요할까?

x 단계를 실시하여 n개의 덩어리가 된다고 한다면

2^x = n  이 되겠다..

여기서 밑이 2인 로그를 곱해버리면

x = logn 이 될것이다..

n개의 덩아리와 N개의 데이터가 일치하는 순간이 바로 더 이상 쪼개지지 않은 상태가 될 것이다

즉 x = logN이다...

 

단계를 만드는데 logN이고

각 단계마다 N개의 데이터를 검사를 해야하므로

logN * N 이 되는것이다..

 

 

하지만 이건 가장 최선의 상황에 있을 때의 가정이다..

x단계를 거친다고 2^x 덩어리가 생기게 하려면 

가장 최선의 상황인 항상 중앙값을 기준점으로 하여 조졌을 경우에 생기는 것이다.

예를 들어서 10개의 데이터값에서 운이 나빠 가장 작은 값을 항상 기준점을 삼는다고 생각해보자...

그러면 아까 위에서와는 다르게 3단계에서 4개의 덩어리가 생긴다...

즉 n개의 데이터가 있을 경우 n-1 단계를 거쳐야 더이상 쪼개지지 않은 상태..

각 단계에서 어차피 검사는 모두 해야 하는 n번

총 N(N-1) 시간 복잡도를 가지는데 N^2이 가장 크니까 

O(N^2)이 최악의 상황에서 시간 복잡도이다..

 

여기서 확률을 이용해서 더 접근할 수 있겠지만 지금은 콤퓨타 알고리즘 시간이므로 여기까지..