Section5. 빠른 정렬
2021. 8. 6. 00:29ㆍ책/misc
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
51
52
53
54
55
56
57
58
59
60
61
|
package me.kingsubin.studyrepo.book.algorithm.section5;
public class QuickSort {
public static void main(String[] args) {
int[] A = {15, 22, 13, 27, 12, 10, 20, 25, 32};
System.out.println("주어진 배열");
print(A);
quickSort(A, 0, A.length - 1);
System.out.println("\n 정렬 후 배열");
print(A);
}
public static int partition(int[] S, int low, int high) {
int i, j, temp;
i = low + 1;
j = high;
while (i <= j) {
if (S[i] <= S[low]) {
i = i + 1;
} else if (S[j] > S[low]) {
j = j - 1;
} else {
temp = S[i];
S[i] = S[j];
S[j] = temp;
i = i + 1;
j = j - 1;
}
}
temp = S[low];
S[low] = S[j];
S[j] = temp;
return j;
}
public static void quickSort(int[] S, int low, int high) {
int pivotPoint;
if (low < high) {
pivotPoint = partition(S, low, high);
quickSort(S, low, pivotPoint - 1);
quickSort(S, pivotPoint + 1, high);
}
}
public static void print(int[] A) {
for (int j : A) {
System.out.print(j + " ");
}
System.out.println();
}
}
|
cs |
여러 곳에서 퀵정렬 코드를 봤는데 매번 혼자 스스로 짜라고 하면 좀 힘들거 같다.
외우는건 너무 비효율적이고 손코딩 느낌으로 몇 번 혼자 해보고 나중에는 아이디어만 가지고 있으면 그냥 바로 구현할 수 있게끔 하는게 제일 좋을거 같다.
- 임의의 기준점 피봇을 배열의 한 원소로 잡는다. 일반적으로 A[1] 을 사용한다.
- 피봇을 기준으로 작은건 왼쪽 left, 큰건 오른쪽 right으로 분할한다.
- 위 과정을 반복하는건데 피봇은 분할된 배열에서의 다시 설정한다.
분할해서 정렬하고 분할해서 정렬하고 이런식이다.
출처: 자바로 쉽게 배우는 알고리즘
'책 > misc' 카테고리의 다른 글
HTTP 완벽 가이드 책 샀다. (2) | 2022.02.10 |
---|---|
프로그래밍 면접 이렇게 준비한다 책 샀다. (0) | 2021.08.29 |
Section5. 최댓값 최솟값 찾기 (0) | 2021.08.05 |
SQL 첫걸음 책 샀다. (0) | 2021.07.25 |
알고리즘 책 샀다. (1) | 2021.04.21 |