|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
import java.util.Arrays;
public class PancakeSort {
public static void main(String[] args) {
int len = 10;
int[] arr = new int[len];
//Random initialization
for(int i = 1; i <= len; i++) {
arr[i - 1] = ((int)((Math.random() * len) + 1));
}
System.out.println(Arrays.toString(arr));
sort(arr, len - 1);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr, int beginIdx) {
if(beginIdx > 0) { sort(arr, beginIdx - 1); }
int m = minIdx(arr, beginIdx);
if(m != beginIdx) {
flip(arr, m, arr.length - 1);
flip(arr, beginIdx, arr.length - 1);
}
}
public static void flip(int[] arr, int fromIdx, int toIdx) {
if(toIdx - fromIdx >= 1) {
flip(arr, fromIdx + 1, toIdx - 1);
int temp = arr[fromIdx]; arr[fromIdx] = arr[toIdx]; arr[toIdx] = temp; }
}
public static int minIdx(int[] arr, int beginIdx) {
if(beginIdx == arr.length - 1) {
return arr.length - 1;
} else {
int m = minIdx(arr, beginIdx + 1);
if(arr[beginIdx] < arr[m]) {
return beginIdx;
} else {
return m;
}
}
}
}
|
cs |
|
|
|
시간 복잡도: $O(n^2)$
선택정렬(https://t0pli.tistory.com/199)이랑 크게 다르지 않은 것 같다.
$minIdx$ 메소드는 아예 그대로 썼다.
$flip$ 메소드만 구현한다면 다 한 거나 진배없다.
원래는 23행의 조건문이 없었는데, 문제를 풀려고 넣었다.
$arr$로 내림차순으로 정렬된 배열이 주어졌을 때 시간복잡도가 $O(n)$이 되는 걸 설명해야 되는데,
이게 성립하려면 조건문이 필요했다. 저 조건문이 없으면 내림차순이고 뭐고 무조건 $O(n^2)$이다.
오름차순 정렬이 주어지면 $flip$ 연산은 한 번도 실행되지 않는다. 따라서 이 경우가 best case가 된다.
'Programming > 과제' 카테고리의 다른 글
| [과제] Dynamic programming (0) | 2021.06.22 |
|---|---|
| [과제] Divide and conquer (1) | 2021.05.21 |
| 재귀호출을 이용한 최소값 찾기, 총합 구하기, 선택 정렬 (0) | 2021.03.21 |
| Pancake sorting by Iteration (0) | 2021.03.16 |
| 재귀함수를 이용한 최소공배수 구하기 (0) | 2021.03.08 |
