1.4 정렬 - 퀵 정렬 (Quick sort)

삽입정렬, 버블정렬, 선택정렬은 모두 시간복잡도가 O(n^2)를 가지고 있다.

O(n^2)의 시간복잡도는 데이터의 갯수가 10만개일 때 100억번의 연산을 할 수 도 있기 때문에,

데이터가 많으면 사용하기 어렵다.

따라서 더 작은 시간복잡도의 알고리즘이 필요하다.

• 퀵정렬 - 대표적인 분할정복 알고리즘
• 시간복잡도 = O(N*logN)
• 특정한 값(pivot)을 기준으로 큰 값과 작은 값으로 나누어 교환한 뒤, 배열을 반으로 나누어 정렬

ex)

int[] arr = {6, 7, 3, 2, 5, 8, 1, 4}; -> (오름차순 정렬)

1. arr[0] -> pivot {일반적으로 가장 앞의 값을 피벗으로 설정}
2. {6, 7, 3, 2, 5, 8, 1, 4} -> arr[1] ~ arr[end] 피벗보다 큰 수 탐색 -> {7}
3. {6, 7, 3, 2, 5, 8, 1, 4} -> arr[end] ~ arr[1] 피벗보다 작은 수 탐색 -> {4}
4. 위치정렬 -> {6, 4, 3, 2, 5, 8, 1, 7}
5. repeat [2~4];
6. -> {6, 4, 3, 2, 5, 1, 8, 7}
7. if( 3번 탐색 인덱스 < 2번 탐색 인덱스 ) {
   • pivot // arr[3번 탐색 인덱스] 위치변경
   • pivot = arr[0] ;
   • }
8. -> {1, 4, 3, 2, 5, 6, 8, 7} -> 피벗지정 -> 재귀
9. -> {1, 4, 3, 2, 5, 6, 7, 8} -> {1, 4, 3, 2, 5, 6, 7, 8} -> {1, 2, 3, 4, 5, 6, 7, 8} -> 반복.....
10. -> {1, 2, 3, 4, 5, 6, 7, 8}

public class Blog {
 
    public static void main(String[] args) {
        int[] arr = { 6, 7, 3, 2, 5, 8, 1, 4 };
        int n = arr.length;
 
        quickSort(arr, 0, n - 1);
 
        for (int i = 0; i < n; i++) {
            System.out.printf("%d", arr[i]);
        }
    }
 
    private static void quickSort(int[] arr, int start, int end) {
        if (start >= end)
            return; // 원소가 1개일 때 그대로두기
        int pivot = start; // 첫번째 원소
        int i = start + 1; // 앞 부터 탐색
        int j = end; // 뒤 부터 탐색
        int temp;
 
        while (i <= j) { // 작은 원소 탐색 값이 큰 원소 탐색 값 보다 앞 일때 까지 반복
            while (i <= end && arr[i] <= arr[pivot])
                i++; // 피벗보다 큰 값을 만날 때 까지
            while (j > start && arr[j] >= arr[pivot])
                j--; // 피벗보다 작은 값을 만날 때 까지
 
            if (i > j) { // 탐색 결과가 엇갈렸을 때, 작은원소가 앞일 때
                temp = arr[j];
                arr[j] = arr[pivot];
                arr[pivot] = temp;
                // pivot 교체
            } else {
                temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
                // i,j 교체
            }
            quickSort(arr, start, j - 1);
            quickSort(arr, j + 1, end);
        }
    }
}
 

• 예를 들어, 배열의 길이가 10 일 때 (N=10)
  • 선택정렬의 정렬 => 10 X 10 = 10회 연산
  • 배열을 절반으로 나눈뒤 정렬 (분할) => 5 X 5 = 25 회
    • 총 25 X 2 = 50회 연산
• 따라서, 매회 마다 절반씩 나누어 계산 정렬하게되면, 연산횟수는 log(2)N에 비례하게 된다. O(NlogN)
• 다만, 최악의 경우 O(N^2)이 된다. (이미 정렬이 완료된 경우)