정렬 - 퀵 정렬

1. 퀵 정렬이란

https://visualgo.net/en/sorting

• 선택, 버블, 삽입 정렬은 데이터가 1만개만 넘어가도 사용하기가 어려운 시간복잡도를 가진 알고리즘이다
• 퀵 정렬은 분할 정복 알고리즘을 사용하여 원소들을 나누어서 계산한다.
  
  1. 특정 값을 기준(= 기준값 = Pivot)으로 반으로 나눔(pivot보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 모으는 함수를 만듦)
     • 피벗은 왼쪽 끝, 오른쪽 끝, 중간으로 선택하여 사용할 수 있다.
  2. 피벗을 기준으로 왼쪽에서는 피벗보다 큰 값을 찾고 오른쪽에서부터는 피벗보다 작은 값을 찾는다.
  3. 찾은 값을 바꾼다
  4. 2, 3을 반복한다
  5. 2, 3을 반복하다가 인덱스가 같아지거나 엇갈리는 때가 생기는데 그러면 해당인덱스와 피벗을 바꾼다.
     • 바꾼 후 인덱스를 하나씩 증가/감소 시켜 포인터를 이동시켜 준다.
     • 5를 수행하고 나면 피벗을 기준으로 왼쪽은 피벗보다 작은 값, 오른쪽은 피벗보다 큰 값이 오게 된다.
  6. 왼쪽과 오른쪽에 대해서도 똑같이 퀵 정렬을 수행한다(재귀)
     • 재귀함수는 스택 구조를 갖는다는 것을 잊지 말자

• • 큰 값 찾기 : 왼쪽에서 오른쪽으로, 작은 값 찾기 : 오른쪽에서 왼쪽으로 이동

이미지 출처 :  https://ju-nam2.tistory.com/61

2. 피벗을 가장 왼쪽 끝으로 잡고 퀵 정렬 하는 경우

public class QuickSort {
    static int[] solution(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
        return arr;
    }

    static void quickSort(int[] arr, int start, int end){
        int i, j, tmp;
        if (start >= end) {
            return;
        }
        int pivot = start;
        i = start + 1;
        j = end;
        while (i <= j) { // 엇갈릴 때까지 반복
            while (i <= end && arr[i] <= arr[pivot]) i++;
            while (j > start && arr[j] >= arr[pivot]) j--;
            if (i > j) { // 엇갈리면 왼쪽값과 피봇값 바꾸기
                tmp = arr[j];
                arr[j] = arr[pivot];
                arr[pivot] = tmp;
            }else{ // 엇갈리지 않았으면 두 값을 서로 바꾸기
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
            }
        }
        quickSort(arr, start, j - 1);
        quickSort(arr, j + 1, end);
    }

    public static void main(String[] args) {
        int[] arr = new int[]{3, 7, 8, 1, 5, 9, 6, 10, 2, 4};

        int[] result = solution(arr);
        for (int i : result) {
            System.out.print(i + " ");
        }
    }
}

3. 피벗을 가운데로 잡고 퀵 정렬 하는 경우

• [ 0, 9, 4, 7, 3, 1, 5, 8, 6, 2 ]를 예로 들었을 때 피벗은 0 + 9 / 2 = 4 -> 값 : 3
  • start = arr[0], end = arr[9]부터 시작하여 증감하는데
  • start = arr[1], end = arr[9]에서 각각 3보다 큰 값(작지 않은 값), 작은 값(크지 않은 값)을 찾음 -> 위치 바꿈
  • 인덱스를 하나씩 증감 -> start = arr[2], end = arr[8]
• [ 0, 2, 4, 7, 3, 1, 5, 8, 6, 9 ] : 4와 6부터 다시 큰 값, 작은 값 찾기 시작
  • start = arr[2], end = arr[5]에서 각각 3보다 큰 값(작지 않은 값), 작은 값(크지 않은 값)을 찾음 -> 위치 바꿈
  • 인덱스를 하나씩 증감 -> start = arr[3], end = arr[4]
• [ 0, 2, 1, 7, 3, 4, 5, 8, 6, 9 ]
  • start = arr[3], end = arr[4]에서 각각 3보다 큰 값(작지 않은 값), 작은 값(크지 않은 값)을 찾음 -> 위치 바꿈
  • 인덱스를 하나씩 증감 -> start = arr[4], end = arr[3]
  • start와 end의 인덱스가 역전되었으므로 반복문 종료 
    • [ 0, 2, 1, 3, 7, 4, 5, 8, 6, 9 ]
      • start = 0보다 part -1 = 3 이 크므로 왼쪽 파티션에 대해서 재귀함수 호출
      • [ 0, 2, 1, 3, 7, 5, 8, 6, 9 ] : pivot = 2
      • start = arr[0], end = arr[3]부터 시작하여 증감함
      • start = arr[1], end = arr[2]에서 각각 2보다 큰 값(작지 않은 값), 작은 값(크지 않은 값)을 찾음 -> 위치 바꿈
      • 인덱스를 하나씩 증감 -> start = arr[2], end = arr[1]
      • start와 end의 인덱스가 역전되었으므로 반복문 종료 
      • 다시 재귀함수 호출하여 정렬 수행 마지막까지 수행한 후 part - 1이 start(= 0)보다 크지 않으면 오른쪽 파티션 정렬 시작
    • 오른쪽 파티션 정렬 시작

 

import java.util.Arrays;

public class QuickSort2 {
        private static void quickSort(int[] arr,int start, int end) {
            int part=partition(arr,start,end);
            System.out.println("part : " + part);
            System.out.println("***** 왼쪽 파티션 시작 *****");

            // 왼쪽 파티션에 정렬할 값이 있으면
            if(start<part-1) quickSort(arr,start,part-1);

            System.out.println("***** 왼쪽 파티션 끝 *****");
            System.out.println("***** 오른쪽 파티션 시작 *****");

            // 오른쪽 파티션에 정렬할 값이 있으면
            if(end>part) quickSort(arr,part,end);

            System.out.println("***** 오른쪽 파티션 끝 *****");
        }

        private static int partition(int[] arr,int start,int end) {
            int pivot=arr[(start+end)/2];
            System.out.println("최초 start : " + start + ", end : " + end + ", pivot : " + pivot);
            System.out.println("===== while start =====");
            while(start<=end) {
                while (arr[start] < pivot) {
                    start++;
                   System.out.println("start : " + start);
                }
                while(arr[end]>pivot) {
                    System.out.println("end : " + end);
                    end--;
                }
                if(start<=end) {
                    System.out.println("swap 수행 전 start : " + start + ", end : " + end);
                    swap(arr,start,end);
                    System.out.println(Arrays.toString(arr));
                    start++;
                    end--;
                    System.out.println("swap 수행 후 start : " + start + ", end : " + end);
                }
            }
            System.out.println("===== while end ===== start : " + start);
            return start;
        }

        private static void swap(int[] arr,int start,int end) {
            int tmp=arr[start];
            arr[start]=arr[end];
            arr[end]=tmp;
            return;
        }


        public static void main(String[] args) {
            int[] arr= {0, 9, 4, 7, 3, 1, 5, 8, 6, 2};
            quickSort(arr,0,arr.length-1);
            for(int i=0;i<arr.length;i++) {
                System.out.print(arr[i]+" ");
            }
        }
}

/**

최초 start : 0, end : 9, pivot : 3
===== while start =====
start : 1
swap 수행 전 start : 1, end : 9
[0, 2, 4, 7, 3, 1, 5, 8, 6, 9]
swap 수행 후 start : 2, end : 8
end : 8
end : 7
end : 6
swap 수행 전 start : 2, end : 5
[0, 2, 1, 7, 3, 4, 5, 8, 6, 9]
swap 수행 후 start : 3, end : 4
swap 수행 전 start : 3, end : 4
[0, 2, 1, 3, 7, 4, 5, 8, 6, 9]
swap 수행 후 start : 4, end : 3
===== while end ===== start : 4

part : 4
***** 왼쪽 파티션 시작 *****
최초 start : 0, end : 3, pivot : 2
===== while start =====
start : 1
end : 3
swap 수행 전 start : 1, end : 2
[0, 1, 2, 3, 7, 4, 5, 8, 6, 9]
swap 수행 후 start : 2, end : 1
===== while end ===== start : 2

part : 2
***** 왼쪽 파티션 시작 *****
최초 start : 0, end : 1, pivot : 0
===== while start =====
end : 1
swap 수행 전 start : 0, end : 0
[0, 1, 2, 3, 7, 4, 5, 8, 6, 9]
swap 수행 후 start : 1, end : -1
===== while end ===== start : 1

part : 1
***** 왼쪽 파티션 시작 *****
***** 왼쪽 파티션 끝 *****
***** 오른쪽 파티션 시작 *****
***** 오른쪽 파티션 끝 *****
***** 왼쪽 파티션 끝 *****
***** 오른쪽 파티션 시작 *****
최초 start : 2, end : 3, pivot : 2
===== while start =====
end : 3
swap 수행 전 start : 2, end : 2
[0, 1, 2, 3, 7, 4, 5, 8, 6, 9]
swap 수행 후 start : 3, end : 1
===== while end ===== start : 3
part : 3
***** 왼쪽 파티션 시작 *****
***** 왼쪽 파티션 끝 *****
***** 오른쪽 파티션 시작 *****
***** 오른쪽 파티션 끝 *****
***** 오른쪽 파티션 끝 *****
***** 왼쪽 파티션 끝 *****


최초 왼쪽 파티션(0, 1, 2, 3) 정렬 완료


***** 오른쪽 파티션 시작 *****
최초 start : 4, end : 9, pivot : 5
===== while start =====
end : 9
end : 8
end : 7
swap 수행 전 start : 4, end : 6
[0, 1, 2, 3, 5, 4, 7, 8, 6, 9]
swap 수행 후 start : 5, end : 5
start : 6
===== while end ===== start : 6
part : 6
***** 왼쪽 파티션 시작 *****
최초 start : 4, end : 5, pivot : 5
===== while start =====
swap 수행 전 start : 4, end : 5
[0, 1, 2, 3, 4, 5, 7, 8, 6, 9]
swap 수행 후 start : 5, end : 4
===== while end ===== start : 5
part : 5
***** 왼쪽 파티션 시작 *****
***** 왼쪽 파티션 끝 *****
***** 오른쪽 파티션 시작 *****
***** 오른쪽 파티션 끝 *****
***** 왼쪽 파티션 끝 *****
***** 오른쪽 파티션 시작 *****
최초 start : 6, end : 9, pivot : 8
===== while start =====
start : 7
end : 9
swap 수행 전 start : 7, end : 8
[0, 1, 2, 3, 4, 5, 7, 6, 8, 9]
swap 수행 후 start : 8, end : 7
===== while end ===== start : 8
part : 8
***** 왼쪽 파티션 시작 *****
최초 start : 6, end : 7, pivot : 7
===== while start =====
swap 수행 전 start : 6, end : 7
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
swap 수행 후 start : 7, end : 6
===== while end ===== start : 7
part : 7
***** 왼쪽 파티션 시작 *****
***** 왼쪽 파티션 끝 *****
***** 오른쪽 파티션 시작 *****
***** 오른쪽 파티션 끝 *****
***** 왼쪽 파티션 끝 *****
***** 오른쪽 파티션 시작 *****
최초 start : 8, end : 9, pivot : 8
===== while start =====
end : 9
swap 수행 전 start : 8, end : 8
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
swap 수행 후 start : 9, end : 7
===== while end ===== start : 9
part : 9
***** 왼쪽 파티션 시작 *****
***** 왼쪽 파티션 끝 *****
***** 오른쪽 파티션 시작 *****
***** 오른쪽 파티션 끝 *****
***** 오른쪽 파티션 끝 *****
***** 오른쪽 파티션 끝 *****
***** 오른쪽 파티션 끝 *****
0 1 2 3 4 5 6 7 8 9 

*/

2. 시간복잡도(O(N^2))

• 평균적인 퀵 정렬의 시간 복잡도는 O(N * logN)
• 데이터가 정렬이 되어 있거나 역순으로 정렬되어 있는 경우의 시간복잡도는 O(N^2)
• 퀵 정렬은 값에 따라서 편향되게 분할할 가능성이 있음 → 최악의 시간복잡도 : O(N^2)

→ 빅오표기법은 최악이 수행시간을 나타낼 때 사용하는 표기법이므로 퀵 정렬의 시간복잡도는 O(N^2)