퀵정렬(Quick Sort)

퀵정렬은 특정한 배열이 있을 때 그 배열의 원소들을 반복적으로 분할하는 것이다. 

 

즉, 퀵정렬은 특정한 피벗값(기준값)을 기준으로 왼쪽과 오른쪽으로 나누기 때문에 '분할 정복'이라고도 부른다.

 

[퀵 정렬의 시간 복잡도]

퀵 정렬의 시간 복잡도는 O(N * logN) 이다.

예를 들어, 1 2 3 4 5 6 7 8 9 10 와 같이 10개 수가 존재할 때 선택 정렬을 사용하게 되면 O(N^2) 이기 때문에

10 * 10 = 100 이 나온다.

하지만, 퀵 정렬을 사용하면 1 2 3 4 5 와 6 7 8 9 10 으로 분할하여서 N^2 이라고 했을 때 (5 * 5) + (5 * 5) = 50 이

나오기 때문에 결과적으로 훨씬 적은 수만큼 연산을 수행하게 된다. 

이렇게 수를 반으로 나누는 과정은 2씩 계속 나눈다는 점에서 logN이라고 할 수 있다. 이러한 원리에서 데이터의 갯수가

N개이고 반씩 나누어 수행되기 때문에 N * logN이 성립된다.

 

하지만 퀵 정렬은 최악의 경우에 N^2 까지 나올 수 있다. 즉, 퀵 정렬의 최악 시간 복잡도는 O(N^2) 이다.

[소감]

데이터의 개수가 굉장히 컸을 때 선택 정렬, 버블 정렬, 삽입 정렬을 사용하는 것보다 퀵 정렬을 통해 분할 하면서

 

정렬을 수행하면 훨씬 더 빠르게 처리될 수 있을 것 같다고 생각된다.

---

출처

https://blog.naver.com/ndb796/221226813382

5. 퀵 정렬(Quick Sort)