[기본정렬] Quick Sort & Merge Sort 특징 및 차이점 정리, 자바로 구현해보기

분명히 예전에 자료구조 공부하며 직접 구현해보기도 했지만, 한참을 안보니 기억 속에서 희미해져 버렸다.

 

그래서 다시 책을 보며 java 로 구현해보고, 각 정렬의 동작 방식을 복기해보려고 한다.

 

더 나아가 두 정렬을 이론적으로 설명할 수 있게끔 제대로 학습해야겠다.

 

Quick Sort

주요 키워드 : 피벗 (Pivot) 

시간 복잡도 : 평균 O(nlongn), 최악O(nc2)

특징

- 별도의 메모리를 사용하지 않는다.

- 배열 내 교환이 이루어지기 때문에 불안정 정렬이다.

- 이미 정렬된 배열이면 최악의 시간복잡도를 가진다.

private static void swap(int[] a, int i, int j) { // 인덱스 i,j 의 위치를 교환하는 함수
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    private static void quickSort(int[] arr, int left, int right){ //실제 정렬 함수
        int pl = left; //왼쪽 커서
        int pr = right; //오른쪽 커서
        int pivot = arr[(left+right) / 2]; //피벗은 중앙값으로 지정 (왼쪽, 오른쪽 피벗이 모두 가능하다.)

        do{ 
            while(arr[pl] < pivot) pl++; //피벗보다 큰 값을 찾을때까지 왼쪽 커서 오른쪽으로 이동
            while(arr[pr] > pivot) pr--; //피벗보다 작은 값을 찾을때까지 오른쪽 커서 왼쪽으로 이동
            if(pl<=pr) //여기에 도달했을때는 피벗을 기준으로 왼쪽 커서는 피벗보다 큰 값을, 오른쪽 커서는 피벗보다 작은 값을 가르킨다.
                swap(arr, pl++, pr--); // 두 데이터를 교환해준다.
        }while(pl<=pr); //두 커서가 어긋날때까지 반복한다. (여기서 안멈추면 다시 제자리로 바뀐다)

        if(left < pr) quickSort(arr, left, pr); //pr이 left보다 크다는 것은 왼쪽에 아직 손대지 못한 데이터가 남았다는 뜻
        if(pl < right) quickSort(arr, pl, right ); //pl이 right보다 작다는 것은 오른쪽에 손대지 못한 데이터가 남았다는 뜻
        //남은 데이터들을 각각의 범위로 쪼개서 분할 정복을 진행한다.
        
    }

 

---

Merge Sort

주요 키워드 : 병합

시간 복잡도 : 평균 O(nlongn), 최악O(nlongn)

특징

- 원소가 하나만 남을때까지 배열을 반으로 계속 쪼갠다. 그리고 나서 차순에 따라서 다시 병합한다.

- 별도의 메모리 공간을 사용한다. (빈 배열)

- 교환이 일어나지 않기 때문에 안정적인 정렬이라고 한다.

 

static void merge(int[] arr, int left, int mid, int right){
        int indexL = left; // 분할된 배열 중 왼쪽 배열
        int indexR = mid + 1; //분할된 배열 중 오른쪽 배열
        int index = left; //빈 객체의 인덱스 (left부터 저장해야할 인덱스임)

        int[] tmp = new int[right + 1];

        while(indexL <= mid && indexR <= right){ //왼쪽 배열이나 오른쪽 배열 둘 중 하나가 끝날때까지
            if(arr[indexL] <= arr[indexR]) //오름차순이기 때문에 작은값부터 넣어줘야 한다.
                tmp[index++] = arr[indexL++];
            else
                tmp[index++] = arr[indexR++];
        }

        //남은거 처리
        if(indexL > mid){ //만약 왼쪽 배열이 끝났다면 오른쪽 배열이 남아있다는 뜻
            for(int i=indexR; i<=right; i++){ //나머지 처리
                tmp[index++] = arr[i];
            }
        } else{ //반대로 오른쪽 배열이 끝났다면 왼쪽 배열이 남아있다는 뜻
            for(int i=indexL; i<=mid; i++){ //나머지 처리
                tmp[index++] = arr[i];
            }
        }

        for(int i=left; i<=right; i++){ //정렬된 빈 배열을 원래 배열로 다 옮긴다.
            arr[i] = tmp[i];
        }
    }

    static void mergeSort(int[] arr, int left, int right){
        if(left < right){ //정렬해야될 범위가 있을 때
            int mid = (left + right) / 2; //중간 지점을 기준으로 둘로 나눈다. (log n)

            mergeSort(arr, left, mid); // 왼쪽 범위

            mergeSort(arr, mid+1, right); //오른쪽 범위

            merge(arr, left, mid, right); //왼쪽 오른쪽 나눴으면 빈 배열에 정렬해서 넣어줘야 한다. 
        }
    }

 

메모리가 부족하고 데이터가 정렬되어 있지 않다는 확신이 있을 때는 Quick Sort를,

메모리가 여유롭고 데이터가 정렬되어 있을 수도 있으면 Merge Sort를 사용해야 한다.