[알고리즘] Quick Sort: 이론 (Array 1단계)

QuickSort 는 어려운 부분이 포인터 총 세 개를 이용해서 하나는 기준값, 하나는 맨 왼쪽의 원소, 하나는 맨 오른쪽의 원소를 가리킨 채로 시작을 한다는 점이다. 기준값을 가지고 어떠한 액션을 취할 것 같은데, 사실 기준값은 말 그대로 기준의 역할 외에는 하는 것이 없다. 기준 값을 기준으로 현재의 두 원소들을 (포인터들로 가리키고 있다) swap할 것인지, 아니면 다른 원소를 찾을 것인지를 결정한다. 다른 원소를 찾기로 결정되면 포인터가 가리키는 위치를 증가 or 감소시킨다.

이후 다음 iteration phase 에서 이번 두 원소는 swap 할 조건을 충족시키는지 확인한다. (즉, 왼쪽 포인터는 pivot 보다 더 큰 원소를 가리키고, 오른쪽은 pivot 보다 더 작은 원소를 가리키는 상황) swap 하고 이 두 원소들과 그 왼쪽, 오른쪽까지의 원소들은 자기 자리를 찾았으니 (왼쪽에는 pivot 보다 작은 원소들 / 오른쪽에는 pivot 보다 큰 원소들 ) 다음 위치들을 확인하기 위해 왼쪽은 + 1, 오른쪽은 -1 해준다. 코드로 확인하자.

    public void switchOrStay() {
        int leftIdx = 0;
        int rightIdx = arr.length - 1;

        int pivotIdx = arr.length/2;
        int pivot = arr[pivotIdx];
        /* 우선 while 문 조건을 처음부터 leftIdx 가 rightIdx 보다 작거나 같은 한 으로 설정해야 하는지,
         * 아니면 우선 직관적으로 leftIdx 를 pivotIdx 에 도달할 때까지 증가시키면서 교환한 후에
         * rightIdx 를 감소시키면서 교환하는 논리를 코드로 그대로 구현할 것인지 결정해야 한다.
         * 지금은 첫 구현이므로 후자로 하기로 한다. */
        while (leftIdx <= rightIdx) { // 같을 때 (leftIdx == rightIdx) 에도 교환은 일어난다는 뜻이다. 같은지 확인하는 비용이 더 많이 들기 때문에 교환한다.
            if (arr[leftIdx] < pivot) { // 작거나 같으면 안되는 이유는 pivot 에 도달했을 때 이 조건문을 빠져나와서 밑으로 들어가야 하기 때문이다.
                leftIdx += 1; // 이미 작으면 포인터만 증가시킨다.
                continue;
            }
            if (arr[rightIdx] > pivot) {
                rightIdx -= 1;
                continue;
            }
            swap(leftIdx, rightIdx); // 이건가?
            leftIdx += 1;
            rightIdx -= 1;
            System.out.println("left: " + leftIdx + " right: " + rightIdx);
        }

        System.out.println(Arrays.toString(arr));
    }

사실 첫 번째 루프를 지나면 세 개로 나누어져 있을거라 기대하지만, 그렇지 않다. 루프를 돌고 나면 기준값이 이동해있을 수 있고, 그러면 원래 있던 곳에 기준값이 없으니 당연히 (작은 수, 중간 수, 큰 수) 의 세 그룹으로 나누어져 있지 않다. 그냥 정했던 기준값을 중심으로 (위치는 중심이 아니지만) 더 작은 값들이 왼쪽으로 치우쳐져 있고 큰 값들이 오른쪽에 위치한 '경향' 이 보일 뿐이다.

+ 어려웠던 점

이쯤 되면 기준 값을 이동시켜야 하는게 아닌가 싶어진다. 계속 기준 값을 이동하면서 알고리즘을 실행시키면 알아서 중간값이 찾아들어가는 것이 신기하면서 이해가 안 됐다. 다음 포스트에서 코드를 보며 무슨 일인지 더 자세하게 알아보자.