Quick sort Java 코드

Quick sort

특정값을 정해서 이 값보다 작으면 왼쪽 크면 오른쪽으로 정렬한 후 좌우로 재귀적으로 정렬해가는 방법

시간복잡도

최악: n^2

평균: n*log2(n)

재귀 호출 깊이

log2(n)

Java 코드

public class QuickSort {
    int[] arr; //숫자 배열
    
    public QuickSort(int[] _arr){
        arr = _arr; //배열 입력
    }
 
    //sort 함수로 정렬 후
    //low~mid, mid+1~high 각각 정렬하기 위해 재귀 호출
    public void sortAndDivide(int low, int high){
        if(low >= high) return;
        int mid = sort(low, high);
        sortAndDivide(low, mid);
        sortAndDivide(mid+1, high);
    }
 
    //low~high에서 mid값을 기준으로 작은값은 왼쪽 큰값은 오른쪽으로 정렬
    public int sort(int low, int high){
        int pivot = arr[(low+high)/2]; //mid의 값을 pivot으로 정함
        while(low < high){
            while(arr[low] < pivot) low++; //왼쪽에서 pivot 보다 큰값 찾기
            while(arr[high] > pivot) high--; //오른쪽에서 pivot 보다 작은값 찾기
            if(low >= high) break;
            //좌우 값 바꾸기
            int temp = arr[low];
            arr[low] = arr[high];
            arr[high] = temp;
            low++;
            high--;
        }
        return high; //이때 high값을 기준으로 좌우가 분할 정렬된 상태
    }
 
    //배열 출력
    public void printArr(){
        System.out.println(Arrays.toString(arr));
    }
}