퀵 정렬(Quick Sort) 알고리즘

퀵 정렬(Quick Sort) 알고리즘이란?

중앙 값 정렬 방식을 확장해서 개발한 방식.

먼저 배열을 둘로 나눠 두 그룹을 만들고, 그 기준을 피벗(pivot)이라고 한다.

각 그룹에 대해 피벗 설정과 그룹 나눔을 반복하며 모든 그룹이 1명이 되면 정렬을 마친다.

가장 빠른 정렬 알고리즘 중의 하나.

 

사용 방법

1. 임의로 선정된 데이터를 중심으로 데이터를 2등분한다.

2. 각 분리된 부분의 첫 번째 원소를 기준으로 데이터를 분리한다.

3. 이 작업을 계속 반복한다.

 

자바로 구현하기

static void quickSort(int[] a, int left, int right) {
    //왼쪽 포인터를 왼쪽 끝에, 오른쪽 포인터를 오른쪽 끝에 두고 피벗을 설정한다.
    int pl = left;
    int pr = right;
    int x = a[(pl+pr)/2];
    
    do {
        //피벗보다 작아야하는 영역(왼쪽)에서 1씩 인덱스를 증가시키며
        //피벗보다 큰 값을 찾는다.
        while(a[pl]<x) {
            pl++;
        }
        //피벗보다 커야하는 영역(오른쪽)에서 1씩 인덱스를 감소시키며
        //피벗보다 작은 값을 찾는다.
        while(a[pr]>x) {
            pr--;
        }
        //일단 do로 포인터를 옮겼기 때문에 걸러주는 작업.
        if(pl<=pr) {
            //후위 연산자 꼭 쓰기!!!
            swap(a, pl++, pr--);
        }
    } while(pl<=pr);

    //아직 왼쪽 포인터가 오른쪽 끝에 닿지 못했을 경우
    if(pl < right) {
        quickSort(a, pl, right);
    }
    
    //아직 오른쪽 포인터가 왼쪽 끝에 닿지 못했을 경우
    if(left < pr) {
        quickSort(a, left, pr);
    }
    
}

 

lktprogrammer.tistory.com/33

04 정렬 알고리즘 - 퀵 정렬 (Quick Sort)