Quick Sort

Quick sort의 목적

정렬을 위한 알고리즘이다.

Quick sort의 핵심 아이디어

1. pivot을 선택한다.

2. 선택한 pivot을 기준으로 pivot보다 작은 값과 큰 값으로 분리한다.

3. 나눠진 2개의 배열에 대하여 1,2의 과정을 재귀적으로 수행한다.

Quick sort의 동작 원리

위의 핵심 아이디어 중에서 퀵 소트에서 눈여겨 봐야 할 부분은

2. pivot보다 작은 값과 큰 값으로 분리하는 과정이다.

2번 과정에 대한 자세한 설명은 소스를 쉽게 구할 수 있으니 찾아보자.

이 글에서는 개인적으로 헷갈린 부분과 이를 이해한 과정만 쓰겠다.

개인적으로, "pivot보다 작은 값과 큰 값으로 분리" 하는 과정을 구현 할 때에 있어서 가장 헷갈렸던 부분은 "pivot이랑 같은 값" 에 대한 처리였다. 처음에는 2번 과정을 마무리 했을 때 pivot과 크기가 같은 값이 아래의 [1]과 같이 가운데 부분에 붙어 있어야 한다고 생각했다.

하지만, Quick Sort에서 2번 과정을 수행하기 위한 목적은 결국은 2개의 array로 쪼개기 위함이다. 즉, pivot과 크기가 같은 값은 어디에 있든지 상관이 없는 것이다. 중요한 것은 pivot보다 확실히 작은 값과 큰 값을 완벽하게 분리해 내는 것이다. 즉, 아래의 2와 같이 pivot과 크기가 같은 값은 왼쪽에 있든 오른쪽에 있든, 어차피 재귀적으로 수행하다보면 크기 순으로 정렬 될 것이기 때문에 상관이 없다는 것을 알 수 있었다.

pivot : 5

2번 과정을 수행 한 이후 array의 모습 : [3,2,5,5,5,6,7] - [1]

2번 과정을 수행 한 이후 array의 모습 : [5,2,3,5,6,7,5] - [2]

이를 구현한 코드는 다음과 같다.

public int partition(int[] arr ,int l, int r){ // l <= range <= r
        if(r - l < 1) return l;
        // 정렬할 arr의 크기가 1이라면 그냥 반환.

        int mid = (l + r) / 2;
        int pivot = arr[mid];

        // 포인터 만들기
        int lPtr = l;
        int rPtr = r;

        while(true){

            while(lPtr < rPtr && arr[lPtr] < pivot) lPtr++;
            while (lPtr < rPtr &&  arr[rPtr] > pivot) rPtr--;

            if(lPtr > rPtr) break;

            int temp = arr[lPtr];
            arr[lPtr] = arr[rPtr];
            arr[rPtr] = temp;

            lPtr++;
            rPtr--;
        }

        return lPtr;
    }

Quick sort의 장점

병합 정렬의 가장 큰 장점으로는 in-place sort 라는 점이다.

inplace-sort는 쉽게 말해서 정렬 과정에서 추가로 메모리 공간이 필요하지 않은 정렬 방식을 말한다.

이러한 방식으로 정렬을 하게 되면, cache-hit rate 이 높아져서 속도가 더 빨라지게 된다. - [3]

( [3]에 대한 설명이 이해가 가지 않는다면, Locality/Caching에 대한 개념을 알아야한다. )

Quick sort의 단점

1) 최악의 경우 시간 복잡도가 O(N^2)이 된다.

만약 배열이 오름 차순으로 정렬 되어있고 해당 배열의 첫번째 값을 pivot으로 선택한다고 한다면,

재귀의 깊이는 logN이 아닌 N이 될 것이다.

따라서, 최악의 경우 시간 복잡도는 N^2이 된다.

2) stable-sort가 아니다.

Quick sort를 공부하며 느낀점

1. 알고리즘이 가진 특성과 그러한 특성을 잘 살리기 위해서 구현상 주의 해야 할 점들을 같이 알아두어야 한다.

• Quick Sort이 경우 pivot 보다 큰 값과 작은 값으로 분류하는 과정을 올바르게 사용해야 in-place sort 라는 장점을 살릴 수 있다. <- 해당 내용은 바킹독 님의 강의에 나와있다. 참고하자.

Source Code

내 소스 코드

Reference

Quick sort의 아이디어-> 전반적인 Quick Sort에 대한 자세한 설명도 있음.

바킹독 님의 강의 -> 강추 꼭 볼 것!