속도를 높이는 재귀 알고리즘

재귀 알고리즘을 이용해서 속도를 높이는 알고리즘이 있다. 대표적인 예로 퀵 정렬을 말 할수 있다. 하지만 퀵정려를 알기전에 우선 분할에 대해서 이해하고 있어야 한다.

분할

배열을 분할한다는 것은 배열로부터 임의의 수를 가져와(이후 수를 피벗이라 부름) 피벗보다 작은 모든 수는 피벗의 왼쪽에, 피벗보다 큰 모든 수는 피벗의 오른쪽에 두는 것이다.
[0,5,2,1,6,3] 다음과 같은 배열이 있다고 가정한다. 이 때 피벗을 고르는 기준은 오른쪽에 있는 값을 항상 피벗으로 고르겠다(다른 값을 골라도 무방)

따라서 위 배열에서는 3이 피벗이 된다. 이서서 두 포인터를 사용해서 하나는 배열 가장 왼쪽에 있는 값에, 다른 하나는 피벗을 제외한 배열 가장 오른쪽에 있는 값에 할당한다.
왼쪽 포인터 - 0, 오른쪽 포인터 6

이제 다음과 같은 단계를 따라 실제로 분할을 할수 있다.

1. 왼쪽 포인터를 한 셀씩 게속 오른쪽으로 옮기면서 피벗보다 크거나 같은 값에 도달하면 멈춘다.
2. 이어서 오른쪽 포인터를 한 셀씩 계속 왼쪽으로 옮기면서 피벗보다 작거나 같은 값에 도달하면 멈춘다(혹은 배열 맨 앞에 도달 할 때).
3. 오른쪽 포인터가 멈춘 후에는 둘 중 하나를 선택해야 한다. 왼쪽 포인터가 오른쪽 포인터에 도달했으면(넘어 섰으면) 4단계로 넘어간다. 그렇지 않으면 왼쪽 포인터와 오른쪽 포인터가 가리키고 있는 값을 교환한 후 1,2,3,단계를 반복한다.
4. 끝으로 왼쪽 포인터가 현재 가리키고 있는 값과 피벗을 교환한다.

분할이 끝나면 피벗 왼쪽에 있는 값은 모두 피벗보다 작고, 피벗 오른쪽에 있는 값은 모두 피벗보다 크다. 다른 값들은 아직 정렬되지 않았지만 피벗 자체는 이제 배열 내에서 올바른 위치에 있게 된다.

이제 이 절차를 위 배열에 적응해 보자.

0은 피벗보다 작으므로 왼쪽 포인터를 옮긴다(2단계). 왼쪽 포인터 - 5,오른쪽 포인터 6
왼쪽 포인터와 피벗을 비교한다(5 > 3) 왼쪽 포인터를 멈추고 다음 단계에서 오른쪽 포인터를 이동시키기 시작한다.
오른쪽 포인터와 피벗을 비교한다(6 > 3) 6이 더 크므로 다음 단계에서 포인터를 옮긴다(3단계).
오른쪽 포인터를 한칸 왼쪽으로 옮긴다(4단계). 오른쪽 포인터 1
오른쪽 포인터(1)와 피벗을 비교. 피벗보다 작으므로 포인터를 멈춘다.
두 포인터가 모두 멈췄으니 두 포인터의 값을 교환한다(5단계). [0,*1,2,*5,6,3]
다시 왼쪽 포인터를 이동시킨다(6단계). [0,1,*2,*5,6,3]
왼쪽 포인터와 피벗을 비교 후 다시 왼쪽 포인터를 이동시킨다. 이때 포인터는 모두 같은 값을 가르키고 있다.[0,1,2,**5,6,3]
왼쪽 포인터와 피벗을 비교한다(5 < 6) 왼쪽 포인터와 피벗을 비교한다. 왼쪽 포인터(5)가 피벗(3)보다 큰 값을 가지고 있으므로 멈춘다. 이 때 왼쪽 포인터가 오른쪽 포인터에 도달 했으므로 포인터 이동을 중지하고 왼쪽 포인터가 가르키고 있는 값과 피벗을 교환한다. [0,1,2,3,6,5]

배열을 완전히 정렬되지 않았지만 분할은 성공적으로 끝냈다. 즉 피벗이 숫자 3이었으므로, 3보다 작은 수는 왼쪽에, 3보다 큰 수는 오른쪽에 있다. 또한 3은 이제 배열 내 올바른 위치에 있게 됐다.

코드 구현:분할

class sortTableArray{
    private ArrayList<Integer> arrayList;
    public sortTableArray(ArrayList<Integer> arr) {
        this.arrayList = arr;
    }
       public int partition(int left_pointer, int right_pointer){
        //항상 오른쪽에 있는 값을 피벗으로 선택.
        //나중에 사용 할 수 있도록 피벗의 인덱스를 저장.
        int pivotIndex = right_pointer;
        int temp;
        //피벗 값을 저장.
        int pivot = this.arrayList.get(right_pointer);
        right_pointer -= 1;
        while (true){
            //피벗보다 크거나 값을 값을 가리킬 때까지 왼쪽 포인터를 오른쪽으로 이동.
            while (arrayList.get(left_pointer) < pivot && left_pointer < arrayList.size() -1){
                left_pointer += 1;
            }
            //피벗보다 크거나 값을 값을 가리킬 때까지 오른쪽 포인터를 왼쪽으로 이동.
            while (arrayList.get(right_pointer) > pivot && right_pointer > 0){
                right_pointer -= 1;
            }
            //이제 왼쪽 포인터와 오른쪽 포인터 모두 이동을 멈춘다.
            //왼쪽 포인터가 오른쪽 포인터에 도달했는지 확인.
            //그렇다면 루프를 종료하고 피벗을 교환한다.
            if(left_pointer >= right_pointer) break;
            //왼쪽 포인터가 오른쪽 포인터보다 앞에 있으면 서로 값을 교환한다.
            else{
                temp = arrayList.get(left_pointer);
                arrayList.set(left_pointer,arrayList.get(right_pointer));
                arrayList.set(right_pointer,temp);
                left_pointer -= 1;
            }
        }
        temp = arrayList.get(pivotIndex);
        arrayList.set(pivotIndex,arrayList.get(left_pointer));
        arrayList.set(left_pointer,temp);
        return left_pointer;
    }
}

퀵 정렬

퀵 정렬 알고리즘은 분할과 재귀로 이뤄진다. 알고리즘은 다음과 같이 동작한다.

1. 배열을 분할한다. 피벗은 이제 올바른 위치에 있다.
2. 피벗의 왼쪽과 오른쪽에 있는 하위 배열을 각각 또 다른 배열로 보고 1단계와 2단계를 재귀적으로 반복한다. 즉, 각 하위 배열을 분할하고 각 하위 배열에 있는 피벗의 왼쪽과 오른쪽에서 더 작아진 하위 배열을 얻는다. 이어서 이러한 하위 배열을 다시 분할하는 과정을 반복한다.
3. 하위 배열이 원소를 0개 또는 1개 포함하면 기저 조건이므로 아무것도 하지 않는다.

배열 [0,5,2,1,6,3] 한 번의 분할을 수행하면, [0,1,2,3,6,5] 다음과 같은 배열을 얻을 수 있다. 퀵 정렬은 분할로 시작한다.
[0,1,2,3,6,5] 배열에서 피벗은 3이였다. 분할이 한번 끝나게 되면 피벗 왼쪽에 있는 값 [0,1,2] 하나의 배열로 보고 분할한다. 하위 배열 [0,1,2] 중에서 가장 오른쪽 원소를 피벗으로 설정한다. 이 후 왼쪽과 오른쪽 포인터를 설정한다. [*0,*1,2]
왼쪽 포인터0과 피벗2를 비교한다. 0은 2보다 더 작으므로 왼쪽 포인터를 한 칸 오른쪽으로 옮긴다. [0,**1,2,]
이제 왼쪽 포인터와 오른쪽 포인터는 같은 값을 가리키게 된다.
다음으로 왼쪽 포인터와 피벗을 비교한다. 1이 피벗 보다 작으므로 포인터를 옮긴다.[0,*1,*2,]
왼쪽 포인터가 이제 피벗을 가리키게 된다. 이 때 왼쪽 포인터가 가리키는 값이 피벗과 동일하므로 왼쪽 포인터를 멈춘다. 이제 오른쪽 포인터를 동작시킨다. 1은 0 보다 크므로 포인터는 멈춘다. 왼쪽 포인터가 오른쪽 포인터를 지나쳤으므로 이제 분할에서는 더 이상 포인터를 이동시키지 않는다. 이후 왼쪽포인터와 피벗을 교환한다. 하지만 왼쪽 포인터는 이미 피벗을 가리키고 있으므로 아무런 변화가 일어나지 않는다. 이제 다음 하위 배열 [0,1]에서 이 작업을 반복한다. 이런 작업을 거치게 되면 [0,1,2,3] 배열은 정렬이 완료된다. 이제 기존 피벗인 3 오른쪽에 있는 [6,5]를 에서 위 작업을 반복한다. 이렇게 배열을 분할하면서 재귀적으로 반복하는것이 퀵 정렬이다.

코드 구현: 퀵 정렬

    public void quickSort(int leftIndex, int rightIndex){
        //기저 조건: 하위 배열 원소가 0개 또는 1개일 때
        if (rightIndex - leftIndex <= 0) return;
        // 범위 내 원소들을 분할하고 피벗의 인덱스를 가져온다.
        int pivotIndex = partition(leftIndex,rightIndex);
        //피벗 왼쪽에 대해 퀵 솔트 메서드를 재귀적으로 호출한다.
        quickSort(leftIndex,pivotIndex - 1);
        //피벗 오른쪽에 대해 퀵 솔트 메서드를 재귀적으로 호출한다.
        quickSort(pivotIndex + 1, rightIndex);
    }

이 퀵 정렬은 sortTableArray 내부 함수이다.

퀵 정렬의 효율성

퀵 정렬의 효울성은 어떻게 될까???
분할에 필요한 단계를 분루해 보면 단계가 두 종류임을 알 수 있다.
1. 비교: 각 값과 피벗을 비교.
2. 교환: 적절한 때에 왼쪽과 오른쪽 포인터가 가리키고 있는 값을 교환.
각 분할마다 배열 내 각 원소를 피벗과 비교하므로 최소 N번 비교한다. 분할을 한번 할때마다 왼쪽과 오른쪽 포인터가 서로 만날 때까지 매 셀을 이동하기 때문이다.
하지만 교환 횟수는 데이터가 어떻게 정렬되어 있느냐에 따라 다르다. 가능한 값을 모두 교환한다 해도 한 번에 값 두개를 교환하므로 한 분할에 최대 N/2번 교환한다.

일반적으로 N/4번 교환한다. 따라서 평균적으로 데이터가 N개일 때 대략 1.25N단계가 걸린다. ㅂ따라서 O(N)시간에 분할을 실행한한다고 볼 수있다.

한 눈에 보는 퀵 정렬

퀵 정렬은 기본적으로 연이은 분할로 수행되는데, 각 분할마다 하위 배열의 원소가 N개일 떄 약 N단계가 더린다. 결국 모든 하위 배열의 크기를 합하면 퀵 정렬에 걸리는 총 단계 수가 나온다.

• O O O O O O O O
• O O O V X X X X
• O V X V X X X X
• V V O V X X X X
• V V V V O O O O
• V V V V O O V X
• V V V V V O V X
• V V V V V V V O
  원소 8개 + 원소 3개 + 원소 1개 + 원소 1개 + 원소 4개 +원소 2개 + 원소 1개 + 원소 1개 = 총 약 21단계
  다음의 표를 보자.
  

빅 오로 나타낸 퀵 정렬

빅오 표가법 관점에서 퀵 정렬을 어떻게 분류할까?

표를 보면 알 수있다. 배열의 원소가 N개일 때 퀵 정렬에 필요한 단계는N * logN이다.
그렇다면 NlogN은 다른 빅오 카테고리와 어떠한 차이점이 있을까??

어째서 퀵 솔트는 NlogN이 나올까??
배열이 하나의 값만 남을 떄 까지 반으로 나눈다고 생각해보자. 이 경우 몇 번의 단계가 필요하겠는가??
배열이 길이가 8이라면 3번의 단계에 크기가 하나인 배열이 나오게된다. 즉 logN번이다.
따라서 퀵 정렬은 NlogN이 걸리게 된다.
하지만 이것은 배열을 정확히 반으로 나눴을 때 일어나는 가정이다. 일반적으로 퀵 정렬을 수행 할 경우 정확하게 배열을 반으로 나누지 않는다. 피벗 값과 비교하여 배열을 분할하기 때문이다.

퀵 정렬의 최악의 시나리오

[O][O][O][O][O][O][O][O] : 분할 1, 8개 원소
[V][O][O][O][O][O][O][O] : 분할 2, 7개 원소
[V][V][O][O][O][O][O][O] : 분할 3, 6개 원소
[V][V][V][O][O][O][O][O] : 분할 4, 5개 원소
[V][V][V][V][O][O][O][O] : 분할 5, 4개 원소
[V][V][V][V][V][O][O][O] : 분할 6, 3개 원소
[V][V][V][V][V][V][O][O] : 분할 7, 2개 원소
[V][V][V][V][V][V][V][O] : 분할 8, 1개 원소
피벗이 항상 각 하위 배열의 왼쪽 끝에 놓인다고 가정하자.
각 분할마다 교환은 한 번뿐이지만 비교가 너무 많으므로 효율성이 떨어진다. 그 전에 예시에서는 피벗이 항상 중간 쯤에 위치했었다. 그렇기에 첫 번째 분할 후에 비교적으로 작은 하위 배열에 대해 분할을 수행 할 수 있었다. 하지만 위 예시에서는 분할이 N,N-1,N-2...1 까지 일어난다.
따라서 계산되는 빅 오는 O(N^2)이다.

퀵 정렬 대 삽입 정렬

	최선의 경우	평균적인 경우	최악의 경우
삽입 정렬	O(N)	O(N^2)	O(N^2)
퀵 정렬	O(Nlog)	O(Nlog)	O(N^2)

평균적인 경우 킉 정렬이 더욱 빠르다. 최선의 경우와 최악의 경우의 비중보다 평균적인 시나리오의 비중이 더욱 크다. 그렇기에 내장 정렬 함수를 구현 할 때 퀵 정렬을 사용하는 경우가 많다.

퀵 셀렉트

무작위 숫자로 이루어진 배열이 있다. 이 때 두 번째로 작은 값을 찾으려고 한다.
어떻게 찾아야 할까??
정렬 후 1번째 인덱스를 출려하는 방법도 아무리 빨라도 NlogN이란걸 알 고 있다. 하지만 이때 퀵 셀렉트를 사용하게 되면 더욱 빠르게 원하는 값을 찾을 수 있다.

|ㅁ|ㅁ|ㅁ|ㅁ|ㅁ|ㅁ|ㅁ|ㅁ| 우선 배열을 분할한다.
|ㅁ|ㅁ|ㅁ|ㅁ|V|ㅁ|ㅁ|ㅁ| 이제 5번째로 작은 값을 알게 됐다.
2번 쨰로 작은 값을 찾기 위에 오른쪽 배열은 무시한다.
|O|O|V|O|V|X|X|X| 왼쪽의 하위 배열의 새 피벗이 3번째 있다고 가정하자.
이 경우 이제 왼쪽에 남은 배열은 두 개다. 이 하위 배열을 분할하자.
|V|V|V|O|V|X|X|X| 이제 우리는 인덱스 0,1,2,4가 올바른 위치에 있다는 걸 알고 있다. 이제 우리가 찾는 값이 두번째로 작은 값인 인덱스 1을 출력한다.

퀵 셀렉트의 훌륭한 점은 전체 배열을 정렬하지 않고도 올바른 값을 찾을 수 있다는 것이다.

퀵 셀렉트의 효율성

퀵 셀렉트의 효울성은 평균 시나리오세어 O(N)이다.
퀵 셀렉트는 분할 할 때마다 반을 버린다. 즉 N = 8 이면 8 + 4 + 2 = 14, N = 64 일 때 64 + 32 + 16 + 8 + 4 + 2 = 126, N = 128이면 254단계를 수행한다.
N + N/2 + N/4 + N/8 + 2 = 2N이다. 따라는 O(N)

퀵 셀렉트 코드 구현

    public int quickSelect(int lowestValue, int leftIndex, int rightIndex){
        // 기저 조건이면, 즉 하위 배열에 셀이 하나면 찾고 있던 값을 찾은 것이다.
        if (rightIndex - leftIndex <= 0) return arrayList.get(leftIndex);
        // 배열을 분할하고 피벗의 위치를 가져온다.
        int pivotIndex = partition(leftIndex,rightIndex);
        // 찾고 있는 값이 피벗 왼쪽에 있으면
        if (lowestValue < pivotIndex)
            //피벗 왼쪽의 하위 배여렝 대해 재귀적으로 퀵 셀렉트를 수행한다.
            return quickSelect(lowestValue,leftIndex,pivotIndex -1);
        else if (lowestValue > pivotIndex)
            //피벗 오른쪽의 하위 배여렝 대해 재귀적으로 퀵 셀렉트를 수행한다.
            return quickSelect(lowestValue,pivotIndex + 1, rightIndex);
        else
            return arrayList.get(pivotIndex);
    }

다른 알고리즘의 핵심 역활을 하는 정렬

현재까지의 가장 빠른 정렬 알고리즘의 속도는 O(N lonN)이다.
퀵 정렬이 가장 유명하나 병합 정렬 역시 O(N logN)이다.

4장에서 다뤘던 배열에 중복이 있는지 확인하는 문제에서, 정렬을 이용해 O(N^2)인 이차 해법을 개선할 수 있다.

중복이 있는 배열 [5, 9, 3, 2, 4, 5, 6]을 정렬하면 [2, 3, 4, 5, 5, 6, 9]가 된다. 정렬된 배열을 순회하며 다음 숫자와 동일한지 판단하면 중복을 찾을 수 있다.

Arrays.sort()는 Dual-Pivot Quicksort를 사용하고
Collections.sort()는 merge sort와 insert sort를 합친 timsort를 사용합니다.
Quick sort는 배열에서 좋은 성능을 보이지만 stable하지 않아서 stable이 필요한 Object에는 Collections.sort()가 많이 쓰입니다.

    public static boolean hasDuplicateValue(ArrayList<Integer> arrayList){
       Collections.sort(arrayList);
       for (int i = 0; i < arrayList.size() - 1; i++){
           if(arrayList.get(i) == arrayList.get(i+1)) return true;
       }
        return false;
    }

자바에서 지원하는 sort() 함수를 통해 배열을 정렬한다. 이 경우 평균 시나리오에서 NlogN의 단계를 필요로 한다. 그 후 N번 반복하면 배열의 중복을 찾는다. 따라서 O(NlogN)이다.
O(N^2)에서 O(NlogN) 코드의 효율성을 올릴 수 있었다.

결론

퀵 정렬과 퀵 셀렉트는 이해하긴 어렵지만 깊은 생각 끝에 나온 알고리즘이 얼마나 성능을 높일 수 있는지 보여준다.