Informatica Online Judge

  빠른 정렬 (Quick-sort) [1323 / 052B]

Time Limit(Test case) : 2000(ms)
Number of users who solved : 65   Total Tried : 98


The Champion of this Problem (C++) : gs17044 - ms / 644byte
My Best Submission (C++) : N/A

[JKJeong 2015]

Background

빠른 정렬(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() // 여기서 출력 (변화가 있다면)
}

Input

첫 번째 줄에 원소의 수 n이 입력된다.

다음 줄에 n개의 원소가 공백으로 구분되어 입력된다.

[입력값의 정의역]
1 <= n <= 5,000
각 원소의 값 <= |1,000|

Output

퀵 정렬 재귀함수가 한 번 완전히 실행되었을 때의 결과를 출력한다. 만약 처음부터 오름차순으로 정렬이 되어 출력할 필요가 없다면 "OK"를 출력한다.

IO Example

입력1
1
5

출력1
OK

입력2
5
3 2 5 1 4

출력2
1 2 3 5 4
1 2 3 4 5

입력3
3
3 2 1

출력3
1 2 3

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]