퀵정렬과 병합 정렬

차이점

---

퀵정렬과 병합 정렬은 비슷한 듯 다른 알고리즘을 가지고 있다.

	퀵 정렬	병합 정렬
동작 방식	분할 정복(Divide and Conquer) 방식을 사용. 배열을 피벗(pivot)을 기준으로 두 개의 부분 배열로 분할하고, 각 부분 배열을 재귀적으로 정렬	분할 정복(Divide and Conquer) 방식을 사용. 배열을 나눠 정렬하고 병합하는 방식
평균 및 최악 시간 복잡도	평균 O(n logn) 최악의 경우(피벗이 최솟값이거나 최대값) O(n^2)	항상 O(n log n)
안정성	동일한 값에 대해 상대적인 순서가 변할 수 있다.	동일한 값에 대해 상대적인 순서가 유지된다.
공간 복잡도	재귀 호출에 따른 스택 공간을 고려해야 한다.	입력 배열 크기에 비례하는 공간이 필요. 따라서 메모리 사용량이 많을 수 있다.
적용 가능성	데이터의 분포를 고려하여 최악을 대비해야 한다.	입력 크기나 데이터의 분포를 알 수 없는 경우에도 일관된 성능을 제공하므로 안정적이다.

 

퀵 정렬

---

 

public class QuickSort {
    
    // 퀵 정렬 알고리즘
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);

            // 피벗을 기준으로 분할하여 재귀적으로 정렬
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }

    // 배열을 피벗을 기준으로 분할하는 메서드
    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1; // 더 작은 요소의 인덱스

        for (int j = low; j < high; j++) {
            // 현재 요소가 피벗보다 작거나 같으면
            if (arr[j] <= pivot) {
                i++;
                swap(arr, i, j); // swap 메서드 호출
            }
        }

        swap(arr, i + 1, high); // 피벗과 위치를 교환

        return i + 1;
    }
    
    // 배열의 두 요소를 교환하는 메서드
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

 

 

병합 정렬

---

시간 복잡도가 항상 같은 이유

• 분할 단계(Divide): 배열을 반으로 나누는 데 O(log N)의 시간이 소요된다.
• 정복 단계(Conquer): 각각의 하위 배열을 정렬하고 합치는데 O(N)의 시간이 소요된다.

위 세 단계를 고려하면, 전체 병합 정렬의 시간 복잡도는 O(log N) * O(N) = O(N log N)이 된다.

예를 들어 8개의 요소를 분할하고 병합하는 과정은 3번 (log8 = 3) 이루어진다. 1번의 분할 병합 과정에서 요소에 1번씩 접근하게 된다.

 

public class MergeSort {

    // 배열을 병합 정렬하는 메서드
    void mergeSort(int[] arr) {
        mergeSort(arr, 0, arr.length - 1);
    }

    // 배열의 특정 부분을 병합 정렬하는 메서드
    void mergeSort(int[] arr, int start, int end) {
        // 시작 인덱스가 끝 인덱스보다 크거나 같으면 종료
        if (start >= end) {
            return;
        }

        // 중간 지점 계산
        int mid = (start + end) / 2;

        // 왼쪽 부분 배열 병합 정렬
        mergeSort(arr, start, mid);

        // 오른쪽 부분 배열 병합 정렬
        mergeSort(arr, mid + 1, end);

        // 이미 정렬된 상태라면 병합하지 않고 종료
        if (arr[mid] <= arr[mid + 1]) {
            return;
        }

        // 부분 배열들 병합
        merge(arr, start, mid, end);
    }

    // 두 부분 배열을 병합하는 메서드
    void merge(int[] arr, int start, int mid, int end) {
        // 임시 배열 생성
        int[] tmp = new int[end - start + 1];
        int lp = start;
        int rp = mid + 1;
        int currentIndex = 0;

        // 두 부분 배열을 비교하며 병합
        while (lp <= mid && rp <= end) {
            if (arr[lp] < arr[rp]) {
                tmp[currentIndex++] = arr[lp++];
            } else {
                tmp[currentIndex++] = arr[rp++];
            }
        }

        // 남은 요소들을 임시 배열에 추가
        while (lp <= mid) {
            tmp[currentIndex++] = arr[lp++];
        }

        while (rp <= end) {
            tmp[currentIndex++] = arr[rp++];
        }

        // 임시 배열의 내용을 원래 배열로 복사
        System.arraycopy(tmp, 0, arr, start, tmp.length);
    }
}