퀵 정렬(quick sort) Java 구현

퀵 정렬(quick sort) Java 구현

퀵정렬

• 가장 빠른 알고리즘 중의 하나

순서
1. 피벗 값을 지정한다
2. 피벗을 기준으로 좌측엔 피벗보다 작은값들을, 오른쪽엔 피벗보다 큰 값들이 오게끔 정렬한다
3. 피벗을 기준으로 두 집합으로 나뉘게 되면 각각의 집합에서 퀵 정렬을 똑같이 진행한다(재귀방식)
4. 값이 한개씩 남으면 끝나게 된다.

구현

static void swap(int[] a, int idx1, int idx2){
    int t =a[idx]; 
    a[idx1] = a[idx2]; 
    a[idx2] = t;
}

static void quickSort(int[] a, int left, int right){
    int pl = left; // 왼쪽 커서
    int pr = right; //오른쪽 커서
    int x = a[(pl + pr)/2]; // 피벗(보통 중간값)

    do{
        while(a[pl] < x ) pl++; // a[pl]이 피벗보다 큰 값에 마주하는 순간 탈출
        while(a[pr] > x) pr++; //a[pr]이 피벗보다 작아지는 값을 마주하는 순간 탈출
        if(pl <= pr) swap(a, pl, pr); //커서가 서로 지나치기 전인지 확인
    }while(pl <= pr); // 보통 여기서 pass1이 끝남

    if(left < pr) quickSort(a, left, pr);
    if(pl < right) quickSrot(a, pl, right);
    //pl은 피벗+1, pr은 피벗-1에 위치해있을 것이니 피벗을 기준으로 두 집단을 나누어서 정렬 진행
}

시간 복잡도 O(nlogn), 최악의 경우에는 O(n2) ==> 피벗값이 끝값일 경우