퀵 정렬 (Quick sort)

퀵 정렬(Quick Sort)

퀵 정렬은 기준값(pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘이다. 기준값이 어떻게 선정되는지가 시간 복잡도에 많은 영향을 미치고, 평균적인 시간 복잡도는 O(nlogn)이다.

 

pivot을 중심으로 계속 데이터를 2개의 집합으로 나누면서 정렬하는 것이 퀵 정렬의 핵심이다.

 

https://www.w3resource.com/csharp-exercises/searching-and-sorting-algorithm/searching-and-sorting-algorithm-exercise-9.php

 

퀵 정렬 과정

1. 데이터를 분할하는 pivot 설정
2. pivot 기준 다음 2.1~2.5 과정을 거쳐 데이터를 2개의 집합으로 분리
   1. start가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start 오른쪽으로 1칸 이동
   2. end가 기리키는 데이터가 pivot이 가리키는 데이터보다 크면 end 왼쪽으로 1칸 이동
   3. start가 가리키는 데이터가 pivot이 가리키는 데이터보다 크고, end가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start, end가 가리키는 데이터를 swap하고 start는 오른쪽, end는 왼쪽으로 1칸씩 이동
   4. start가 end를 지나갈 때까지 반복
   5. start가 가리키는 값과 end가 가리키는 값 중 작은 값을 pivot과 교환, 이 pivot 값은 정렬 위치 확정
3. 분리 집합에서 각각 다시 pivot을 선정
4. 분리 집합이 1개 이하가 될 때까지 과정 1~3을 반복

 

퀵 정렬의 시간 복잡도는 비교적 준수하므로 코딩 테스트에서도 종종 응용한다.

---

[백준 11004번] K번째 수

https://www.acmicpc.net/problem/11004

 

N의 최대 범위가 5,000,000이므로 O(nlogn)의 시간 복잡도로 정렬을 수행하면 된다.

 

이 문제는 시간 복잡도가 민감하므로 퀵 정렬 알고리즘에서 K번째 수를 좀 더 빨리 구하기 위한 아이디어를 먼저 고안하기 위해 우선 어떤 값을 pivot으로 정해야 할지 생각해 봐야 한다. 

 

pivot을 정하는 방법
- pivot == K : K번째 수를 찾은 것이므로 알고리즘을 종료한다.
- pivot > K : pivot의 왼쪽 부분에 K가 있으므로 왼쪽 (S ~ pivot-1)만 정렬을 수행한다.
- pivot < K : pivot의 오른쪽 부분에 K가 있으므로 오른쪽 (pivot-1 ~ E)만 정렬을 수행한다.

 

데이터가 대부분 정렬되어 있는 경우 앞쪽에 있는 수를 pivot으로 선택하면 불필요한 연산이 많아진다. 따라서 이 문제는 배열의 중간 위치를 pivot으로 설정하겠다.

 

[정답]

import java.io.*;
import java.util.*;

public 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());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        quickSort(arr, 0, N-1, K-1);
        System.out.println(arr[K-1]);
    }
    public static void quickSort(int[] arr, int S, int E, int K) {
        if(S < E) {
            int pivot = partition(arr, S, E);
            if(pivot == K)      // K번째 수가 pivot이면 더 이상 구할 필요 없음
                return;
            else if(K < pivot)  // K가 pivot보다 작으면 왼쪽 그룹만 정렬 수행하기
                quickSort(arr, S, pivot-1, K);
            else    // K가 pivot보다 크면 오른쪽 그룹만 정렬 수행하기
                quickSort(arr, pivot+1, E, K);
        }
    }
    public static int partition(int[] arr, int S, int E) {
        if(S + 1 == E) {    // 비교 대상 2개 뿐. 소팅하지 말고 그냥 직접 비교
            if(arr[S] > arr[E]) swap(arr, S, E);
            return E;
        }
        int M = (S + E) / 2;
        swap(arr, S, M);        // 중앙값을 1번째 요소로 이동하기
        int pivot = arr[S];
        int i = S + 1, j = E;
        while(i <= j) {
            while(pivot < arr[j] && j > 0)  // 피벗보다 작은 수가 나올 때까지 j--
                j--;
            while(pivot > arr[i] && i < arr.length-1)   // 피벗보다 큰 수가 나올 때까지 i++
                i++;
            if(i <= j)
                swap(arr, i++, j--);
        }
        // i == j 피벗의 값을 양쪽으로 분리한 가운데에 오도록 설정하기
        arr[S] = arr[j];
        arr[j] = pivot;
        return j;
    }
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}

 

 

 

 

 

[참고 자료]

- 알고리즘 코딩 테스트 자바편

 

[참고]

- https://erinh.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%80%B5-%EC%A0%95%EB%A0%AC-Quick-sort-%EC%9E%90%EB%B0%94-Java

[알고리즘] 퀵 정렬 (Quick sort) - 자바 Java

- https://st-lab.tistory.com/250

자바 [JAVA] - 퀵 정렬 (Quick Sort)

- https://cdragon.tistory.com/entry/Algorithm-Quick-Sort%ED%80%B5-%EC%A0%95%EB%A0%AC

[Algorithm | Java] Quick Sort(퀵 정렬)