[資料構造]Chapter 09.配置

9044 ワード
sorting データ構造 ツールバーの テキストリンク
🚨 '過去に「C言語で簡単に書ける資料構造」という本を使った授業ノートを整理した.
💡 Chapterの順序は本と同じですが、教授の過去の授業内容によっては他の内容と異なる本もあります.

1.ソートの選択（Selection Sort）


時間=比較回数=(N-1)+(N-2)+...+2 + 1 = O(N^2)

2.ソートの挿入


起動したデータは迅速に完了
for(k = 2 to N) { // [1 ~ k-1] sorted에 k를 삽입
	m = A[k];
    	for(i = k-1 down to 1) {
        	if(A[i] < m) break;
            	else A[i+1] = A[i] // shift
        }
        A[i+1] = m;
}

3.気泡ソート


2つの隣接要素を比較して繰り返し交換
for(k = 1 to N-1) {
	count = 0;
    	for(j = N down to k+1) {
        	if(A[j-1] > A[j]) {
            		swap(A[j-1],A[j]);
                    	count++;
                }
        }
        if(count == 0) break; // 완료
}

4.Shell Sort（シェルソート）


間隔(gap)でsub-listにソートを挿入->少しソートした状態ですばやく完了
for(gap = N/2; gap >0; gap = gap/2){
	if(gap == 짝수) gap++;
    	for(i=1 to gap) insertion - sort(); // gap만큼의 sub-list 존재 -> 삽입정렬
}

5.連結ソート（Merge Sort）



6.クイックソート


コミットされたデータには時間がかかります(最悪)
現実で最も速いアルゴリズム(実験データ)
QS(1,N);
QS(l,h) {
    if(l >= h) return
    m = partition(l,h);
    QS(l,m-1);
    QS(m+1,h);
}
  • 時間分析

    • 7.heap Sort（Hip Solt）


    ヒープ構成後に削除を繰り返す->O(Nlg N)

    8. BST Sort

  • A[1],…,N]のN個のデータはバイナリナビゲーションツリー(BST):O(Nlg N)
    • を構成する.
  • BSTを受注としてアクセスし、データをA(O(N)にリダイレクトする
    -> time = O(Nlg N) + O(N) = O(Nlg N)
    -> space = O(N) : BST

    • Liner Sort


    SortingからO(N)

  • 基数(=Bucket Sort)
    時間は利益であり,空間は損失である
    A[1,...,N]のN個のk-digit十進法整数


  • HashingのSortingに
    N個の整数をT[0,...,M-1]に格納して回収する(M 24579142>>>>N M=k*N (저장 사이즈))
    1 ) for all integer k, T[k] = k
    2)T[i]、i=0からM-1の順にデータを再収集する->O(M)
    -> O(M) = O(k*N) = O(N)
    • チームメンバーによって作成された新しいブランチを受信
    「python自然言語処理」ノート---chap 2テキスト語彙リソースを取得