kingsubin

Section5. 빠른 정렬 본문

책/misc

Section5. 빠른 정렬

kingsubin 2021. 8. 6. 00:29
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 = {152213271210202532};
 
        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' 카테고리의 다른 글

3장. HTTP 메시지  (0) 2022.05.02
2장. URL과 리소스  (0) 2022.04.25
1장. HTTP 개관  (0) 2022.04.24
HTTP 완벽 가이드 책 샀다.  (2) 2022.02.10
Section5. 최댓값 최솟값 찾기  (0) 2021.08.05
0 Comments
댓글쓰기 폼