퀵 정렬은 전쟁 전략중의 하나인 분할 정복에 기반한 알고리즘입니다.
분할 정복 전략은 적군의 전체를 공략하는 대신, 전체를 구성하는 구성 요소들을 나누어 잘개 쪼개진 적을 공략하는 전법입니다.
퀵 정렬은 아래과정을 거칩니다.
1. 데이터 집합 내에서 임의의 기준 요소를 선택하고, 기준 요소보다 작은 요소들은 순서에 관계없이 기준 요소의 왼편에, 큰 값은 오른편에 위치시킵니다.
2. 이렇게 나눈 데이터 집합들을 다시 1에서와 같이 임의의 기준 요소를 선택 후 같은 방법으로 데이터 집합을 분할합니다.
3. 1, 2의 과정을 더 이상 데이터 집합을 나눌 수 없을 때까지 반복하면 정렬된 데이터 집합을 얻게 됩니다.
[0, 1, 2, 2, 3, 5, 6, 50]
위와 같은 최종 결과값이 나오게 됩니다.
퀵 정렬의 성능은 퀵 정렬의 재귀 호출 깊이, 데이터 집합을 나누기 위해 필요한 비교 횟수를 근거로 성능을 분석 할 수 있습니다.
퀵 정렬은 데이터 집합이 어떻게 정렬되어 있는지가 성능을 좌우하는 알고리즘입니다. 데이터가 미리 정렬되어 있거나 또는 역순으로 정렬되어 있는 경우에는 최악의 성능을 보입니다. 하지만 데이터 요소들이 이리저리 흩어져 있는 경우에는 최고의 성능을 자랑합니다.