[알고리즘] Quick Sort 이론 및 구현: List

배열이 주어졌을 때, 임의로 기준값을 정하여
기준보다 작은 수와 큰 수들의 집합으로 쪼개는 과정을
각 집합이 더이상 쪼개질 수 없을 때까지 반복한 후,
나누어진 집합들을 각각 정렬한 후 병합하는 알고리즘

Pivot?
noun. a fixed point supporting something that turns or balances
명사. 변하거나 균형을 맞추는 것들을 받쳐주는 고정된 지점

Quick Sort 적용 과정

1단계: 대소비교를 통해 세 개 내지는 두 개의 리스트로 분리,
각 리스트 내에는 기준값보다 크고 작은 수들이 모여 있도록 함.

import java.util.ArrayList;
import java.util.List;

public class QuickSort {
    /* 1. 배열의 중간(크기 / 2)에 있는 원소를 기준 값으로 잡는다.
     * 2. 모든 원소들과 비교하면서 기준 값보다 작은 값들은 left 에, 큰 값들은 right 에 넣는다.
     * 3. 정렬해야 하는 배열의 크기는 계속해서 반으로 줄게 된다. (재귀 또는 List 내 원소 교환) */

    public void divideIntoThree(int[] arrToBeSorted) {
        int pivotIdx = arrToBeSorted.length / 2;
        int pivot = arrToBeSorted[pivotIdx];
        List<Integer> right = new ArrayList<>();
        List<Integer> left = new ArrayList<>();
        List<Integer> centre = new ArrayList<>();

        for (int i : arrToBeSorted) {
            if (pivot < i) right.add(i);
            else if (pivot > i) left.add(i);
            else centre.add(i);
        }

        System.out.print(left + "\n" + centre + "\n" + right);
    }

    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        int[] testArr = {20, 18, 5, 19, 40, 50, 5, 25};
        quickSort.divideIntoThree(testArr);
    }
}

여기에 보면 pivot 도 리스트에 담았다. 이는 pivot 이 기준값이 되면서 동시에 중복된 수인 경우 를 고려하여 사용한 방식이다. 기준값과 중복되는 값은 centre에 pivot 과 함께 저장될 것이다. centre은 정렬할 필요도 없고, 위치가 바뀔 일도 없다.

 

2단계: 재귀 호출 도입

package algorithms.quicksort;

import java.util.ArrayList;
import java.util.List;

public class QuickSort {
    /* 1. 배열의 중간(크기 / 2)에 있는 원소를 기준 값으로 잡는다.
     * 2. 모든 원소들과 비교하면서 기준 값보다 작은 값들은 left 에, 큰 값들은 right 에 넣는다.
     * 3. 정렬해야 하는 배열의 크기는 계속해서 반으로 줄게 된다. (재귀 또는 List 내 원소 교환)
     * 질문: 만약 중복되는 수가 기준값이 되었다면 분류할 수 없는데 어떤 방법을 써서 정렬할 수 있을까?
     *  답: 어차피 중복되는 수 두개는 붙어있어야 하므로 두 개가 한 곳에 같이 있어도 상관 없다. */

    public List<Integer> divideIntoThree(List<Integer> arrToBeSorted) {
        if (arrToBeSorted.size() <= 1 || arrToBeSorted.stream().distinct().count() == 1)
            return arrToBeSorted; // 더 이상 쪼갤 수 없을 때 현재 리스트를 리턴한다.

        int pivotIdx = arrToBeSorted.size() / 2;
        int pivot = arrToBeSorted.get(pivotIdx);
        List<Integer> left = new ArrayList<>();
        List<Integer> right = new ArrayList<>();
        List<Integer> centre = new ArrayList<>();

        for (int i : arrToBeSorted) {
            if (pivot < i) right.add(i);
            else if (pivot > i) left.add(i);
            else centre.add(i);
        }

        // 리턴할 때 재귀적으로 나누어진 배열들을 더 쪼개고, 마지막에 병합함으로서 정렬한다. 이 부분을 외부 메소드로 분리해도 된다.
        List<Integer> processed = divideIntoThree(left); // 결국 원소 하나의 리스트가 될 때까지 쪼개고 병합한 후에 processed 에 결과가 할당된다.
        System.out.println("left:\n" + processed);
        processed.addAll(divideIntoThree(centre)); // 정렬된 중간 리스트를 더한다.
        System.out.println("centre:\n" + processed);
        processed.addAll(divideIntoThree(right)); // 정렬된 오른쪽 리스트를 더한다.
        System.out.println("right:\n" + processed);
        System.out.println("--------------------");
        return processed;
    }

    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        List<Integer> testArr = List.of(20, 18, 5, 19, 40, 50, 5, 25);
        System.out.println(quickSort.divideIntoThree(testArr));
    }
}

BASE CASE (탈출 조건)

중복된 수가 있을 때를 유의해서 조건을 설정해 주어야 한다.

예를 들어, 위 알고리즘에서는 아무리 리스트의 사이즈가 크더라도 모두 같은 수이면 더 이상 정렬할 여지가 없으며,

절대 사이즈가 1보다 작거나 같아질 여지가 없다.

즉, base case 에 도달하지 못하고 무한 루프에 빠지는 문제가 생긴다.
그래서 Base case 에 만일 모든 수가 중복되는 경우에는 더 이상 정렬이 필요하지 않다는 조건을 추가했다.

+ 나중에 알고 보니 내 코드가 centre, 즉 1단계에서 언급한 정렬이 필요없는 pivot 과 중복되는 수의 리스트 또한 재귀적으로 정렬하려고 했던 것이 문제였다. divideIntoThree(centre) 이 아니라 그냥 centre를 addAll 해주면 Base case 를 단순히 1보다 작은 경우에 리턴하는 조건으로만 설정해주어도 오류가 나지 않고 정렬이 된다.
+ 하지만 결국 모든 원소가 같은 리스트는 나타날 가능성이 있고, 밑의 for 문을 들어가지 않고 정렬이 필요 없는 리스트를 한 번 필터링해주는 원래의 조건은 유지하는 것이 효율적인 구현 방법이다.

Q. 컴퓨터는 그럼 재귀를 한 줄을 먼저 다 처리하고 돌아와서 두 번째 줄을 처리할까요??
A. 실험해본다. 재귀는 호출 스택을 사용한다. Stack 은 LIFO 를 따르기 때문에 결국 처음 호출 스택으로 들어간 함수들 (메소드들)이 리턴을 만나 해결되지 않으면 절대 그 이후에 들어간 함수들의 결과값을 낼 수 없다.

그림 1-1 스택 구조로 호출되는 함수

3단계: 리팩토링 - 마지막 병합 부분을 외부 메서드로 분리해서 구현함.

 

import java.util.ArrayList;
import java.util.List;

public class QuickSort {
    /* 1. 배열의 중간(크기 / 2)에 있는 원소를 기준 값으로 잡는다.
     * 2. 모든 원소들과 비교하면서 기준 값보다 작은 값들은 left 에, 큰 값들은 right 에 넣는다.
     * 3. 정렬해야 하는 배열의 크기는 계속해서 반으로 줄게 된다. (재귀 또는 List 내 원소 교환)
     * 질문: 만약 중복되는 수가 기준값이 되었다면 분류할 수 없는데 어떤 방법을 써서 정렬할 수 있을까?
     *  답: 어차피 중복되는 수 두개는 붙어있어야 하므로 두 개가 한 곳에 같이 있어도 상관 없다. */

    // 리턴할 때 재귀적으로 나누어진 배열들을 더 쪼개고, 마지막에 병합함으로서 정렬한다. 이 부분을 외부 메소드로 분리해도 된다.
    private List<Integer> merge(List<Integer> left, List<Integer> centre, List<Integer> right) {
        List<Integer> processed = divideIntoThree(left); // 결국 원소 하나의 리스트가 될 때까지 쪼개고 병합한 후에 processed 에 결과가 할당된다.
        System.out.println("left:\n" + processed);
        processed.addAll(centre); // 정렬된 중간 리스트를 더한다.
        System.out.println("centre:\n" + processed);
        processed.addAll(divideIntoThree(right)); // 정렬된 오른쪽 리스트를 더한다.
        System.out.println("right:\n" + processed);
        System.out.println("--------------------");
        return processed;
    }


    public List<Integer> divideIntoThree(List<Integer> arrToBeSorted) {
        if (arrToBeSorted.size() <= 1 || arrToBeSorted.stream().distinct().count() == 1)
            return arrToBeSorted; // 더 이상 쪼갤 수 없을 때 현재 리스트를 리턴한다.

        int pivotIdx = arrToBeSorted.size() / 2;
        int pivot = arrToBeSorted.get(pivotIdx);
        List<Integer> left = new ArrayList<>();
        List<Integer> right = new ArrayList<>();
        List<Integer> centre = new ArrayList<>();

        for (int i : arrToBeSorted) {
            if (pivot < i) right.add(i);
            else if (pivot > i) left.add(i);
            else centre.add(i);
        }
        return merge(left, centre, right);
    }

    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        List<Integer> testArr = List.of(20, 18, 5, 19, 40, 50, 5, 25);
        System.out.println(quickSort.divideIntoThree(testArr));
    }
}

 

! 배운 사실

• 알고리즘을 풀 때는 먼저 내가 짠 로직이 어떤 값을 출력할지 생각해볼 필요가 있다.