정렬 알고리듬(2)

퀵 정렬 (중요)

평균 : O(n log n), 최악 : O(n2), 메모리 : O(log n), 안정성 : X
일반/범용적으로 가장 빠름, 분할 정복 알고리듬
어떤 값(pivot)을 기준으로 목록을 하위 목록 2개로 나눔
목록을 나누는 기준은 pivot 보다 작다/크다
위 과정을 재귀적으로 반복
재귀 단계마다 새로운 pivot 을 선정

로무토(Lomuto) 분할법
왼쪽 -> 오른쪽 방향으로만 진행하는 방식
보통 가장자리 값을 기준값으로 선택할 때 작동

호어(Hoare) 분할법
왼쪽 -> 오른쪽, 왼쪽 <- 오른쪽 방향으로 번갈아 진행하는 방식
어떤 값을 기준으로 선택해도 작동

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

private static void quickSortRecursive(int[] nums, int left, int right) {
    if (left >= right) {
        return;
    }

    //맨 우측을 pivot 으로 시작으로 파티셔닝하고 이후 왼쪽 오른쪽으로 나누어 재귀한다
    int pivotPos = partition(nums, left, right);
    //pivot 은 확정이므로 pivot -1, +1 기준한다
    quickSortRecursive(nums, left, pivotPos - 1); // 시작부터 전 피봇 인덱스 - 1 까지
    quickSortRecursive(nums, pivotPos + 1, right); // 전 피봇 인덱스 + 1 - 끝 까지
}

private static int partition(int[] nums, int left, int right) {
    int pivot = nums[right];
    int i = (left - 1);
    for (int j = left; j < right; ++j) {
        //pivot 까지 반복(왼쪽 > 오른쪽)히면서 pivot 보다 작으면 왼쪽이랑 교환
        //i 는 pivot 보다 큰 경우 숫자가 멈춰있음
        //그러므로 1,2,3,7,7,6 이고 pivot 이 7 인 경우 i = 3의 인덱스 + 1, j = 6 으로 2칸 왼쪽으로 이동 가능 
        if (nums[j] < pivot) {
            ++i;
            swap(nums, i, j);
        }
    }

    int pivotPos = i + 1;
    swap(nums, pivotPos, right);
    return pivotPos;
}

private static void swap(int[] nums, int left, int right) {
    int temp = nums[left];
    nums[left] = nums[right];
    nums[right] = temp;
}

병합 정렬

평균 : O(n log n), 최악 : O(n log n), 메모리 : O(n), 안정성 : O
입력 배열을 재귀적으로 반씩 나눠 요소수가 1인 배열을 만듦
재귀 반대방향으로 배열을 계속 합치는데 이 때 정렬 상태 유지하며 재귀의 시작점까지 모두 합친다

힙 정렬

평균 : O(n log n), 최악 : O(n log n), 메모리 : O(1), 안정성 : X
힙은 트리에 기반한 자료 구조
힙을 사용하는 정렬 알고리듬
부모 키는 자식보다 크거나 같음
많이 사용하지 않은 정렬