퀵 정렬(Quick Sort)

Algorithmday_4 정리 (2021.12.01 수요일)

퀵 정렬(Quick Sort)

• 분할 정복 정렬 방법 중 하나
• 전체 리스트를 2개의 부분 리스트로 분할하고
• 각각의 서브 리스트를 다시 퀵 정렬로 정렬
  • 기준 값보다 큰 값들은 오른쪽으로, 작은 값들은 왼쪽으로 재 배열
• 정렬 방법
  • 전체 리스트에서 한 원소를 기준 값(pivot)으로 선정
  • 피벗을 기준으로 두 개의 서브 리스트로 분할
    • 왼쪽 : 피벗보다 작은 값의 원소들로 구성
    • 오른쪽 : 피벗보다 크거나 같은 값의 원소들로 구성
  • 각각의 파티션(서브 리스트)에 대해 다시 퀵 정렬을 순환 적용
    • 피벗 선정 및 파티션 분할
• 퀵 정렬 수행 순서
• 피벗(pivot) : 가장 왼쪽 숫자를 피벗으로 선정
• 두 개의 변수 : low와 high(이동)
  • low는 왼쪽에 위치
  • high는 오른쪽에 위치
• low : 오른쪽으로 이동하면서 피벗 보다 큰 숫자를 찾음
  • 피벗 보다 작으면 통과, 큰 숫자를 찾으면 정지
• high : 왼쪽으로 이동하면서 피벗 보다 작은 숫자를 찾음
  • 피벗 보다 크면 통과, 작은 숫자를 찾으면 정지
• 정지된 위치의 숫자들 서로 교환
• low와 high가 교차하면 종료. high와 pivot 교환

퀵 정렬 예제 코드

• QuickSort.java

public class QuickSort {
    public static void main(String[] args) {
        int [] arr = {8,5,4,6,3,1,2,7,9};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
    static void quickSort(int[] arr, int low, int high) {
        if(low >= high) {
            return;
        }
        int pivot = low;
        int i = low + 1;
        int j = high;
        int temp;
        while(i <= j) { // 교차할 때 까지 반복 j가 i보다 크면 while문 종료
            while(i <= high && arr[i] < arr[pivot]) { // 피벗보다 큰 값을 만날 때 까지 반복
                i++;
            }
            while (j > low && arr[j] >= arr[pivot]) { // 피벗보다 작은 값을 만날 때 까지 반복
                j--;
            }
            if(i > j) { // 교차한 상태가 되면 피복과 j 교환
                temp = arr[j];
                arr[j] = arr[pivot];
                arr[pivot] = temp;
            }
            else { // i와 j값 교환
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        quickSort(arr, low, j-1);
        quickSort(arr, j+1, high);
    }
}