퀵 정렬

퀵 정렬

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다.
가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다.

시간 복잡도

• 평균의 경우: O(NlogN)
• 최악의 경우: O(N^2)

 

 

동작 과정

0) 현재 피벗의 값은 '5'이다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '7'이 선택되고
오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '4'가 선택된다. 이제 이 두 데이터의 위치를 서로 변경한다.

1) 현재 피벗의 값은 '5'이다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '9'가 선택되고
오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '2'가 선택된다. 이제 이 두 데이터의 위치를 서로 변경한다.

2) 현재 피벗의 값은 '5'이다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '6'이 선택되고
오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '1'이 선택된다. 단, 이처럼위치가 엇갈리는 경우 '피벗'과
'작은 데이터'의 위치를 서로 변경한다.

3) 이제 '5'의 왼쪽에 있는 데이터는 모두 5보다 작고, 오른쪽에 있는 데이터는 모두 '5'보다 크다는
특징이 있다. 이렇게 피벗을 기준으로 데이터 묶음을 나누는 작업을 분할(Divide)이라고 한다.

4) 왼쪽에 있는 데이터에 대해서 마찬가지로 정렬을 수행한다.

5) 오른쪽에 있는 데이터에 대해서 마찬가지로 정렬을 수행한다.

 

 

구현 코드

public class Main {
    public static void main(String[] args) {
        int n = 10;
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
 
        quickSort(arr, 0, n - 1);
 
        for(int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }
 
    public static void quickSort(int[] arr, int start, int end) {
        // 원소가 1개인 경우 종료
        if (start >= end) {
            return;
        }
 
        int pivot = start; // 피벗은 첫 번째 원소
 
        int left = start + 1;
        int right = end;
 
        while (left <= right) {
            // 피벗보다 큰 데이터를 찾을때까지 반복
            while (left <= end && arr[left] <= arr[pivot]) {
                left++;
            }
 
            // 피벗보다 작은 데이터를 찾을때까지 반복
            while (right >= start && arr[right] >= arr[pivot]) {
                right--;
            }
 
            // 엇갈렸다면 작은 데이터와 피벗을 교체
            if (left > right) {
                int temp = arr[pivot];
                arr[pivot] = arr[right];
                arr[right] = temp;
            } else { // 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
 
        // 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
        quickSort(arr, start, right - 1);
        quickSort(arr, right + 1, end);
    }
}