kingsubin

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();
    }
}
 

 

여러 곳에서 퀵정렬 코드를 봤는데 매번 혼자 스스로 짜라고 하면 좀 힘들거 같다. 

외우는건 너무 비효율적이고 손코딩 느낌으로 몇 번 혼자 해보고 나중에는 아이디어만 가지고 있으면 그냥 바로 구현할 수 있게끔 하는게 제일 좋을거 같다.

 

- 임의의 기준점 피봇을 배열의 한 원소로 잡는다. 일반적으로 A[1] 을 사용한다.

- 피봇을 기준으로 작은건 왼쪽 left, 큰건 오른쪽 right으로 분할한다.

- 위 과정을 반복하는건데 피봇은 분할된 배열에서의 다시 설정한다.

 

분할해서 정렬하고 분할해서 정렬하고 이런식이다.

 

---

출처: 자바로 쉽게 배우는 알고리즘