[알고리즘] Sorting Algorithm(2)

4. Mergesort

 

 

 병합정렬은 divide and conquer의 방법을 사용하는 분할 정복 알고리즘이다. divide and conquer란 DP에서 설명했듯 큰 문제를 작은 문제들로 나누어 각각을 푸는 것으로, top-down approach의 방식으로 접근한다. divide and conquer의 특성을 이용하는 만큼 재귀호출을 이용한다.

//pseudocode
mergeSort(left, right) {
	if(left<right) {
    	mid = left와 right의 중간지점;
        mergeSort(left, mid);
        mergeSort(mid, right);
        merge;
        
        
merge {
	정렬되어 있는 두 배열을 합쳐서 정렬된 하나의 배열 만들기;
}

 

    public void mergeSort(int[] arr, int left, int right) {
        int mid = (left+right)/2;
        if(left<right) {
            mergeSort(arr, left, mid);
            mergeSort(arr, mid+1, right);
            merge(arr, left, mid , right);
        }
    }

    private void merge(int[] arr, int left, int mid, int right) {
        int[] tmpArr = arr.clone();
        int c1 = left;
        int c2 = mid+1;
        int cursor = left;

        while (cursor<=right) {
            if(tmpArr[c1]<=tmpArr[c2]) {
                arr[cursor++] = tmpArr[c1++];
            } else {
                arr[cursor++] = tmpArr[c2++];
            }
        }
    }

이 코드 어디가 틀렸을까요?

//올바른 코드
if(c2>right || (c1<=mid && tmpArr[c1]<=tmpArr[c2])) {

merge함수 while문안의 첫 if문의 조건이 모자랐다.

        while (cursor<=right && c1<=mid && c2<=right) {
            if(tmpArr[c1]<=tmpArr[c2]) {
                arr[cursor++] = tmpArr[c1++];
            } else if(tmpArr[c1]>tmpArr[c2]) {
                arr[cursor++] = tmpArr[c2++];
            }
        }

그럼 이건 왜안될까? whlie문에서 c1과 c2의 조건을 무조건 만족해야 반복문이 진행되게 설정해놓고

index c1과 c2의 확실한 조건비교를 통해서 코드를 진행시켜나가는 방법인데

진행이 마무리된 c1이나 c2가 중복검사될 확률은 cursor와 c1,c2에 ++연산을 해줌으로서 차단했지만 이 경우 외부 while문을 통해서 들어올 수 없게된다.

 

정리

 병합정렬은 배열에 저장된 input들을 처음부터 하나씩 비교하여 두개의 리스트의 값 중에서 작은 값을 새로운 리스트로 옮기는 과정을 반복하는 알고리즘이다. 새로운 리스트를 필요로 하는 만큼 추가적인 메모리를 필요로 하지만, 정렬 알고리즘(1)에서 다루었던 알고리즘들과는 다르게 O(nlgn)의 시간복잡도를 가진다. 이는 merge를 호출할 때 input length가 n이라고 하면, (left<right)라는 조건에 의해 재귀호출의 최대 깊이가 lgn이 되고, 각 단계마다는 크기가 n/2로 줄어들지만 비교쌍이 2배씩 늘어나서 n의 시간복잡도를 갖기 때문이다. 

T(n) = nlgn(비교) + 2nlgn(이동 2번) = 3nlgn = O(nlogn)

 

5. QuickSort

 

 

 퀵정렬은 병합정렬과 비슷하게 divide and conquer를 사용하는 정렬이다. 하지만 병합정렬과는 다르게 배열을 비균등하게 분배하고, 피벗의 위치에 따라 최악의 경우 O(n^2)의 시간복잡도를 가진다. 

 퀵정렬에서는 정렬을 위해 배열 안 원소 중에서 피벗을 지정한다. 그 후 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗보다 왼쪽으로, 피벗보다 큰 요소들은 피벗보다 오른쪽으로 정렬되게끔 한다. 그 후 각각의 분할된 배열 집합에 대해서도 동일한 과정을 수행해서 각각의 배열집합을 분할이 불가능할때까지 재정렬하는 과정을 반복하고, 그를 통해 전체 배열이 정렬되게끔 한다. 

 이러한 순환 호출이 진행될때마다 피벗은 위치가 정렬되므로, divide and conquer의 과정에서 알고리즘이 반드시 종료됨을 알 수 있다.

    public void quickSort(int[] arr, int left, int right) {
    //    if(left>=right) return;
    //
    //    int pivot = partition(arr, left, right);
    //    quickSort(arr, left, pivot);
    //    quickSort(arr, pivot+1, right);

        int p = partition(arr, left, right);
        if(left<p-1) quickSort(arr,left,p-1);
        if(p<right) quickSort(arr,p,right);
    }

    private int partition(int[] arr, int left, int right) {
        //pivot 기준 설정
        int pivot = arr[(left+right)/2];
        while(left<=right) { //=를빼면 오류
        	//pivot도 위치를 바꾸어 지정해주어야하므로 =가 들어가면 오류
            while(arr[left]<pivot) left++;
            while(arr[right]>pivot) right--;
            if(left<=right)  { //=를빼면 오류
                swap(arr, left++, right--);
            }
        }
        return left;
    }

개념이해는 쉬웠고 코드로 작성하는것까지도 간단했는데 막상 디버깅해보니깐 left와 right가 왔다갔다하는 범위설정하는게 헷갈리고 이해가 100%는 안간다. left가 right보다 크거나 같게되면(or크게되면) 바로 return해버리는걸 조건으로 넣으면 왜 스택 오버플로 에러가 발생하는걸까?? (주석처리해놓은 부분)

 

정리

시간복잡도: O(nlgn), worst case O(n^2)

피벗값을 기준으로 나누므로 피벗값이 한쪽으로 치우치게 설정되면 재귀호출의 횟수가 log꼴이 아닌 선형(n)으로 실행될 수 있다.