Algorithms

[알고리즘] Quick Sort: 구현 (Array 2단계)

Nickolodeon 2022. 11. 17. 10:28
지난 시간, 리스트를 활용해서 퀵 정렬을 보다 직관적으로 구현해보았다.
이번에는 이론 (Array 1단계) 에서 설명한 구현에 이어서 재귀호출과 배열을 사용해 퀵 정렬을 구현해보자. 
배열을 활용한 퀵 정렬
- 시간복잡도: O(logN)
- 공간복잡도: O(N).
이론에서 설명한 대로 한 차례 루프를 돌고 나면, 이제 배열을 쪼갤 차례이다. 기준 값이 이동하는 것이다. 그 전에, 먼저 메서드의 매개 변수를 추가해주어야 한다. 추적하기 위함인데, 쪼개진 배열의 첫 번째와 마지막 인덱스로, 계속 어디를 기준으로 쪼갤지를 명시한다고 생각하면 된다. 이 매개 변수가 변하면서 재귀적으로 메서드를 호출하면 된다. 그래서 정수 startIdx, endIdx 를 새로운 메서드의 매개 변수로 넣어주고 구현한다.
public class QuickSortWithArray {
	
    	private int[] arr;

    	public QuickSortWithArray(int[] arr) {
        	this.arr = arr;
    	}
        
        public void sort(int startIdx, int endIdx) { // 최초의 start 와 end 는 각각 arr 의 가장 첫 인덱스와 가장 마지막 인덱스이다.

            int oldPivotIdx = arr.length / 2; // 지금까지의 기준값 인덱스 선정 방식
            int pivotIdx = (endIdx - startIdx + 1) / 2; // 변경된 선정 방식

            int pivot = arr[pivotIdx]; // pivot 값 선정

            /* 우선 편의를 위해 식별이 쉬운 이름을 가진 변수에 할당한다. */
            int leftIdx = startIdx;
            int rightIdx = endIdx;

            while (rightIdx >= leftIdx) { // 두 지점이 교차될 때까지 반복한다.
                if (arr[leftIdx] < pivot) { // pivot 보다 왼쪽에 있는 값이 자기 자리에 잘 있을 때
                    leftIdx++;
                    continue;
                }
                if (arr[rightIdx] > pivot) { // 왼쪽에 있는 값이 교환이 필요한데, pivot 보다 오른쪽에 있는 값이 자기 자리에 잘 있을 때
                    rightIdx--; // 새로운 교환 대상을 찾기 위해 한 칸 왼쪽으로 움직여 탐색을 이어나간다.
                    continue;
                }
                /* 만약 위 두 개의 조건문을 통과하고 여기까지 왔으면, 교환을 해야 되는 상황에 적절한 교환 대상도 찾았다는 뜻이다. */
                swap(leftIdx, rightIdx); // 교환해주자
                /* 교환 후에는 이번 phase 에서는 자기 자리를 찾아갔다. 이 자리 이후 자리들을 교환하자. */
                leftIdx++;
                rightIdx--;
            }
        }
    }
여기서 막혔다. 재귀 호출을 어떻게 한단 말인가? 우선 나는 생성자에서 배열 arr 생성을 담당하고 있었다. 그래서 void 로 메서드를 만든 것이었다. 그럼 어차피 두 개로 나누어진 분할들을 차례대로 재귀적으로 호출하면 되는 것일까? 재귀 호출 시 한 개가 재귀적으로 반복을 끝낸 후 그 다음 재귀 호출이 일어날텐데... 맞다, 어차피 두 개는 나누어진 이상 재귀적으로 반복될 때 절대로 서로에게 관여할 일이 없다. 그래서 차례대로 호출하기만 하면 (솔직히 차례가 뒤바뀌어도 상관 없다) 알아서 arr 를 계속해서 정렬하고, 탈출 조건(Base case)를 만나면 멈출 것이다. 자, 이제 Base case 만 정하면 되는 상황이다. 언제 멈출까? 재귀 반복 안에서 일어날 마지막 정렬을 생각해보자. 원소가 두 개일 때이다. 이 정렬을 마치고 rightIdx 와 leftIdx 가 교차되고 나면, rightIdx 는 startIdx 에 무조건 도달해 있을 것이다 (단순히 왼쪽은 startIdx 이므로). leftIdx 도 endIdx 에 도달해 있다. 즉, rightIdx == startIdx 고 leftIdx == endIdx 가 될 것이다. 다른 말로, 이 때 재귀 호출을 하면 sort 의 매개 변수 두 값은 동일해질 것이라는 것이다. 즉, 각 재귀 호출은 startIdx == endIdx 일 때 멈춘다. 이제 코드로 보자.
public class QuickSortWithArray {
    private int[] arr;
    
    public QuickSortWithArray(int[] arr) {
    	this.arr = arr;
    }
    
    public void sort(int startIdx, int endIdx) { // 최초의 start 와 end 는 각각 arr 의 가장 첫 인덱스와 가장 마지막 인덱스이다.

        if (startIdx == endIdx) return;

        int oldPivotIdx = arr.length / 2; // 지금까지의 기준값 인덱스 선정 방식
        int pivotIdx = (endIdx + startIdx + 1) / 2; // 변경된 선정 방식

        int pivot = arr[pivotIdx]; // pivot 값 선정

        /* 우선 편의를 위해 식별이 쉬운 이름을 가진 변수에 할당한다. */
        int leftIdx = startIdx;
        int rightIdx = endIdx;

        while (rightIdx >= leftIdx) { // 두 지점이 교차될 때까지 반복한다.
            if (arr[leftIdx] < pivot) { // pivot 보다 왼쪽에 있는 값이 자기 자리에 잘 있을 때
                leftIdx++;
                continue;
            }
            if (arr[rightIdx] > pivot) { // 왼쪽에 있는 값이 교환이 필요한데, pivot 보다 오른쪽에 있는 값이 자기 자리에 잘 있을 때
                rightIdx--; // 새로운 교환 대상을 찾기 위해 한 칸 왼쪽으로 움직여 탐색을 이어나간다.
                continue;
            }
            /* 만약 위 두 개의 조건문을 통과하고 여기까지 왔으면, 교환을 해야 되는 상황에 적절한 교환 대상도 찾았다는 뜻이다. */
            swap(leftIdx, rightIdx); // 교환해주자
            /* 교환 후에는 이번 phase 에서는 자기 자리를 찾아갔다. 이 자리 이후 자리들을 교환하자. */
            leftIdx++;
            rightIdx--;
        }
        /* 여기로 나왔을 떄는 이미 교차되어서 rightIdx < leftIdx 인 상황이다.
         * 그러므로, rightIdx 가 첫 번째 분할의 endIdx, leftIdx 가 두 번째 분할의 startIdx 가 되어서 재귀 호출시킨다. */
        sort(startIdx, rightIdx);
        sort(leftIdx, endIdx);
    }    
}
메인 함수에서 아래와 같이 메서드를 테스트해보았다. getArr() 는 arr 를 가져오는 getter 이다.
    public static void main(String[] args) {
        int[] testArr = {20, 18, 5, 19, 40, 50, 5, 25};
        QuickSortWithArray quickSortWithArray = new QuickSortWithArray(testArr);
        quickSortWithArray.sort(0, 7);
        System.out.println(Arrays.toString(quickSortWithArray.getArr()));
    }
결과적으로 아래와 같이 배열이 정렬되었다.
[5, 5, 18, 19, 20, 25, 40, 50]
발생한 오류
pivotIdx 를 정할 때, 처음에는 재귀호출에서 arr.length / 2 를 어떻게 변수 startIdx 와 endIdx 를 이용해 표현할 수 있을까 생각하다가 endIdx - startIdx + 1 / 2 를 해 주었다. arr 의 길이는 고정이라 이 공식이 항상 arr 의 중간을 가리키기는 한다.
int pivotIdx = (endIdx - startIdx + 1) / 2;
하지만 우리가 pivot 을 사용하는 용도는 각 분할에서의 기준값을 찾기 위함이고, 각 분할에서 배열에는 변화가 없어도 우리가 배열 내에서 탐색하는 범위에는 변동이 생긴다. pivot 으로 그 범위 내의 중간값을 찾아야 하는 것인데, endIdx - startIdx + 1 / 2는 범위가 변하더라도 계속 배열의 중간만 찾는다. 그래서, 범위를 나타내는 startIdx 와 endIdx 의 중간을 찾기 위해 (즉 두 숫자의 평균을 찾으면 된다) startIdx + endIdx + 1 / 2 를 해주기로 했다.
int pivotIdx = (endIdx + startIdx + 1) / 2;
정상적으로 작동했다. 위 두 코드에서 1을 더해주는 이유는 중간을 찾을 때 범위 내의 모든 숫자의 개수를 2로 나눈 값을 중간으로 생각하고 싶었기 때문이다. 두 숫자 포함 그 사이에 몇 개가 있는지 세기 위해 1을 더해준 것이다.
댓글수0