[알고리즘] 퀵 정렬 Quick Sort 구현해보기

백준 문제를 풀다가 퀵 정렬을 사용해야하는 문제를 만났는데
생각보다 이해하는데 오래걸리고 어렵다고 느껴져서 정리해보는 퀵 정렬.
관련 문제 : 백준 11004 K번째 수

혹시 잘못된 내용이나 질문 있으시면 댓글 부탁드립니다 :)

퀵 정렬 Quick Sort

임의의 기준 값(pivot)을 정한 후 그 값을 기준으로 좌우로 분할하며 정렬하는 방식

알고리즘 복잡도

• O(n^2) : 기준 값이 최소값 또는 최대값으로 지정되는 경우(최악의 경우)
• 평균적으로는 O(nlogn) : 일반적으로는 중간값 또는 특정값으로 지정됨

구현해보기

public class Main {

    // 퀵 정렬을 시행할 재귀함수
    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }

        int pivot = partition(arr, left, right); // 가장 partition 함수를 실행해 나오는 pivot 값

        quickSort(arr, left, pivot - 1); // pivot 좌측 quickSort
        quickSort(arr, pivot + 1, right); // pivot 우측 quickSort
    }

    public static int partition(int[] arr, int left, int right) {
        int pivot = arr[left];
        int i = left;   // pivot 좌측 index
        int j = right;  // pivot 우측 index

        while (i < j) {
            while (pivot < arr[j] && i < j) {
                j--; // 우측에서 시작해 pivot 값보다 작은 값이 나올 때까지 j 찾기
            }

            while (pivot >= arr[i] && i < j) {
                i++; // 좌측에서 시작해 pivot 값보다 크거나 같은 값이 나올 때까지 i 찾기
            }

            swap(arr, i, j); // arr[i]와 arr[j]의 값을 swap
        }
        swap(arr, left, i); // i와 j가 만난 자리의 값과 pivot 값을 swap

        return i; // 새로운 pivot 자리의 index
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 5, 4, 7, 9, 8};
        quickSort(arr, 0, arr.length - 1);
        System.out.println("result: " + Arrays.toString(arr));
    }
}