[JAVA] 퀵정렬(Quick Sort)

퀵정렬(Quick Sort)

정렬 알고리즘 중 가장 효율적이고 빠른방식 입니다.

동작방식(아이디어)은 아래와 같습니다.

1. 기준점이 되는 pivot을 구한다.

2. pivot을 기준으로 left(pviot보다 작은 값) 리스트와 right(pivot 보다 큰 값)리스트를 구합니다.

3. 나눠진 left와 right 리스트를 정렬이될 때까지 분할처리 합니다. => 재귀사용(자기자신을 호출)

(설명 및 그림참고 : 네이버 지식백과(퀵정렬))

퀵정렬은 버블 정렬이나 삽입 정렬보다 훨씬 더 효율적인 성능을 발휘합니다. 퀵정렬의 평균 시간복잡도는 O(nlogn)이며, 최악의 경우에는 여전히 O(n^2)의 시간복잡도를 갖습니다. 이 성능차이는 pivot의 선택에 따라 좌우되게 되는데, 아래코드와 같이 가장앞에 있는 수를 pivot으로 잡을 경우, 리스트가 역순으로 정렬되어 있다면 최악의 시간복잡도를 갖게됩니다. pivot은 리스트의 중간숫자로 잡는 것이 가장 효율적인 방법입니다.

public List<Integer> quickSort(List<Integer> numbers){
        if(numbers.size() < 2)
            return numbers;
        
        final Integer pivot = numbers.get(0);
        final List<Integer> lower = new ArrayList<>();
        final List<Integer> higher = new ArrayList<>();
        
        for(int i=1; i<numbers.size(); i++) {
            if(numbers.get(i) < pivot) {
                lower.add(numbers.get(i));
            }else {
                higher.add(numbers.get(i));
            }
        }
        
        final List<Integer> sorted = quickSort(lower);
        sorted.add(pivot);
        sorted.addAll(quickSort(higher));
        
        return sorted;
    }