C로 구현한 Quick Sort (퀵 정렬)

퀵 소트는 다른 정렬 알고리즘에 비해 상대적으로 속도가 빠르고 큰 배열에 대해서도 잘 동작하기 때문에 가장 널리 사용되는 정렬 알고리즘이다.

큰 배열을 일정한 기준값을 경계로 하여 기준값보다 큰 값들과 작은 값들로 구성된 작은 두 개의 배열로 분할한다. 그리고 분할된 각 배열을 똑같은 방법으로 다시 정렬하는 점진적인 방법을 사용한다.

<quicksort.c>

<결과값>

배열을 분할하기 위해 먼저 기준값을 선정하는데 여기선 배열의 마지막 값을 key값으로 잡았다.
그리고 for 루프에서 배열의 왼쪽과 오른쪽에 각각 left, right 포인터를 두고 중앙으로 이동하면서 left에 기준값보다 큰 값, right에 기준값보다 작은 값을 찾는다. 그리고 두 값을 교환하여 기준값보다 작은 값은 배열의 왼쪽으로 보내고 큰 값은 오른쪽으로 보낸다.

이 과정을 left와 right가 만날 때까지 반복하는데 이때 left 는 기준값보다 큰 값을 가리킨다. left와 기준값을 교환하여 left가 가리키는 값을 배열 끝으로 보내면 기준값의 왼쪽에는 이 값보다 작은 값만 있고 오른쪽에는 더 큰 값만 있을 것이다. 

왼쪽 구간과 오른쪽 구간을 다시 재귀 호출로 정렬한다. 좌우 구간의 시작점과 길이를 적절히 계산해서 QuickSort 함수를 다시 호출한다. QuickSort 함수는 주어진 크기의 배열을 정렬하되 구간 길이가 1밖에 안될 때는 정렬이 이미 완료된 것으로 보고 곧바로 리턴한다. 그렇지 않다면 구간의 끝 값을 기준으로 다시 정렬하고 이 단계에서 생긴 또 다른 작은 구간들을 정렬하기 위해 재귀 호출이 발생할 것이다.

이 과정을 반복하면 전체 배열이 정렬된다.