퀵 정렬 알고리즘(Quick Sort Algorithm)

 퀵 정렬 알고리즘은 현재 사용되고 있는 정렬 알고리즘 중에서 가장 빠르다고 알려진 알고리즘입니다. 퀵 정렬 알고리즘은 1960년 찰스 앤터니 리처드 호어가 소개한 이후 많은 사람에 의해 수정, 보완되어 만들어진 알고리즘입니다. 빠르기도 하고 구현도 쉽고 메모리 사용량도 적어서 정렬 알고리즘은 대부분 이 알고리즘을 사용합니다.

 대부분의 정렬 알고리즘은 평균적으로 최소 2번의 반복 실행을 통해 데이터를 정렬합니다. 하지만 퀵 정렬 알고리즘은 반복 실행은 1번만 한다는 점에서 큰 차이를 보입니다. 퀵 정렬 알고리즘의 방식은 이렇습니다.

1. 정렬할 기준이 되는 데이터 하나를 선택합니다. 이 기준 데이터를 피벗(pivot)이라고 합니다.
2. 기준 데이터를 기준으로 왼쪽에는 기준 데이터보다 작은 데이터, 오른쪽에는 큰 데이터로 가릅니다.
3. 갈랐던 각각의 데이터도 1,2번 과정을 반복합니다.
4. 위 과정을 정렬될 때까지 반복합니다.

 퀵 정렬의 시간복잡도는 최악의 경우에는 O(N^2)번의 비교를 수행하고, 평균적으로 O(NlogN)번의 비교를 수행합니다. 퀵 정렬의 내부 루프는 대부분의 컴퓨터 아키텍처에서 효율적으로 작동하도록 설계되어 있고, 정렬할 때 제곱 시간이 걸릴 확률이 거의 없도록 알고리즘을 설계할 수 있기 때문에 같은 시간이 걸리는 다른 알고리즘에 비해 훨씬 빠르게 동작합니다.

다음은 퀵 정렬의 소스코드입니다.