퀵소트(quickSort) 2 timer 2s memory 1256MB

퀵소트는 토니 호어(찰스 엔터니 리처드 호어 - Charles Antony Richard Hoare)가 개발한 알고리즘이다.

원소들간의 비교와 교환을 통하여 정렬하는 비교기반정렬 알고리즘이다.

원소들 중에 같은 값이 있는 경우 정렬후에 이들의 순서가 달라질 수 있어 불안정 정렬에 속한다.

3518 : Tutorial : 퀵소트 문제에서 자세한 설명을 참조할 수 있다.

퀵소트를 수행하는 방식은 여러가지가 있다.

이번에는 다음과 같은 방법을 사용해보자.

quickSort(arr[], st, ed) 는 arr배열의 인덱스 st부터 ed까지 구간을 정렬하는 

재귀 함수로서 다음과 같이 구현한다.

0. st < ed라면 다음을 수행한다.

1. 인덱스 st를 피봇(pivot)으로 정하고 left = st + 1, right = ed로 한다.

2. left <= right인 동안 다음을 수행한다.

   (가) left<=ed이고 피봇보다 큰 원소가 나오기 전까지 left++

   (나) right>=s+1이고 피봇보다 작은 원소가 나오기 전까지 right--

   (다) 만약 left < right라면 두 원소의 위치를 바꾼다.

3. 피봇 st위치의 값과 right 위치의 값을 바꾼다.

4. [s, right-1]구간과 [right+1, e] 구간에 대하여 재귀적으로 퀵소트한다.

5. arr[]에 변화가 있었다면 배열을 출력한다.

quickSort(arr[], st, ed){
    
    // 위에서 설명한 0 ~ 4 프로세스
    process()
 
    quickSort(A, st, right-1)
    quickSort(A, right+1, high)
 
    // *** arr[]에 변화가 있다면 출력한다.
    output()
}