[JAVA] 퀵정렬(Quick Sort) 개념과 코드 구현

퀵정렬(Quick Sort)은 가장 빠른 정렬 알고리즘 중 하나로 사용되는 정렬 알고리즘이다.

다른 원소와 비교만으로 정렬을 수행하는 비교정렬이다.

값의 정렬이후 순서가 초기 순서와 달라질 수 있는 불안정 정렬이고, 분할 정복 알고리즘에 속한다.

 

구분	최악 시간복잡도	최선 시간복잡도	평균 시간복잡도	공간복잡도(메모리)	안정성
퀵정렬	O(N^2)	O(n log n)	O(n log n)	평균적으로 O(log n), 최악의 경우 O(n)	N

 

알고리즘

 

1. 리스트 가운데에서 하나의 원소를 고른다. 이 원소를 피벗(Pivot)이라고 한다.
2. 피벗 앞에는 피벗보다 작은 모든 원소가 오고 피벗 뒤에는 피벗보다 큰 모든 원소가 오도록 리스트를 둘로 나눈다.
3. 분할된 각 리스트에 대해 피벗 설정과 그룹 나눔을 반복하여 모든 그룹 원소수가 1이 되면 정렬을 마친다.

 

좌측 그림과 같이 특정 피벗을 기준으로 피벗보다 작은 값을 피벗 앞에,

피벗보다 큰 값은 피벗 뒤로 이동시킨다.

그러면 피벗을 기준으로 좌측과 우측 두개의 그룹이 생기는데

그룹 내에서 동일한 과정을 반복해서 쪼개진 그룹의 크기가 1이 되면 모든 정렬이 완료된다.

 

 

소스코드[Ver1]

// 1. 전체를 총괄하는 메서드 (재귀함수 호출지점)
public static int[] quickSort(int[] arr) {
    return doQuickSort(arr, 0, arr.length - 1);
}

// 2. 재귀적으로 정렬해주는 메서드
public static int[] doQuickSort(int[] arr, int left, int right) {
    // 양 끝에 커서를 두고, 안쪽으로 이동하면서 피벗과의 값을 비교함
    int pivot = arr[(left + right) / 2];
    int leftCursor = left;
    int rightCursor = right;

    // 왼쪽 커서가 오른쪽 커서보다 커질때까지 반복
    while (leftCursor <= rightCursor) {

        // 왼쪽 커서가 가리키는 값이 피벗보다 커질때까지 커서 오른쪽으로 이동
        while (arr[leftCursor] < pivot) leftCursor++;
        // 오른쪽 커서가 가리키는 값이 피벗보다 작아질때까지 커서 왼쪽으로 이동
        while (arr[rightCursor] > pivot) rightCursor--;

        // 큰값이 작은 값보다 왼쪽에 있다면 두 요소 교환
        if (leftCursor <= rightCursor) swap(arr, rightCursor, leftCursor);

        // 교환되고나면 그 다음 커서부터 다시 값을 비교하면 되므로 커서 이동시켜줌
        leftCursor++;
        rightCursor--;
    }

    // 재귀호출. rightCursor 앞부분과 leftCursor 뒷부분도 다시 정렬 수행.
    if (left < rightCursor) doQuickSort(arr, left, rightCursor);
    if (leftCursor < right) doQuickSort(arr, leftCursor, right);

    return arr;
}

// 3. 배열 안에서 인자를 교환해주는 메서드
public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

 

소스코드[Ver 2]

// 1. 전체 기능을 총괄하는 메서드. 실제 비즈니스 메서드를 호출하는 지점 (파라미터로 배열 하나만 받아옴)
public static int[] quickSort(int[] arr) {
    if (arr.length == 0) return arr;

    return sort(arr, 0, arr.length - 1);
}

// 2. 배열의 중앙에 위치한 값을 기준으로 양쪽으로 구분하고 그 중앙 인덱스를 리턴해주는 메서드
public static int partition(int[] arr, int left, int right) {
    // 배열 중앙의 피벗값을 추출함
    int pivot = arr[(left + right) / 2];

    // 커서(양끝 인덱스)를 이동하면서 피벗값과 비교해서 피벗보다 작은것은 왼쪽에, 큰것은 오른쪽에 오도록 정렬해줌
    // 오른쪽 인덱스가 왼쪽 인덱스보다 작아지면 모든 경우를 검토한것이므로 반복문을 종료함
    while (left <= right) {
        // 왼쪽 요소중에 피벗보다 큰 값이 나올때까지 왼쪽 커서(인덱스)를 우측으로 이동시킴
        while (arr[left] < pivot) left++;
        // 오른쪽 요소중에 피벗보다 작은 값이 나올때까지 오른쪽 커서(인덱스)를 좌측으로 이동시킴
        while (arr[right] > pivot) right--;

        // 커서 이동이 끝난 후 왼쪽 인덱스가 오른쪽 인덱스보다 작거나 같으면 해당 인덱스 요소를 교환해준다.
        // 요소를 교환한 후에는 각자 그 다음 요소부터 비교하면 되므로 커서를 이동시킨다.
        if (left <= right) swap(arr, left, right);
        left++;
        right--;
    }

    return left;
}

// 3. partition 메서드를 사용해 지귀적으로 정렬해주는 메서드
private static int[] sort(int[] arr, int left, int right) {
    int partition = partition(arr, left, right);
    // 파티션을 기준으로 왼쪽 요소가 남아있는 경우 좌측을 정렬해줌
    if (left < partition - 1) arr = sort(arr, left, partition - 1);
    // 파티션을 기준으로 오른쪽 요소가 남아있는 경우 우측을 정렬해줌
    if (partition < right) arr = sort(arr, partition, right);

    return arr;
}

// 4. 배열에서 요소 arr[i]와 arr[j]의 자리를 바꿔주는 메서드
public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}