퀵정렬(Quick Sort) 쉽게 알기 (Java)

정의

기준값을 선정해 해당값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘

여기서 기준값을 보통 pivot이라 칭한다.

시간복잡도는 O(nlogn)

 

---

 

정렬 방법

1. 데이터를 분할하는 pivot을 정한다.
2. pivot을 기준으로 다음 과정을 거쳐 2개의 집합으로 분리한다.
   1. pivot을 기준으로 start와 end를 잡는다. (pivot이 들어갈 위치를 찾는 것)
      1. start: pivot보다 큰 데이터가 나올때까지 start를 오른쪽으로 이동
      2. end: pivot보다 작은 데이터가 나올때까지 end를 왼쪽으로 이동
      3. start와 end를 swap
   2. start와 end가 만날때까지 위의 1~3번을 반복
   3. start와 end가 만나면, 크기 비교 후 swap
   4. pivot을 start와 end 사이에 삽입
3. 나눠진 각 그룹을 또 quick sort한다. (1번부터 반복)

 

---

 

그림으로 보기

한번의 퀵소트를 진행

pivot을 기준으로 작은값 / 큰값이 분류되었고, 또 이것들을 퀵소트를 한다.

 

---

 

그렇다면 알고리즘을 어떻게 짤까?

Quick sort함수: 정렬을 수행

pivot구하기 함수: 무엇을 pivot으로 삼을지와, pivot을 정했으면 pivot을 기준으로 patition을 나누는 것을 수행

그리고 swap을 자주하므로 swap하는 함수도 따로 구현해주면 좋다.

 

---

 

백준 11004 K번째수

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

11004번: K번째 수

// Baekjoon_11004_K번째수
// Quicksort

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

public class KthNum {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int[] A = new int[N];
        for(int i=0; i<N; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }

        quick(A, 0, N-1, K-1);
        System.out.println(A[K-1]);
    }

	// 퀵정렬 함수
    private static void quick(int[] array, int start, int end, int k) {
        if(start < end) {
            int pivot = partition(array, start, end);

            if(pivot == k)  return;
            // k가 pivot보다 작으면 왼쪽 그룹만 정렬 수행
            else if(k < pivot)  quick(array, start, pivot-1, k);
            // k가 pivot보다 크면 오른쪽 그룹만 정렬 수행
            else   quick(array, pivot+1, end, k);
        }
    }

	// pivot구하기 함수
    private static int partition(int[] array, int start, int end){
        if(start + 1 == end) {    // 원소가 2개면
            if(array[start] > array[end])
                swap(array, start, end);
            return end;
        }

        int medium = (start + end) / 2;   // 중간에 있는 값을 pivot으로 설정
        // pivot을 첫번째 위치로 옮김 (반복문 편하게 돌리기 위해서)
        swap(array, medium, start); 
        int pivot = array[start];

        int i = start + 1;  // 첫번째 값은 pivot이니까 그다음 값부터 순회
        int j = end;
        
        while(i <= j) {
            // pivot보다 작은수가 나올때 까지 --
            while(array[j] > pivot && j > 0) {
                j--;
            }
            // pivot보다 큰수가 나올때 까지 ++
            while(array[i] < pivot && i < array.length-1) {
                i++;
            }
            if(i <= j) {
                swap(array, i++, j--);
            }
        }

        // pivot 인덱스를 리턴
        array[start] = array[j];
        array[j] = pivot;
        return j;
    }

	// swap 함수
    private static void swap(int[] array, int a, int b) {
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}