泡の位置合わせ

2つの隣接する要素を検査してソートするアルゴリズム.

さぎょうモード

コード#コード#

public static void bubbleSort(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j < arr.length - i - 1; j++) {
            if (arr[j] > arr[j+1]) {
                int tmp = arr[j+1];
                arr[j+1] = arr[j];
                arr[j] = tmp;
            }
        }
    }
}

時間の複雑さ

O(N^2)

整列挿入

位置合わせされた部分と比較して、自分の位置の位置合わせを検索して挿入します.

さぎょうモード

コード#コード#

void insertionSort(int[] list) {
    // 인덱스 0은 이미 정렬된 것으로 본다
    for (int i = 1; i < list.length; i++) {
        key = list[i]; //현재 삽입될 숫자인 i번째 정수를 key 변수로 복사
        
        int j = i - 1;
        
        while (j >= 0 && key < a[j]) {
            a[j+1] = a[j] //이전 원소를 한 칸씩 뒤로 민다.
            j--;
        }
        
        // 반복문 탈출하는 경우 앞으 원소가 타겟보다 작다는 의미다. 
        // 타겟 원소는 j 번째 원소 뒤에 와야 한다. 
        a[j+1] = key;
    }
}
            

時間の複雑さ

O(N^2)

連結ソート

アクションの理解

分過程と合過程の構成
実際、ソートされた時点は、2つのリストをマージするフェーズです.

コード#コード#

public class test_2 {

    public static void main(String[] args) throws Exception {

        int[] arr = new int[] {1, 3, 5, 7, 9, 2, 4, 6, 8, 10};
        int[] answerArr = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, answerArr);
        Arrays.stream(arr).forEach(e -> System.out.print(e + " "));
    }

    private static void mergeSort(int[] arr, int l, int r, int[] answerArr) {
        if (l == r)
            return;

        int mid = (l + r) / 2;
        mergeSort(arr, l, mid, answerArr);
        mergeSort(arr, mid + 1, r, answerArr);
        merge(arr, l, mid, r, answerArr);
    }

    private static void merge(int[] arr, int l, int mid, int r, int[] answerArr) {
        int first = l;
        int second = mid + 1;
        int index = l;

        while (first <= mid && second <= r) {
            if (arr[first] < arr[second]) {
                answerArr[index++] = arr[first++];
            } else {
                answerArr[index++] = arr[second++];
            }
        }

        while (first <= mid) {
            answerArr[index++] = arr[first++];
        }

        while (second <= r) {
            answerArr[index++] = arr[second++];
        }

        for (int i = l; i <= r; i++) {
            arr[i] = answerArr[i];
        }
    }
}

パフォーマンス分析

連結ソートには追加のメモリが必要です.

コードで確認できます.「≪データのマージ|Merge Data|emdw≫」セクションでは、マージ・サイズに対応する一時配列が必要です.すなわち、上記の図では、1行で追加的に使用されるメモリの和は、データサイズ全体に相当するNである.
時間複雑度O(Nlogn)

ループ呼び出し深さ→log 2 Nlog 2 Nlog 2 N

N個のデータを1個まで2等分する.
k回が二等分だと思ったら、ループコールの高さに相当します.
式で次のように表す
N×12k=1N\times{\frac12}^k = 1N×21​k=1
N=2kN = 2^kN=2k
log2N=klog_2N = klog2​N=k

連結ステージ毎の比較演算回数→N

マージされたすべてのデータが移動されます.
1行のすべての演算回数を加算するとNになります.

全時間複雑度=ループ呼び出し深さxの各マージステップにおける移動演算=nlog 2 nlog 2 nlog 2 n

速達

リストで、1つの要素をpivot、小さな要素を左、大きな要素を右に配置します.軸を基準にして、2つの部分について同じ操作を繰り返します.(在貴)

アクションの理解

コード#コード#

public class QuickSorter {
    public static void quickSort(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }
    
    private static void sort(int[] arr, int low, int high) {
        if (low >= high)
            return;
        
        int pivot = partition(arr, low, high);
        sort(arr, low, pivot - 1);
        sort(arr, pivot + 1, high);
    }
    
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[left];
        while (low <= high) {
            while (arr[low] < pivot)
                low ++;
            while (arr[high] > privot)
                high --;
            
            if (low <= high) {
                swap(arr, low, high);
                low++;
                high--;
            }
        }
        swap(arr, left, high);
        return high;
    }
    
    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        int[i] = arr[j];
        arr[j] = tmp;
    }
}

パフォーマンス分析

ピボットをデータの中心にし続けると、
正確には、データは2等分であるため、再帰呼び出しの深さはlog 2 nlog 2 nlog 2 nであってもよい.
ただし、軸心を片側に偏った値に設定し続けると、
ループ呼び出しが深くなるたびに、データが失われ、最終的にはN深さになります.

###時間の複雑さを知る：最適状況→O(nlogn)O(nlogn)O(nlogn)

時間の複雑さを知る:最適→O(nlogn)

時間の複雑さを知る:最悪の場合→O(n^2)

軸を片側に傾け続けると、最悪の場合があります.
最悪の場合、ソートされた配列をソートしようとすると


https://www.youtube.com/watch?v=7BDzle2n47c

これまでのソートアルゴリズムの解析

quick sort

時間の複雑さ、なぜ最悪の場合はO(N 2)O(N^2)O(N 2)ですか?
Pivotが引き続き傾斜した価格で捉えられると、
再帰呼び出しの深さはNまで深まります.
同じ再帰呼び出し深さでのすべての演算はO(N)である.
これをN回繰り返した結果,O(N 2)O(N^2)O(N 2)であった.
空間複雑度はO(logn)O(logn)O(logn)ですか?
→再帰呼び出しの深さがlognであるため、lognに対応するスタックメモリを追加する必要がある
quick sortは、データを二等分的に再帰的に実行する.
このとき,再帰呼び出しの深さは「データ数が1になるまでの2等分数」である.
したがって、log 2 nlog 2 nlog 2 n回をループ呼び出します.
すなわち,log 2 nlog 2 nlog 2 n n個のメモリ空間をスタックで割り当てる必要があるため,O(log 2 N)O(log 2 N)O(log 2 N)O(log 2 N)である.

merge sort

なぜ空間複雑度がO(N)O(N)O(N)なのか.
マージ中は、データを一時的に格納するスペースが必要です.
同じ再帰呼び出し深さで、必要なすべてのデータ空間はNである.
必要な追加メモリはO(N)です.

Heap Sort

なぜheap sortはquick sort、merge sortより少し遅いのですか?
→https://d2.naver.com/helloworld/0315536参照

チーム

分割により,小部分に挿入sortを用い,全体的に合併sort方式を採用した.挿入sortを使用するのは,領域参照性が良好であるためである.
https://d2.naver.com/helloworld/0315536

その他

Javaでsort

Arrays.sort()

まずは並ぶArrays.sortについて説明しましょうArrays.sortのコードをチェックすると、コメントとコードは次のようになります.これは、2軸心を使用して迅速にソートされることを示しています.2つのピボットを持つ2つのピボットを持つ2つのピボットのクイックソートとは異なり、3つのセグメントを作成してクイックソートします.このソート方法はランダムデータの平均性能に対して高速ソートよりも優れている.
https://sabarada.tistory.com/138

Collections.sort

連結ソートとTimソートを従来のソートとして用いることを見出した.[レイヤソート](Layer Sort)は、[挿入](Insert)と[合成](Merge)のソートを組み合わせて作成されたソートです.Java 7からTimソートを使用

Arrays.sort() VS Collections.sort()

では、なぜArraysとCollectionをソートする際に使われるアルゴリズムが違うのでしょうか.これが「参照領域原理」(Local of Reference)の原因である.参照領域の原理は、同じ値またはその近傍の記憶位置に頻繁にアクセスする特性を指す.この参照領域の原理は、CPUのキャッシュポリシーに依存します.これは、CPUがデータにアクセスし、隣接メモリのデータ(これらのデータだけでなく)をキャッシュに格納することを意味する.
並べ替えの実際の操作時間をC*時間複雑度+aと呼ぶ.時間の複雑さは既知であり、相対的に無視することができる.しかし,Cを乗じた影響を考慮しなければならない.そう思わざるを得ない.参照領域の原理は、この値Cに影響します.
ArrayのC値は、メモリに連続したアドレスがあるため、低いです.したがって、参照領域性を有する高速ソートは、十分なパフォーマンスを提供することができる.ただし、Collectionは独立したリンクリストであり、メモリに隣接するArrayListだけでなく、メモリに分散したLinkedListにも存在する.したがって,参照隣接性は劣り,Cの値は相対的に高い.この場合、統合ソートと挿入ソートを組み合わせた階層ソートを使用して、迅速なソートではなく、より良い平均パフォーマンスを得ることができます.

メルキソットとQuickソットを比較してください。

速達

Quick Sortは2段階からなる.
まず、ソート範囲でピボットを決定し、ピボットの左側にピボットより小さい数値を配置し、右側に大きな数値を配置します.このときの総演算回数はN回である.
第2に、各範囲に第1のステップを再帰的に適用する.
このとき,同一ループ呼び出しフェーズのすべてのデータ範囲に第1ステップを適用すると,すべての比較演算回数を加算してもN回となる.
したがって,軸心によって並べ替え範囲を最大限に半分に分け,ループ呼び出しの深さを低減することが重要である.
ピボットをソート範囲の中央データに設定し続けると、logn回だけですべてのソート範囲を1に設定できます.各ループ呼び出しステップの合計演算がNであるため、ソート性能はNlognです.

メシソット

メジソトはデータの中心を基準にデータを半分に分けた.
範囲が1になるまで再帰します.
各範囲を結合して並べ替え、同じループ呼び出しフェーズのすべての演算回数がO(N)である.
マギーソットはデータを正確に半分に分割するため,ループ呼び出しの深さはlognによって保証されるため,全体的な性能はNlognである.

比較

高速ソートには、追加のスペースはほとんど必要ありません.しかし,メルジソトはデータをマージする際に一時配列にデータを含める必要があるため,O(N)の付加データが必要である.
Quick Sotはキャッシュ領域性を最大限に活用するという.

キャッシュからローカルに比較

https://medium.com/pocs/locality%EC%9D%98-%EA%B4%80%EC%A0%90%EC%97%90%EC%84%9C-quick-sort%EA%B0%80-merge-sort%EB%B3%B4%EB%8B%A4-%EB%B9%A0%EB%A5%B8-%EC%9D%B4%EC%9C%A0-824798181693
結論:クイックツールのメモリクエリーの範囲は大きくありません.ソートは再帰的に実行されますが、ソート順の範囲です.しかし、メジソットはメモリクエリの開始と終了の間で繰り返している.したがって、キャッシュ領域の利用は高速接続よりも難しい.これは大きな雑音における定数(A＊NlogN＋B)におけるAとBの部分などの定数値の増加の要因であることが知られているので,平均性能はQuick Sotに及ばない.