[Java] 정렬 - 퀵, 병합

1. 퀵 정렬 Quick sort

pivot 값을 기준으로 pivot의 앞과 뒤에 더 작거나 큰 값을 모으는 방식으로
재귀를 이용하여 완성

- 시간복잡도: O(n²) / O(nlogn)

 

// 두 값의 자리를 바꾸는 함수
public static void swap(int [] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

public static int partition(int[] arr, int start, int end) {
    int pivot = start;
    int left = start + 1;
    int right = end;

    while (left <= right) {
        while (left <= right && arr[left] <= arr[pivot]) left++;
        while (left <= right && arr[right] >= arr[pivot]) right--;
        if (left > right) swap(arr, right, pivot);
        else swap(arr, right, left);
    }

    return right;
}

public static void quickSort(int[] arr, int start, int end) {
    if (start >= end) return;
	
    // pivot값을 구하는 partition 함수
    int pivot = partition(arr, start, end);
    
    // pivot 전까지, 다음부터 각각 나누어서 다시 정렬
    quickSort(arr, start, pivot - 1);
    quickSort(arr, pivot + 1, end);
}

quickSort(arr, 0, N - 1);

2. 병합 정렬 Quick sort

배열을 분할하여 정렬하면서 다시 병합
재귀를 이용하여 완성

- 시간복잡도: O(nlogn)

import java.util.Arrays;

public class MergeSort {
    static void mergeSort(int[] arr, int[] temp, int start, int end) {
        // start가 더 커진 경우 (분할 끝난 경우 return)
        if (start >= end) return;

        // divide
        int mid = (start + end) / 2;
        mergeSort(arr, temp, start, mid);
        mergeSort(arr, temp, mid + 1, end);

        // conquer
        int left = start;
        int right = mid + 1;
        int idx = start;    // 실제 삽입할 인덱스

        while (left <= mid || right <= end) {
            // left가 먼저 mid보다 커진 경우: right 소진
            if (left > mid) {
                temp[idx++] = arr[right++];
            }

            // right가 먼저 end보다 커진 경우: left 소진
            else if (right > end) {
                temp[idx++] = arr[left++];
            }

            // 작은 수부터 정렬 기준 -> left가 더 크면 right 먼저 삽입
            else if (arr[left] > arr[right]) {
                temp[idx++] = arr[right++];
            }

            else if (arr[left] < arr[right]) {
                temp[idx++] = arr[left++];
            }
        }

        // 완료한 후에는 arr에 temp 반영시키는 것 잊지 말 것!
        for (int i = start; i <= end; i++) {
            arr[i] = temp[i];
        }
    }

    public static void main(String[] args) {
        int[] arr = {4, 7, 6, 2, 8, 3};
        int[] temp = new int[arr.length];

        mergeSort(arr, temp, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}