고급정렬 - QuickSort (퀵정렬)

정렬 과정

https://ko.wikipedia.org/wiki/퀵_정렬

퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 리스트를 정렬한다.

 

리스트의 길이가 1 이하이면 이미 정렬된 것으로 본다. 그렇지 않은 경우에는
분할(divide): 임의의 피벗을 지정하여 피벗보다 큰 원소와 작은거나 같은 원소, 두 부분 리스트로 나눈다.

결합(combine): 작은 리스트 - 피벗 - 큰 리스트로 결합한다.
정복(conquer): 두 부분 리스트를 재귀적으로 퀵 정렬을 이용해 정렬한다.
복사(copy): 임시 배열에 저장된 결과를 원래 배열에 복사한다.

재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

 

역시나 분할과 정복 방식이다.

 

구현 코드

package net.jetalab.excercise.quicksort;

import java.util.Scanner;

public class Main {
    public static int[] arr, left, right;

    // 피벗보다 작거나 같은 왼쪽 리스트
    public static int getLeft(int start, int end, int pivot) {
        int idx = 0;

        for (int i = start; i <= end; i++) {
            if (arr[i] <= pivot) left[idx++] = arr[i];
        }

        return idx;
    }

    // 피벗보다 큰 오른쪽 리스트
    public static int getRight(int start, int end, int pivot) {
        int idx = 0;

        for (int i = start; i <= end; i++) {
            if (arr[i] > pivot) right[idx++] = arr[i];
        }

        return idx;
    }

    public static void quickSort(int start, int end) {
        if (start >= end) return;

        int pivot = arr[start];

        int idx = start;
        int leftSize = getLeft(start + 1, end, pivot);
        int rightSize = getRight(start + 1, end, pivot);

        for (int i = 0; i < leftSize; i++) {
            arr[idx++] = left[i];
        }
        arr[idx++] = pivot;
        for (int i = 0; i < rightSize; i++) {
            arr[idx++] = right[i];
        }

        quickSort(start, start + leftSize - 1);
        quickSort(start + leftSize + 1, end);
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        System.out.print("원소의 갯수를 입력해주세요: ");
        int size = scan.nextInt();
        arr = new int[size];
        left = new int[size];
        right = new int[size];

        System.out.print("정렬할 원소를 입력해주세요: ");
        for (int i = 0; i < size; i++) {
            arr[i] = scan.nextInt();
        }

        quickSort(0, size - 1);
        for (int e : arr) System.out.print(e + " ");
    }
}

 

참고 문서

퀵 정렬 - 위키백과, 우리 모두의 백과사전 - https://ko.wikipedia.org/wiki/퀵_정렬