[코테 알고리즘] 퀵(Quick) 정렬

분할정복 알고리즘인 퀵(Quick) 정렬

---

특정값을 기준으로 큰숫자와 작은숫자로 분할하자
(기준값, pivot)

❓ 분할정복 알고리즘이란
: 분할한 다음 각각 정렬하고 합치면 빠르다.

🕑 시간복잡도: O(N * log(2)N)
[ 각 단계에서 N번씩 탐색 * 쪼개지는 깊이 ]
[ 평균적으로 반씩 쪼개진다 ]

퀵(Quick) 정렬 코드 구현

---

1. 피벗을 맨 앞에있는 값으로 잡는다. pivot = A[start]
2. i = start + 1로 잡고 A[i]가 피벗보다 작으면 그냥 넘긴다. i++
3. j = end로 잡고 A[j]가 피벗보다 크면 그냥 넘긴다. j--
- 엇갈리면 pivot과 swap, i > j
- 엇갈리지 않으면 양쪽 인덱스 숫자를 swap
4. 엇갈리면 while문에서 빠져나와 재귀함수 이용

<백준 알고리즘, 11004번>

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[] A = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        quickSort(A, 0, N-1);
        System.out.println(A[K-1]);
    }
    public static void quickSort(int[] A, int start, int end) {
        if(start >= end) {
            return;
        }
        int key = start;
        int i = start + 1;
        int j = end;

        while(i <= j) {
            while(i <= end && A[i] <= A[key]) {
                i++;
            }
            while(j > start && A[j] >= A[key]) {
                j--;
            }
            if(i > j) {
                int temp = A[j];
                A[j] = A[key];
                A[key] = temp;
            } else {
                int temp = A[i];
                A[i] = A[j];
                A[j] = temp;
            }
        }
        quickSort(A, start, j-1);
        quickSort(A, j+1, end);
    }
}