[hackerrank] Quicksort 1 - Partition - JAVA

[문제 링크]

https://www.hackerrank.com/challenges/quicksort1/problem?isFullScreen=true

Quicksort 1 - Partition | HackerRank

 

public class QuickSort1Partition {
    public static void main(String[] args) {

        List<Integer> arr = Arrays.asList(4, 5, 3, 7, 2);
        List<Integer>answer = quickSort(arr);

        output(answer);

    }

    public static List<Integer> quickSort(List<Integer> arr) {
        //입력된 리스트가 1보다 작으면 그 리스트를 그대로 반환
        if (arr.size() < 2) {
            return arr;
        }
        int pivot = arr.get(0);

        List<Integer> left = new ArrayList<>();
        List<Integer> right = new ArrayList<>();
        List<Integer> equal = Arrays.asList(pivot);


        for (Integer integer : arr) {
            if (pivot > integer) {
                left.add(integer);
            } else if (integer > pivot) {
                right.add(integer);
            }
        }

        //나누어진 서브리스트를 재귀 정렬
        List<Integer> sortedLeft = quickSort(left);
        List<Integer> sortedRight = quickSort(right);

        List<Integer> answer = new ArrayList<>();
        answer.addAll(sortedLeft);
        answer.addAll(equal);
        answer.addAll(sortedRight);

        return answer;

    }

    public static void output(List<Integer> arr) {
        for (Integer integer : arr) {
            System.out.print(integer + " ");
        }
        System.out.println();
    }
}

퀵 정렬을 구현하는 문제.

퀵 정렬의 시간복잡도는 보통 nlogn으로 (비교하고자 하는 원소의 최대 수는 n-1이고, 분할단계의 수가 n을 2로 나누니까 logn. 상수항을 빼고 계산하니 nlogn) 빠른 성능을 가지는 정렬 알고리즘이다.

퀵 정렬은 분할 정복(divide and conquer) 방법을 사용하여 정렬을 수행한다.

분할 정복 방법
문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.

먼저 리스트에서 피벗(pivot)을 선택한 후, 피벗을 기준으로 리스트를 두 개의 서브리스트로 분할한다.

피벗을 기준으로 분할한 후, 피벗을 제외한 왼쪽 서브리스트는 모두 피벗보다 작거나 같은 원소로 이루어지고, 오른쪽 서브리스트는 모두 피벗보다 큰 원소로 이루어진다.

이후, 분할된 두 서브리스트에 대해 동일한 방법을 재귀적으로 적용하면서 정렬을 계속한다.

이렇게 서브리스트의 크기가 0이나 1이 될 때까지 분할하고, 이를 다시 병합하여 정렬된 전체 리스트를 얻게 된다.