4 ソートと検索

コース内容#

ソート#

四象限原則：安定 / 非安定、内部 / 外部
- 安定：同じ要素のソート前後の相対位置が変わらない
- 内部：データ全体をメモリにロードしてソートする必要がある

【小から大へのソートを考慮】

安定ソート#

挿入（内部）
- 前：ソート済み領域；後：ソート待ち領域
- 後ろの数が前で位置を探して空きを挿入
  - 一つずつ比較、交換し、【挿入】の効果を実現
  - 直接挿入位置と交換するのではなく、これではソート済み領域の順序が乱れる
- 平均時間計算量：O (N^2)
バブル（内部）
- 前：ソート待ち領域；後：ソート済み領域
- 最初の要素から後ろに進み、最大要素をソート済み領域の最前に、ソート待ち領域の最後に置く
- N - 1 ラウンドのバブルを行い、各ラウンドでソート済みに一つの要素を追加
  - 【最適化】あるラウンドのバブルプロセスで交換操作が行われなかった場合、直接終了できる
- 平均時間計算量：O (N^2)
  - 最適時間計算量：O (N)←ソート済み
  - 最悪時間計算量：O (N^2)←完全逆順
- 挿入ソートは逆バブルと理解できる
マージ（外部）
- 前提：二つのソート済み配列（長さそれぞれ m、n）を一つのソート済み配列にマージ
  - 時間計算量：O (m + n)
- まず分治して二つずつ比較できるようにし、次にソート済み配列を二つずつマージ
- 時間計算量（最適、最悪、平均ともに）：O (NlogN)
  - 合計 logN 層、各層のマージ時間は O (N)
- 【外部ソート】2 路マージ（上記）、k 路マージ（多路マージ、ヒープを利用）
  - 参考外部マージソート- ウィキペディア、各ルートのソート方法は任意で、最終的にマージ
  - 実際、この外部ソートの有無はあなたがしたいかどうか、必要かどうかによるが、それは可能である

不安定ソート#

選択（内部）
- 前：ソート済み領域；後：ソート待ち領域
- 各ラウンドでソート待ち領域から最小の要素を選び、ソート待ち領域の最初の要素と交換
  - 自身と自身の交換が発生する可能性があるため、交換関数は排他的論理和を使用できない
- 不安定：例えば 22'1、最初の交換後、2 は 2' の後ろに移動し、つまり 12'2
- 時間計算量（最適、最悪、平均ともに）：O (N^2)
- 一般的にバブルより優れており、比較回数はほぼ同じだが、バブルの交換が頻繁すぎる
クイックソート（内部）
- 【基準値、パーティション】
  - 最初の要素を基準値として取り出す
  - 【尾指標】は後ろから前に基準値より小さい要素を探し、最初の要素の位置（空いている）に置く、【頭指標】は前から後ろに基準値より大きい値を探し、空いた位置に置く、ループ
  - 最後に頭と尾の指標が重なり、空いている位置に基準値を置く
  - 次に基準値の左右の部分に対して同様の操作を行う
- 時間計算量：O (NlogN)
  - 逆順列で最初の要素を基準値に選ぶと、選択ソートに退化し、O (N^2)
- 【最適化】
  - 基準値をランダムに選ぶ
  - 再帰の使用を減らし、ループで行う
  - 左右で交換する値を見つけた後に交換する

検索#

素朴な二分探索
- 前提：単調列
- 検索する値が列の中で重複して存在する場合、二分探索ではどれを見つけたかを区別できない
特殊な二分探索
- 11110000
  - 仮想の頭指標を導入し、インデックスは - 1
  - mid の計算には + 1 が必要で、無限ループを避ける、例えば 10 のケース
- 00001111
  - 仮想の尾指標を導入し、インデックスは n [配列範囲は 0 ~ n - 1]
- 参考《面接筆記アルゴリズム上》——2. 二分専題
- ここでは参考内容に加えて仮想指標の概念を追加し、検索の境界 [-1 ~ n -1 または 0 ~ n] を変更することで、値が見つからない場合の状況を反映できる
三分探索
- 【凹凸関数の極値点を求める】問題を解決
- 元の問題の規模を三分の一に分ける
- 更新戦略：値が小さい要素ともう一方の区間を保持；停止条件：|m1 - m2|< ESPL
- 時間計算量：O (log [3] N)、二分探索の O (log [2] N) より少し遅い

ハッシュテーブル#

検索のための【データ構造】
構造定義
- 要素を格納するために連続した空間が必要
- 順序表と一致し、要素の型は可変
構造操作
- ハッシュ関数：任意の型の要素を整数値 [配列インデックス] にマッピングできる
  - その後、特定の値を対応する配列インデックスに格納できる
  - 配列インデックスは整数型のみ
- 衝突処理方法
  - オープンアドレッシング【一般的】：後ろに空きがあるか見て、二次探索法など... しかしデータの堆積問題が発生しやすい
  - 再ハッシュ：別名ハッシュ法、複数のハッシュ関数を使用
  - チェイン法【一般的】：連結リスト構造を使用して各位置の要素を格納
  - 公共のオーバーフロー領域を設立：衝突した要素を特定の領域に統一して置く
検索の時間計算量：O (1) に近づく
- その他の時間：ハッシュ関数の変換、チェイン法 [連結リスト要素の検索] または他の衝突処理方法による時間
- 配列、順序表のみが O (1) である
ハッシュテーブルの空間利用率は一般的に 50〜90%
- ハッシュ関数には必ず衝突が存在し、空間を開く際には余裕を持つ必要がある
- 利用率が 70% に達すると、工業的に使用できるようになり、衝突が少ないほど、利用率が高く、ハッシュ関数が優れている

コードデモ#

安定ソート#

詳細は注釈と赤枠で示す
安定ソートの安定性を保証するために、== の状況に注意し、交換できない [または元の順序を保証する]！
【注意】TEST マクロを呼び出す際、後の配列は num で、これはマクロ定義内で arr をコピーして得た配列である！

不安定ソート#

V1.0 版：選択ソート & クイックソート通常版#

クイックソートアルゴリズムに重点を置き、多くの最適化ポイントがある
- 【自己最適化】46、48 行の num []> z または num [] < z に == 条件を追加でき、等しい要素に出会ったときに交換しないようにし、交換する必要もなく、アルゴリズムの安定性をできるだけ保つことができる [ただしクイックソートは不安定]
- 【最適化ポイント】基準値の選択、再帰→ループ、交換方法

V2.0 版：クイックソート最適版#

上述の 3 つの最適化ポイントを実現
いくつかの境界の == に注意：x <= y、num [] < z、num [] > z
- ❓== の判断はどう理解するか？詳細は以下の思考ポイント 2 を参照
第 39、40 行：右区間をソートし、ソート後に右境界を縮小

2 つのバージョンのクイックソートの速度比較#

ランダム列と逆順列をそれぞれテスト
- 20 万サイズのランダム列：両者の差はほとんどない
- 10 万サイズの逆順列：明らかな違い
  - 20 万の逆順列に対して、元のクイックソートはスタックオーバーフローを引き起こす

二分探索#

仮想指標の使用により、答えがない場合 [000000] が偽の答え [0 または n - 1] を返す状況を避けることができる
11110000 のケースでは、mid を計算する際に + 1 が必要で、無限ループに陥るのを避ける、例えば 10
詳細は《面接筆記アルゴリズム上》——2. 二分専題を参照

文字列のハッシュテーブルを作成#

ハッシュ関数：BKDR-Hash、衝突処理方法：チェイン法
値を挿入する際に使用されるのは頭挿入法
ハッシュテーブル構造の利用率は 100% には達しないため、開く空間は倍にする必要がある
calloc でハッシュテーブルの空間を開くことで、各位置の連結リストの先頭アドレスを空にし、安全にすることができる
ハッシュ関数は自分で設計することができる

思考ポイント#

【自分の理解】安定ソートの安定性を保証するために、== の状況に注意し、交換できない [または元の順序を保証する]！
❓クイックソート最適版の境界に関する考察
- 同様に通常版クイックソートの最適化境界判断に従い、以下の最適化の考え方には問題があり、通常版では実現可能である
  - 32 - 33 行：num [] < z と num [] > z をそれぞれ <= と >= に変更すると、【セグメンテーションフォルトまたは無限ループ】が発生する
    - num [] <= z 【無限ループ】
      - 例：2 1、基準値が 2 のとき、左指標 x は右端まで進み、境界を越え、右指標 y は変わらず、第 27 行 while (l < r) が成立し、x は再び l に戻り、無限ループになる
    - num []>= z 【セグメンテーションフォルト —— スタックオーバーフロー】
      - 例：1 2、基準値が 1 のとき、右指標 y は左端まで進み、-1 になり、左指標 x と r は変わらず、第 39 行 quick_sort (num, x, r) が繰り返し呼び出され、最終的にスタックオーバーフローになる
    - 原因分析：通常版では基準値を取り出しており、最適版では基準値が内部に残っているため、この違いを考慮する必要がある
  - 32 - 34 行：x <= y を x < y に変更すると、【セグメンテーションフォルト】が発生する
    - 例：2 3、基準値が 2 のとき、x、y はそれぞれ 2、3 を指し、ループを経て、x、y は両方とも 2 を指し、x と r は変わらず、第 39 行 quick_sort (num, x, r) が繰り返し呼び出され、最終的にスタックオーバーフローになる
    - 原因分析：x、y はずれなければならず、そうでなければ特殊な二分 111000 のような状況になる
  - 小結：x、y は両方とも動かなければならず、x が動かないとスタックオーバーフロー、y が動かないと無限ループになる
  - 【個人的理解、考慮が不十分、議論歓迎】
三分探索 —— 練習問題
- まず境界を確定する：INT32_MIN ~ INT32_MAX
- 後は三分探索の手順に従えばよい
- 境界の考察
  - 公式 - b / 2a で推定するが、少しズルをする疑いがある
  - 二次関数 = 0 の二つの解で範囲を決定するが、複雑になる
  - 三分探索の効率は logN レベルで、境界範囲の大きさはあまり影響しない

ヒント#

十大クラシックソートアルゴリズム（アニメーションデモ）-cnblogs
十大クラシックソートアルゴリズムのアニメーションと解析、私を見れば十分- 五分でアルゴリズムを学ぶ

コース速記#

事前にヒープと優先キュー、さらに並列集合の内容を予習すること