퀵 정렬 (Quick Sort) - 정의

얼마나 빠르길래 이름 자체가 퀵 정렬일까?

 

지금까지 선택, 버블, 삽입 정렬들은 이름에서 어떻게 해결하는지 알 수 있었는데, 이건 유추가 불가능

 

퀵 정렬

- 피봇(Pivot)을 고르고, 피봇보다 작은 값은 피봇의 왼쪽, 큰 값을 피봇의 우측 이동해 정렬하는 알고리즘

 

- 분할 정복 방법

- 평균적으로 O(N*logN)을 보여주고 있으나, 최악의 경우 O(N^2)의 시간복잡도를 가짐.
- 최악의 경우는 이미 정렬 되어 있는 경우를 의미.

 

- 퀵 정렬 알고리즘은 코드를 따라가면서 직접 해보는게 좋다.

- 추가로 코드를 올릴 예정