[Java] 고급 정렬 - 퀵 정렬이란? (개념 / 예제 / 알고리즘 분석)

서론

---

이전 병합 정렬에 이어 고급 정렬에 속한 퀵 정렬, 흔히 정렬 알고리즘의 꽃이라 불리는 이 포스팅을 마지막으로 정렬 알고리즘에 대해 마무리하려합니다. 바로 알아보겠습니다.

 

---

 

퀵 정렬(Quick Sort)이란?

---

 

분할 정복 알고리즘 중 하나인 고급 정렬 알고리즘이며, 평균적으로 매우 빠른 수행 속도를 갖고 있는 정렬 방법을 말한다. 퀵 정렬의 구현 방식을 알아보면 다음과 같다.

 

구현 방식

1. 기준점(Pivot)을 정해서, 기준점보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right)으로 모으는 함수를 작성한다.
2. 각 왼쪽(left)과 오른쪽(right) 배열은 재귀용법을 사용하여 다시 동일 함수를 호출하여 위 작업을 반복한다.
3. 함수는 왼쪽(left) + 기준점(pivot) + 오른쪽(right)을 리턴하는 형식을 만든다.

 

퀵 정렬을 한번에 작성하기 앞서 구조의 이해를 위해 구현 방식 1번에 해당하는 로직을 먼저 구현해보자.

 

Q. 1번 구현 방식 문제

ArrayList의 값을 맨 앞(Pivot)을 기준으로 작은 데이터는 leftArray 변수에, 큰 데이터는 rightArray 변수에 넣어보고 leftArray, pivot, rightArray 순으로 출력할 것.

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

        Integer[] array = {5, 7, 3, 1, 3};
        ArrayList<Integer> list = new ArrayList<Integer>(Arrays.asList(array));
        split(list);
    }

    private static void split(ArrayList<Integer> list) {
        if(list.size() <= 1){
            return;
        }

        int pivot = list.get(0);
        ArrayList<Integer> leftArray = new ArrayList<Integer>();
        ArrayList<Integer> rightArray = new ArrayList<Integer>();

        for(int i = 1; i < list.size(); i++){
            if(list.get(i) > pivot){
                rightArray.add(list.get(i));
            }else {
                leftArray.add(list.get(i));
            }
        }

        ArrayList<Integer> mergedArray = new ArrayList<Integer>();
        mergedArray.addAll(leftArray);
        mergedArray.addAll(Arrays.asList(pivot));
        mergedArray.addAll(rightArray);

        System.out.println(mergedArray);

    }
}

문제에서 주어진 내용은 간단하다. 주어진 array 값을 pivot을 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 넣은 후 해당 배열을 다시 하나의 리스트에 합쳐서 출력하라는 말이였다.

 

그래서 필자는 pivot을 0번째 인덱스로 지정하고 for문을 돌려서 작은값은 leftArray, 큰 값은 rightArray로 넣어준 후 새로운 리스트인 mergedArray를 생성하여 addAll 함수를 통하여 배열을 추가하여 출력해주었다.

 

이제 위의 로직을 가지고 퀵 정렬을 구현해보자.

 

퀵 정렬 구현

public class quicksort {
    public static void main(String[] args) {
        ArrayList<Integer> list = new ArrayList<>();

        for(int i=0; i<20; i++)
            list.add((int)(Math.random() * 100));

        System.out.println(sort(list));
    }

    private static ArrayList<Integer> sort(ArrayList<Integer> list) {
        if(list.size() <= 1){
            return list;
        }

        int pivot = list.get(0);
        ArrayList<Integer> leftArray = new ArrayList<Integer>();
        ArrayList<Integer> rightArray = new ArrayList<Integer>();

        for(int i = 1; i < list.size(); i++){
            if(list.get(i) > pivot){
                rightArray.add(list.get(i));
            }else {
                leftArray.add(list.get(i));
            }
        }

        ArrayList<Integer> mergedArray = new ArrayList<Integer>();
        mergedArray.addAll(sort(leftArray));
        mergedArray.addAll(Arrays.asList(pivot));
        mergedArray.addAll(sort(rightArray));

        return mergedArray;
    }
}

출력 값

위와 같이 20개의 랜덤 값의 list를 생성한 후 Q1에서 작성한 로직을 활용하여 퀵 정렬을 구현해보았다. 이 퀵 정렬은 다른 기본 정렬들에 비해 굉장히 빠른 속도를 자랑하지만 운이 안좋으면 최악의 시간 복잡도가 나올 수 있다. 해당 내용은 아래에서 알아보도록 하자.

 

---

 

퀵 정렬 최악의 케이스

알고리즘 분석

---

병합 정렬과 유사하며 기본적으로 시간 복잡도는 O(n log n)을 갖는다.

• 그러나,  최악의 경우에는 다르다. (이미지 참고)
  • 이미 정렬된 배열에서 pivot의 값이 가장 크거나, 작은 경우 큰 시간이 소요된다.
    • 그 이유는 모든 데이터를 비교해야하는 상황이 생기기 때문이다.
  • 그럴 경우 시간 복잡도는 O(n^2)가 된다.

 

---

 

마무리

---

상황에 맞게 좋은 정렬 방식을 사용할 수 있도록 꾸준한 학습이 필요한 것 같습니다. 이렇게 정렬 알고리즘에 대해 마무리 지어보겠습니다. 감사합니다.