퀵 정렬 알고리즘

코드 : 90rm3

 

퀵 정렬 알고리즘을 사용하여 주어진 수열을 오름차순 정렬하고자 한다. 다음은 퀵 정렬 알고리즘의 의사코드다.

 

<퀵 정렬 알고리즘>

   현재 수열의 왼쪽 끝 항이 축이다;
   다음을 반복한다.
      i = 현재 수열의 왼쪽 끝+1;
      j = 현재 수열의 오른쪽 끝;
      오른쪽으로 검사, 축보다 크거나 같은 값이 있는 위치 i;
      왼쪽으로 검사, 축보다 작거나 같은 값이 있는 위치 j;
      i>=j이면 반복을 중단한다;
   i항과 j항을 교환;
   왼쪽 끝의 축과 j항을 교환;

   왼쪽 부분 수열과 오른쪽 부분 수열에 대해서 위와 동일한 과정을 거친다.
   단, 수열을 구성하는 데이터의 개수가 1보다 커야 한다.

 

위 알고리즘을 수행할 때, i항과 j항이 맞교환되는 경우 i와 j를 출력한다.

 

입력

 

INPUT.TXT의 첫 줄에는 수열을 구성하는 데이터의 개수가, 두번째 줄에는 무작위 수열이 나온다.
데이터 개수의 범위는 1부터 1000 사이며, 수열을 구성하는 수의 범위는 1부터 500 이다.

 

출력

 

OUTPUT.TXT에는 첫번째 줄부터 i와 j가 공백을 사이에 두고 한 줄씩 출력되고, 마지막 줄에는 정렬이 완료된 수열을 출력한다.

 

INPUT.TXT의 예시 1
15
432 273 348 46 67 443 410 457 37 274 488 64 387 426 387

 

OUTPUT.TXT의 예시 1
5 14
7 13
10 12
1 8
2 3
5 9
6 8
8 9
37 46 64 67 273 274 348 387 387 410 426 432 443 457 488

 

INPUT.TXT의 예시 2
10
1 2 3 4 5 6 7 8 9 10

 

OUTPUT.TXT의 예시 2

1 2 3 4 5 6 7 8 9 10