[정렬] 퀵정렬 (Quick Sort) - Java

1. 개요

퀵 정렬(Quick Sort)은 피벗을 하나 정하고, 배열을 피벗을 기준으로 배열을 분할하여 정렬하는 기법이다. 재귀 호출을 사용한다.

 

 

2. 시간복잡도

어떤 피벗값을 선정하는지에 따라 시간복잡도 차이가 난다.

평균 시간복잡도 : 𝛳(nlogn)

최악 시간복잡도 : O(n^2)

 

 

3. 핵심이론

1) 하나의 피벗(기준값)을 정한다. (피벗값 배열의 맨 처음 값으로 설정)

2) 시작, 끝 포인터를 설정한다. (시작 s는 0, 끝 e는 배열의 마지막 인덱스로 설정한다.)

3) s가 e보다 작을 때까지 순회한다.

    3-1) 배열의 마지막 값 (arr[e])이 피벗값 (arr[pivot]) 보다 클때 까지 순회하며, e를 1씩 왼쪽(감소)으로 이동한다.

            (피벗값보다 작은 값이 나올때까지 순회)

    3-2) 배열의 처음 값.(arr[s]) 이 피벗값 (arr[pivot]) 보다 작을때까지 순회하며, s를 1씩 오른쪽 (증가)로 이동한다.

            (피벗값보다 큰 값이 나올때까지 순회)

    3-3) arr[s]이 arr[pivot] 보다 크고, arr[e]이 arr[pivot]보다 작으면, 두 위치를 swap 한다.

4) 위 loop를 빠져왔다면, s와 e 두 포인터가 만났다는 의미이므로, s 또는 e 포인터와 pivot을 swap한다.

5) 그 결과, pivot 기준 왼쪽엔 arr[pivot] 보다 작은 값들이, 오른쪽엔 arr[pivot] 보다 큰 값들이 정렬된다.

6) pivot 기준 왼쪽 부분 배열과 오른쪽 부분배열을 다시 퀵정렬한다. (재귀 호출)

 

 

3. 예제 코드

public class Main {
    // 퀵정렬 수행 함수
    public static void quickSort(int[] arr, int start, int end){
        // 배열의 크기가 1이거나, 정렬을 수행할 배열이 더이상 없다면 재귀 호출 종료
        if(start >= end){
            return;
        }

        // pivot 위치를 구하는 partition 함수
        int pivot = partition(arr, start, end);

        // 구한 pivot을 기준으로 왼쪽 부분배열과 오른쪽 부분배열을 다시 퀵정렬 수헹 (재귀)
        quickSort(arr, start, pivot - 1);
        quickSort(arr, pivot + 1, end);
    }

    public static int partition(int[] arr, int start, int end){
        // 피벗은 배열의 첫번째 위치로 설정
        int pivot = start;
        // 처음, 끝 포인터 초기화
        int s = start;
        int e = end;

        // s가 e보다 왼쪽에 있을때 까지 loop (s와 e가 만나면 loop 종료)
        while(s < e){
            // 마지막 값이 피벗값보다 작은 값이 나올때 까지 loop
            while(arr[e] > arr[pivot] && s < e){
                // 마지막 위치를 왼쪽으로 이동
                e--;
            }
            // 처음 값이 피벗값보다 큰 값이 나올때 까지 loop
            while(arr[s] <= arr[pivot] && s < e){
                // 처음 위치를 오른쪽으로 이동
                s++;
            }

            // 처음 값이 피벗값보다 크고, 마지막 값이 피벗값보다 작으면 두 위치를 swap
            swap(arr, s, e);
        }

        // 위 while문을 빠져나왔다는 의미는 s와 e가 만났다는 의미이므로, 맨 처음 위치에 있는 pivot값과 두 포인터가 만난 s값과 swap
        swap(arr, pivot, s);

        // s와 e가 만난 지점 (둘 중 하나)을 반환
        return s;
    }

    // swap 함수
    public static void swap(int[] arr, int t1, int t2){
        int temp = arr[t1];
        arr[t1] = arr[t2];
        arr[t2] = temp;
    }
	
    // 메인 함수
    public static void main(String[] args) {
        int[] arr = {-7, 1, -3, 10, 7};

        // 주어진 배열에 대해 퀵정렬 수행
        quickSort(arr, 0, arr.length - 1);

        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}