1번

BubbleSort
Contents
삽입정렬을 마스터한 소년 빌게이츠는 새로운 정렬법을 배웠다. 빌게이츠가 배운 방법은 다음과 같다.

1. A[1..k]에 대해서 1부터 k-1까지, A[i], A[i+1]에 대해서 비교를 하면서 A[i] > A[i+1]인 경우 맞바꾼다.

2. 배열의 크기가 n이라고 할 때, k = n 부터 k = 2 까지의 위 과정을 반복한다.

긴 설명은 필요 없이 1번에 대해서 교환 회수를 모두 세서 출력하면 된다. 버블정렬은 빌게이츠가 배운대로 구현되어야 한다.

Input
첫 줄에는 정렬해야 하는 원소의 개수 n(1<=n<=10000)이 들어 온다.

그 다음 줄에는 n개의 임의의 정수가 들어 온다.

 

Output
오름차순으로 정렬할 때, 배열 내의 원소들 사이의 교환 회수를 출력한다.

 

Sample Input
10
0 7 1 6 7 7 6 6 5 4
 
Sample Output
21

 

 

2번
InsertionSort
Contents
이번에는 삽입정렬이다. 방법은 다음과 같다.

1. A[1..k]중 A[k]가 들어갈 적당한 자리를 찾는다.

2. 배열의 크기가 n이라고 할 때, k = 1부터 k = n 까지 위 과정을 반복한다.

※ 이동에 대한 추가 설명

 - A[k]가 들어갈 적당한 자리를 찾기 위해 원소가 오른쪽으로 이동 하는 횟수와

 - A[k]가 적당한 위치에 삽입되는 회수까지 포함하여 센다.

삽입정렬 또한 빌게이츠가 배운대로 구현되어야 한다.

Input
첫 줄에는 정렬해야 하는 원소의 개수 n(1<=n<=10000)이 들어 온다.

그 다음 줄에는 n개의 임의의 정수가 들어 온다.

 

Output
오름차순으로 정렬할 때, 배열 내의 원소들의 이동회수를 출력한다.

 

Sample Input
10
0 7 1 6 7 7 6 6 5 4
 
Sample Output
30

 

 


3번
QuickSort
Contents
소년 빌게이츠는 MergeSort를 공부하고 재미 있어서 O(nlogn)으로 정렬하는 다른 알고리즘을 찾았다. 그 중 QuickSort는 다음과 같다.

1. A[p..r]를 정렬해주는 함수 quickSort가 있다고 가정한다.

2. A[p..r]에서 기준 원소를 중심으로 대소를 분류 후, 그 기준 원소의 위치를 q라 하자.( partition )

  2.1 기준 원소를 항상 배열의 마지막 위치에 있는 원소로 선택한다.

3. A[p..q-1]와 A[q+1...r]에 대해서 다시 1의 quickSort를 수행한다.

여기서는 partition을 할 때, 배열 내 원소들 사이의 교환 회수를 계산하여 출력한다. 이 때 퀵소트는 빌게이츠가 배운대로 구현되어야 한다.

Input
첫 줄에는 정렬해야 하는 원소의 개수 n(1<=n<=10000)이 들어 온다.

그 다음 줄에는 n개의 임의의 정수가 들어온다.

 

Output
오름차순으로 정렬할 때, 배열 내 원소들 사이의 교환 회수를 출력한다.

 

 

Sample Input
10
0 7 1 6 7 7 6 6 5 4
 
Sample Output
20

4번
RadixSort
 

Contents
O(nlogn) 알고리즘을 어느 정도 공부한 빌게이츠는 O(n)에 정렬을 할 수 없는지 궁리하기 시작했다. 그런데 아무리 생각해도 다른 방법을 생각 할 수 없었다. 그러던 어느날 빌게이츠는 7호관 뒷마당 땅을 파다가 고대 문서를 발견했다. 고대 문서에는 다음과 같은 정렬법이 써있었다.

1
2
3
4
5
6
7
8 radixSort(A[], n, k){
//원소들이 각각 최대 k 자리수인 A[1..n]을 정렬한다.
//가장 낮은 자리수를 1번째 자리수라 함
   for i<-1 to k
      //i 번째 자리수에 대해 A[1..n]을 안정성을 유지하면서 O(n)안에 정렬한다.
      ....내용 훼손
       
}

빌게이츠는 자리수라는 아이디어에 O(n)에 정렬 할 수 있겠구나 생각을 했다. 그러나 훼손된 문서로는 완벽한 구현이 힘들었다.  그래서 빌게이츠는 학원 선생님을 찾아 갔다. 학원 선생님이 알려준 구체적인 방법은 다음과 같다.

1
2
3
4
5
6
7
8
9
10
11
12 radixSort(A[], n, k){
   queue que[10]; //que[0..9]
 
   for i<-1 to k
      for j<-1 to n
         d <- digit(A[j], i) //A[j]의 i번째 자리의 수
         enque( que[d], A[j] );
      p<-1;
      for j<-0 to 9
         while( que[j] is not empty )
            A[p++] = deque(que[j]);
}

빌게이츠는 자신의 눈을 의심하지 않을 수가 없었다. 그래서 디버깅을 하기로 했다. 여러분이 해야 하는 일은 위와 같은 방식으로 radixSort를 구현 했을 때, 정렬이 진행되다 자릿수 t에 대해 정렬한 후 그 단계에서 배열을 출력하는 것이다.

 

Input
첫 줄에는 정렬해야 하는 원소의 개수 n(1<=n<=10000)와 디버깅을 위한 자릿수 t가 들어온다.

그 다음 줄에는 n개의 임의의 정수가 들어 온다.

여기서는 각 입력별 최대 자릿수(k)는 주어지지 않는다. 입력에 따라 계산을 해야 한다.

 

Output
radixSort를 진행하다가, 자릿수 t에 대해서 정렬 한 뒤 그 단계에서 배열을 출력한다.

출력 할 때 원소 사이에는 빈칸이 들어가야 한다.

 

Sample Input
10 1

0 7 1 6 7 7 6 6 5 4
 

Sample Output
0 1 4 5 6 6 6 7 7 7