ソートアルゴリズム(2)

クイックソート(重要)

平均:O(n logn)、最悪:O(n 2)、メモリ:O(logn)、安定性:X
一般/汎用的な最速分割征服アルゴリズムリズム
ある値(pivot)でリストを2つのサブリストに分割する
ディレクトリの分割基準がpivotより小さい/大きい
上記の手順を繰り返します
回帰フェーズごとに新しいピボットを選択
Lomuto分割法
左から右へ
通常、エッジ値を基準値として選択した場合の操作
アーク分割法
左->右、左<-右
任意の値から選択可能

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 logn)、最悪:O(n logn)、メモリ:O(n)、安定性:O
入力配列を2つの部分に再帰的に分け,1つの要素数が1の配列である.
配列を再帰的に反転してマージし続け、再帰の開始点までソート状態を維持します.

お尻の位置合わせ

平均:O(n logn)、最悪:O(n logn)、メモリ:O(1)、安定性:X
HIPはツリーベースのデータ構造です
hipを用いたソートアルゴリズムのリズム
親が子以上
非アクティブソート