[정렬] 퀵 정렬 : Quick Sort

📌 퀵 정렬 : Quick Sort

✅ 분할 정복(Divide and Conquer) 기법 사용

✅ 특정 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤, 배열을 반으로 나눈다.

✅ 시간 복잡도 \( O(n^2) \sim O(n \log n) \)

✅ 이미 정렬되어있는 경우에는 최악의 성능을 보여준다.

 

import java.util.Arrays;

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

    public static void quickSort(int[] arr, int start, int end){
        if(start >= end){
            return;
        }

        int pivot = partition(arr, start, end);
        quickSort(arr, start, pivot - 1);
        quickSort(arr, pivot + 1, end);

    }

    public static int partition(int[] arr, int start, int end){
        int pivot = arr[start];
        int i = start + 1;
        int j = end;

        while(i <= j){
            while(i <= end && arr[i] <= pivot){
                i++;
            }
            while(arr[j] > pivot && j > start) {
                j--;
            }
            if(i < j){
                swap(arr, i, j);
            }
        }
        swap(arr, start, j);
        return j;
    }

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

}

 

---

012

Reference.

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