[Algorithm] 고급 정렬 알고리즘

퀵 정렬(Quick Sort)

Logic

1. 배열 가운데서 피벗이 될 요소를 고른다.

2. 피벗 요소 좌측에는 해당 요소보다 작은 요소들이 오고, 우측에는 큰 요소들이 오도록 한다.

3. 피벗을 기준으로 좌우로 나뉘어진 배열 각각에 동일한 과정을 수행한다.

Algorithm

public void quickSort(int[] nums) {
    quickSort(nums, 0, nums.length - 1);
}

private void quickSort(int[] nums, int left, int right) {
    if (right <= left) return;
    int pivot = nums[right], sortedIdx = left;
    for (int i = left; i < right; i++)
        if (nums[i] <= pivot) {
            swapWithIdx(nums, sortedIdx, i);
            sortedIdx++;
        }
    swapWithIdx(nums, sortedIdx, right);
    quickSort(nums, left, sortedIdx - 1);
    quickSort(nums, sortedIdx + 1, right);
}

private void swapWithIdx(int[] nums, int left, int right) {
    int tmp = nums[left];
    nums[left] = nums[right];
    nums[right] = tmp;
}

Complexixy Analysis

• Time Complexity

최악(Worst) : 배열nums가 오름차순으로 이미 정렬되어 있고 피벗이 가장 작은 요소일 경우 배열 nums의 길이(n)에 따른 for반복문의 실행 횟수가 n + (n - 1) + … + 1 = n(n + 1) / 2이 된다. 따라서 O(n²)의 시간 복잡도를 가진다.

평균(Average) : 피벗을 평균적인(배열의 중간에 위치한) 요소라면 최선의 경우와 같아지므로 nums의 길이(n)에 따라 O(nlogn)의 시간 복잡도를 가진다.

최선(Best) : 피벗으로 고른 요소가 항상 배열의 중간에 위치한 요소가 되면 배열 nums의 길이(n)에 따른 for반복문의 실행 횟수가 n + (n / 2) + (n / 4) + n / n = nlogn이 된다 따라서 O(nlogn)의 시간 복잡도를 가진다.

• Space Complexity

최악(Worst) : 시간 복잡도 최악의 경우에서 재귀 호출이 n번 일어나므로 메모리 내의 스택영역의 크기는 O(n)의 공간 복잡도를 가진다.

평균(Average) : 시간 복잡도 평균의 경우에서 재귀 호출이 logn번 일어나므로 메모리 내의 스택영역의 크기는 O(logn)의 공간 복잡도를 가진다.

최선(Best) : 시간 복잡도 최선의 경우에서 재귀 호출이 logn번 일어나므로 메모리 내의 스택영역의 크기는 O(logn)의 공간 복잡도를 가진다.

병합 정렬(Merge Sort)

Logic

1. 배열을 각각 하나의 요소만 포함하는 n개의 정렬된 배열로 분할한다.

2. 각각의 배열 중 2개씩 짝을 지어 정렬하여 병합한다.

3. 정렬된 배열이 하나가 남을 때까지 동일한 과정을 진행한다.

Algorithm

public void mergeSort(int[] nums) {
    mergeSortImpl(nums, 0, nums.length - 1);
}

private void mergeSortImpl(int[] nums, int left, int right) {
    if (right <= left) return;
    int mid = (left + right) / 2;
    mergeSortImpl(nums, left, mid);
    mergeSortImpl(nums, mid + 1, right);
    merge(nums, left, mid, right);
}

private void merge(int[] nums, int left, int mid, int right) {
    int[] arrL = Arrays.copyOfRange(nums, left, mid + 1);
    int[] arrR = Arrays.copyOfRange(nums, mid + 1, right + 1);
    int i = 0, j = 0, k = left;
    while (i < arrL.length && j < arrR.length)
        nums[k++] = arrL[i] < arrR[j] ? arrL[i++] : arrR[j++];
    while (i < arrL.length) nums[k++] = arrL[i++];
    while (j < arrR.length) nums[k++] = arrR[j++];
}

Complexixy Analysis

• Time Complexity

배열 nums의 길이(n)에 따라 실행되는 while반복문의 횟수는 반드시 n + (n / 2) + (n / 4) + … + (n / n) = nlogn이 된다. 따라서 모든 경우에 O(nlogn)의 시간 복잡도를 가진다.

• Space Complexity

항상 배열 nums의 길이(n)과 같은 길이의 배열을 생성해서 정렬을 수행하기 때문에 모든 경우에 O(n)의 공간 복잡도를 가진다.

힙 정렬(Heap Sort)

Logic

1. 배열을 최대 힙으로 구성한다.

2. 가장 큰 요소와 가장 작은 요소를 교환해 정렬한다.

3. 정렬된 부분을 제외한 나머지 배열에 동일한 과정을 반복한다.

Algorithm

public static void heapSort(int[] nums) {
    for (int i = nums.length / 2 - 1; 0 <= i; i--)
        heapify(nums, nums.length, i);
    for (int i = nums.length - 1; 0 < i; i--) {
        swapWithIdx(nums, 0, i);
        heapify(nums, i, 0);
    }
}

private static void heapify(int[] nums, int len, int idx) {
    int p = idx, l = p * 2 + 1, r = p * 2 + 2; // p = parent, l = left, r = right
    if (l < len && nums[p] < nums[l]) p = l;
    if (r < len && nums[p] < nums[r]) p = r;
    if (p != idx) {
        swapWithIdx(nums, p, idx);
        heapify(nums, len, p);
    }
}

private void swapWithIdx(int[] nums, int left, int right) {
    int tmp = nums[left];
    nums[left] = nums[right];
    nums[right] = tmp;
}

Complexixy Analysis

• Time Complexity

O(nlogn)

• Space Complexity

O(1)