정렬(Sort)

Selection-Sort

Contents

소년 빌게이츠는 학원에서 알고리즘 수업에서 선택정렬을 배웠다. 학원 선생님이 말하길 제일 큰 원소를 찾아서 뒤로 옮기면 정렬이 된다고 했다.

학원 선생님이 전수해준 비기는 다음과 같다. 

1. A[1..k]중 가장 큰 원소를 찾는다.

2. 가장 큰 원소를 A[k]와 바꾼다. (매번의 반복 마다 swap은 한번만 일어나야한다.)

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

소년 빌게이츠는 수행 시간을 측정하기 위해 1번에서 최대값을 찾기 위해 수행하는 비교 횟수를 다음의 조건에 따라 측정하기로 했다. 여러분이 해야하는 일은 소년 빌게이츠를 도와 선택정렬의 비교 회수를 출력하면 된다. 선택정렬은 소년 빌게이츠가 배운대로 구현되어야 한다. 

Input

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

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

Output

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

※ 비교 회수를 세는 방법에 대한 추가사항

 - 최대값을 찾기 위한 비교회수를 세는 것은 결국 조건문이 얼마나 수행되었나를 세는 것과 같이 때문에 배열의 크기가 n개 라면 선택정렬 알고리즘에 의해 조건문 수행 회수는 n*(n - 1) / 2와 같다. 이는 정렬 알고리즘을 구현하지 않고도 충분히 수식으로 계산 가능한 값이다. 따라서 다음의 조건일 때만 비교회수를 센다. 

 조건) A[1..k]에서 최대값을 찾기 위해 수행하는 조건문이 참일 때만 비교회수를 센다.

※ 최대값을 구하는 방법에 대한 추가 사항

- 최대값을 구하기 위한 max 초기값을 임의로 잡지 말고 배열 내 첫 번째 원소로 잡는다.

Sample Input

10

0 7 1 6 7 7 6 6 5 4 

 

Sample Output

17

=================================================================

Bubble-Sort

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

=================================================================

Insertion Sort

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

=================================================================

Merge Sort

Contents

소년 빌게이츠는 정렬 알고리즘의 O(n^2)의 비효율성에 치를 떨며 분노하고 있었다. 평소 평화주의자의 길을 걷고 있던 학원 선생님은 빌게이츠의 마음에 평화를 주기 위해 더 빠른 알고리즘을 소개해주었다. 

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

2. A[p..r]에서 절반으로 자른다. (q = (p + r) / 2)

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

4. 3이 정상적으로 수행되었다면 A[p...q]와 A[q+1...r]는 정렬되어 있다. 이를 서로 비교하며 merge 한다.

소년 빌게이츠는 이것의 수행시간을 분석해보고 싶었다.  여러분이 할일은 빌게이츠를 도와 다음의 조건대로 비교회수를 구해 출력하는 프로그램을 만드는 것이다. 이 때 머지소트는 빌게이츠가 배운대로 구현되어야 한다.

※ merge할 때 책에 있는 소스 대로 구현해야 합니다. 

Input

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

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

Output

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

Sample Input

10

0 7 1 6 7 7 6 6 5 4 

Sample Output

21

=================================================================

Quick Sort

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을 할 때, 배열 내 원소들 사이의 교환 회수를 계산하여 출력한다. 이 때 퀵소트는 빌게이츠가 배운대로 구현되어야 한다. 빌게이츠가 배운 partition 방법은 다음과 같다.

partition(A[], p, r)

{

   x = A[r];

   i = p - 1;

   for j = p to r - 1

      if(A[j] <= x) then A[++i] ↔ A[j];

   A[i+1] ↔ A[r];

   return i + 1;

}

※ 책과 다른 partition 방법을 쓰면 정렬은 되나 교환 회수가 다르게 나타날 수 있습니다. 문제의 명확성을 위해서 책에 나온 partition을 써놓았고, 문제의 조건을 수정하였습니다. 불편을 끼쳐드려 죄송합니다. 

※ 책 : 쉽게 배우는 알고리즘 관계 중심의 사고법 - 문병로 지음

Input

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

그 다음 줄에는 n개의 임의의 정수가 들어온다. 이 때 각 정수는 서로 다른 값을 가진다.

Output

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

Sample Input

10

4 3 7 8 0 5 2 1 6 9 

 

Sample Output

24

=================================================================

Heap Sort

Contents

학원 선생님은 소년 빌게이츠가 열정적으로 코딩하는 모습을 보고 감동해서 다른 O(nlogn) 알고리즘인 HeapSort를 소개 해주었다. (소년 빌게이츠는 작년에 자료구조 시간에 Heap배워서 Heap을 구성 할 순 있었다.)

1. A[1...n]에 대해서 Max-Heap를 구성한다

2. A[1...k]에서 A[1]과 A[k]를 맞바꾼다.

3. A[1...k-1]에서 다시 Max-Heap을 재구성한다.

4. A[1...k-1]에 대해서 2, 3을 반복한다.

여기서 3번의 Max-heap를 재구성할 때 필요한 원소의 교환 회수를 계산해서 출력한다. (1번의 과정을 위한 원소 교환 회수는 제외) 이 때 힙소트는 빌게이츠가 배운대로 구현되어야 한다.

※ heapify에서 원소 비교 기준 추가

1. 부모의 왼쪽 원소와 오른쪽 원소가 같은 경우 큰 것을 오른쪽 원소로 한다. 

2. 부모와 bigger의 교환는 bigger가 클 때만 교환한다.

Input

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

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

Output

오름차순으로 정렬하고, Max-heap를 재구성할 때 필요한 원소의 교환 회수를 계산해서 출력한다.

Sample Input

10

0 7 1 6 7 7 6 6 5 4

 

Sample Output

12

=================================================================

Couting Sort

Contents

빌게이츠는 정렬하고자 하는 원소들의 값이 한정되있는 경우, 예를 들어서 배열 A[1..n]의 원소들이 k를 넘지 않는 자연수인 경우 각 원소를 세는(count)하는 방식으로도 정렬을 할 수 있음을 알아냈다. 알고리즘은 다음과 같다. 

1. 배열 A에서 max와 min값을 찾고 k를 max - min + 1로 둔다. 

2. 배열 C를 k 만큼 확보 한다. 

3. 배열 A에 대해서 각 원소를 카운팅 한다. 예를 들어 32에 대해서는 C[32 - min]을 1 증가 한다.

4. 배열 C를 2부터 시작해서 k까지 누적한다. ( C[1...k] )

C[i] = C[i] + C[i - 1];

5. 배열 A에 대해서 카운팅 횟수를 참조하여 B에 다음과 같은 방식으로 기록한다.

B[C[A[j] - min]] = A[j];

C[A[j] - min] --;

위 과정을 수도 코드로 표현 하면 다음과 같다.

coutingSort(A, B, n){

   //A[1...n]

   //B[1...n]

   //C[1...k]

   //find min max of A

   k = max - min + 1

   for i = 1 to k

      C[i] = 0;

   for j = 1 to n

      C[A[j]-min]++;

   for i = 2 to k

      C[i] = C[i] + C[i-1];

   for j = n to 1

      B[C[A[j]-min] = A[j]

      C[A[j]-min]--;

}

이 때 빌게이츠는 누적 배열의 값이 궁금해졌다. 여러분이 할일은 B에 값을 쓰기 전에 누적 배열의 값들을 출력해야 한다.

Input

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

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

Output

오름차순으로 정렬할 때, 누적 배열 C[1...k]의 원소들을 1부터 k까지 하나씩 출력한다. 

각 원소는 빈칸으로 분리 되어야 한다. 

Sample Input

10

0 7 1 6 7 7 6 6 5 4 

 

Sample Output

1 2 2 2 3 4 7 10

=================================================================

Radix Sort

Contents

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

radixSort(A[], n, k){

//원소들이 각각 최대 k 자리수인 A[1..n]을 정렬한다.

//가장 낮은 자리수를 1번째 자리수라 함

   for i<-1 to k

      //i 번째 자리수에 대해 A[1..n]을 안정성을 유지하면서 O(n)안에 정렬한다.

      ....내용 훼손       

}

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

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