[알고리즘] 퀵정렬 (Quick Sort) Java Example

 

퀵 정렬 알고리즘

퀵 정렬(Quick Sort) 알고리즘은 원소들 중에서 특정한 기준을 피봇(Pivot)라고 부르며

피봇보다 작은 원소는 왼쪽으로 큰 원소는 오른쪽으로 이동한다.

초기 세팅 변수 left = 0 , rigth = 배열 길이-1 , pivot = (left+right)/2 (피봇은 중앙값으로 세팅함)

 

public class Quick_Sort {
 
    public static void main(String[] args) {
        
        int[] arr = { 10, 50, 80, 90, 70 };
        
        quick_Sort(arr, 0, arr.length - 1);
        output(arr);
    }
 
    private static void quick_Sort(int[] arr, int start, int end) {
        
        int left = start;
        int right = end;
        /*pivot을 중앙 값으로 셋팅*/
        int pivot = arr[(left + right) / 2];
 
        do {
            while (arr[left] < pivot) {
                left++;
            }
            while (arr[right] > pivot) {
                right--;
            }
 
            if (left <= right) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
                left++;
                right--;
            }
 
        } while (left <= right);
 
        if (start < right) {
            quick_Sort(arr, start, right);
 
        }
        if (end > left) {
            quick_Sort(arr, left, end);
        }
    }
 
    private static void output(int[] arr) {
        
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

 

퀵 정렬 성능 향상 방법

• 작은 데이터 구간에는 삽입 정렬을 사용하여 퀵 정렬의 재귀의 깊이를 줄여 스택 사용을 줄여 준다
• 비 재귀 구현
• 난수(Random) 분할 > Worst 경우 인 정렬된 배열과 역순 배열일 때 문제를 해결하기 위해 난수로 선택한다
• 메디안 퀵 정렬(Median of Three QuickSort) - 세 값(처음, 가운데, 끝)의 중윗값을 찾아 Pivot으로 선택한다