알고리즘 4(퀵 정렬)

안녕하세요!

 

게임개발자가 되기위해 공부하고 있는 구구입니다.

오늘은 알고리즘의 퀵 정렬에 대해 알아보도록 하겠습니다.

---

• 퀵 정렬

- 피봇을 기준으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰 값을 지닌 데이터는 뒤로 보내서 작은값을 가지는

  데이터와 큰값을 가지는 데이터로 분리해 나가며 정렬하는 방식

 

1. 분할 정복 알고리즘
2. 일반적으로 빠른 알고리즘

 

 

• 퀵 정렬의 특징

- 속도가 빠름

- 정렬된 리스트에 대해서는 수행시간이 더 오래 걸림

 

 

• 시간 복잡도

- O(n^2)

 

최악의 경우를 고려해보면 '분할 기준이 매번 제일 크거나 제일 작은값인 경우' 입니다.

 

따라서 1번부터 n-1번까지 적어도 한번씩은 비교하게 됩니다.

그래서 최악의 경우 n의 2차식꼴이 나옵니다.

 

- O(n logn)

 

위처럼 최악의 경우는 n의 2차식이 나오지만 평균적인 경우는 다른 시간복잡도가 나옵니다.

그림의 경우처럼 피봇에 의해 반반씩 나눠지는 케이스인 경우 매 분할마다 정렬해야할 데이터가 반씩 줄어듭니다.

따라서 logn 만큼의 분할이 발생하고 각 분할 마다 최대 n번의 데이터 비교가 발생합니다.

그러므로 logn(분할깊이) * n(비교횟수) = n logn 의 시간복잡도를 가집니다.

 

 

 

 

 

 

FuncPartition이라는 함수에서 정렬이 이루어지는데 피봇값이 30일때 어떻게 바뀌는지를 주석으로 적어놨습니다.

nLow의 데이터값이 피봇보다 크거나 같을때까지 nLow값을 늘리고

nHigh의 데이터값이 피봇보다 작거나 같을때 까지 nHigh값을 줄입니다.

 

마지막에는 피봇값과 nLow의 데이터값을 교환함으로서 피봇값의 위치를 확정지어 줍니다.

 

 

 

 

 

 

 

 

오늘은 여기까지 하도록 하겠습니다.