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 の + 1 しない場合のようになる
  - 小結：x、y は両方とも動かなければならず、x が動かないとスタックオーバーフロー、y が動かないと無限ループになる
  - 【個人的理解、考慮不足、議論歓迎】
三分探索 —— 練習問題
- まず境界を決定：INT32_MIN ~ INT32_MAX
- 後は三分探索の手順に従うだけ
- 境界の考察
  - 公式 - b / 2a で推定するが、少しズルをする疑いがある
  - 二次関数 = 0 の二つの解で範囲を決定するが、複雑になる
  - 三分探索の効率は logN レベルで、境界範囲の大きさはあまり影響しない

ヒント#

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

コース速記#

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