[정렬] Quick Sort

퀵 정렬이란?

  퀵 정렬은 배열 중 적당한 수 (Pivot)을 골라 그 기준으로 그 수보다 작은 원소와 큰 원소로 나누어서 분류하는 것.

 

퀵 정렬 아이디어

  비어있는 배열 || 원소가 1개인 배열   ㅡ   정렬을 할 필요가 없음.

  원소가 2개 라면?    ㅡ  아주 쉽다. 그냥 두 개의 위치(swap)를 바꾸기만 하면 된다.

  원소가 3개 이상이라면?  

  우선 원소가 3개라고 가정해보자 { 4, 3 , 1 } 여기서 우리가 4(Pivot)를 선택한다고 하자.

  1 . 왼쪽 배열에 작은 원소를 나열해보자 { 3 , 1 } + Pivot + 오른 배열에 큰 원소를 나열해보자 { X } 

       이렇게 Pivot에 의해 큰 원소와 작은 원소로 나뉘는 것을 분할(Partitioning) 이라 한다.

 

  2 . 이제 왼쪽 배열과 오른쪽 배열을 보자.

      왼쪽 배열만 본다면 { 3, 1 } 로 다시 3을 기준(Pivot)으로 분할을 한다면 { 1 } + Pivot +{X} 이 될 것이다.

      오른쪽 배열은 존재 하지 않으니 생각을 안해도 된다.

그림으로 나타내 본다면  

Java 구현 

private List<Integer> quickSort(List<Integer> arr)
    {
        if (arr.size() <= 1) return arr;
        int pivot = arr.get(arr.size() / 2);

        List<Integer> lesserArr = new LinkedList<>();
        List<Integer> equalArr = new LinkedList<>();
        List<Integer> greaterArr = new LinkedList<>();

        for (int num : arr) {
            if (num < pivot) lesserArr.add(num);
            else if (num > pivot) greaterArr.add(num);
            else equalArr.add(num);
        }

        return Stream.of(quickSort(lesserArr), equalArr, quickSort(greaterArr))
                .flatMap(Collection::stream)
                .collect(Collectors.toList());
    }

위의 구현은 간결하고 이해하기 쉽지만 매번 재귀 호출될 때 마다 새로운 리스트를 생성하여 리턴하기 때문에 메모리 사용 측면에서 비효율적이다.

 

Java 최적화 구현 

 private static void sort(int[] arr, int low, int high) {
        if (low >= high) return;

        int mid = partition(arr, low, high);
        sort(arr, low, mid - 1);
        sort(arr, mid, high);
    }

    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[(low + high) / 2];
        while (low <= high) {
            while (arr[low] < pivot) low++;
            while (arr[high] > pivot) high--;
            if (low <= high) {
                swap(arr, low, high);
                low++;
                high--;
            }
        }
        return low;
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }