빠른 정렬(Quick sort)는 1959년에 Tony Hoare에 의하여 만들어졌다. 이 정렬은 평균적으로 매우 빠르게 수를 정렬할 수 있기 때문에 다양한 응용이 가능하다. 퀵소트로 오름차순으로 정렬하기 위하여 구간 [s, e]를 정렬한다면 알고리즘은 다음과 같다. (단 s <= e ) 1. s를 피벗으로 정한다. 2. left = s+1번으로 시작하여 피벗보다 큰 원소가 나올 때까지 left++ 3. right = e로 하고 피벗보다 작은 원소가 나올 때까지 right-- 4. 만약 left < right라면 두 원소의 위치를 바꾸고, 2번으로 진행 5. 피벗과 right의 원소의 위치를 바꾼다. 6 [s, right-1]구간과 [right+1, e] 구간을 다시 퀵소트한다. 예를 들어 처음 주어진 집합이 3 2 5 1 4 라고 하자. 피벗을 다음과 같이 3으로 정하고 l, r은 다음과 같이 된다.


[3] 2 5 1 4
    l     r

먼저 l을 이동한다. 5는 3보다 크므로 정지


[3] 2 5 1 4
      l   r

다음으로 r을 이동한다. 1은 3보다 작으므로 정지


[3] 2 5 1 4
      l r

l < r이므로 두 원소 교환 [3] 2 1 5 4 다시 l, r을 이동하면, 다음과 같이 멈춘다.


[3] 2 1 5 4
      r l

이 상태에서 l < r이 아니므로 피벗과 r의 자리를 바꾸고 다음 두 구간으로 다시 실행 [1 2] 3 [5 4] 피벗을 기준으로 왼쪽과 오른쪽을 다시 퀵정렬 수행 과 같이 진행된다. 퀵 정렬이 진행되는 동안 배열의 내용이 어떻게 변하는지 과정을 출력하는 프로그램을 작성하시오. 단, 출력은 [s, e]가 한 번 모두 처리된 후 모든 원소의 순서를 출력해야하며, 만약 바로 이전과 출력결과가 같으면 출력하지 않는다. 즉 전체 단계를 출력했을 때, i번째와 i-1번째의 출력결과가 같다면 i번째 결과를 출력하지 않는다. 코드로 나타내면 출력문을 다음과 같이 구성하라는 의미이다.


qsort()
{
    algorithm()  // 위에서 설명한 알고리즘
    qsort(s, right-1);
    qsort(right+1, e);
    print()    // 여기서 출력 (변화가 있다면)
}

빠른 정렬 (Quick-sort)

문제 설명

입력

출력

예제

코드 제출

로그인

LOGIN