Sortアルゴリズムの比較

水 14 8月 2019

Sortアルゴリズムの勉強

目的

  • Sortアルゴリズムを改めて勉強する。
    • 参考書籍「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」
  • 一覧化／およびPythonでコーディングして知識整理を行い、再コーディング時に自走出来るようにする。

アルゴリズム一覧

No アルゴリズム 方法 特徴 ソート完了タイミング 外ループ i の方向性 内ループ j の方向性 オーダー 安定か？
1 Insertion Sort 注目セルの代入箇所を確認し、トランプを先頭から並べるかのように挿入していく。 ある程度整列されたデータに対しては高速
(比較演算がデータ依存)
操作済みの部分に絞ってはソート済みの状態が出来る。		 最後 左から右（正順）
\(1{\leqq}i{\leqq}N-1\)
\(i++\)		 iを保存、i-1から左へ。（挿入箇所を探索して入れ替え）
\(i-1{\geqq}j{\geqq}0\)
\(j--\)		 \(O(n^2)\) 安定
2 Bubble Sort 未整列の残り部分の末端から先頭へ、隣同士の２つのセルを比較し、小値であれば２つを交換していく。 交換回数は反転数、転倒数と呼ばれ、列の乱れの具合を表す。 先頭から確定 右から左（逆順）
\(N-1{\geqq}i{\geqq}1\)
increment無し		 内ループ無し \(O(n^2)\) 安定
3 Selection Sort 最小のセルを抽出しながら、先頭と置き換えていく。 離れた対象を比較、入れ替えるため安定ではない 先頭から確定 左から右（正順）
\(0{\leqq}i{\leqq}N-1\)
\(i++\)		 左から右（正順）
\(i+1{\leqq}j{\leqq}N-1\)
\(j++\)		 \(O(n^2)\) 安定では無い
4 Shell Sort 対象の数列をある数値間隔 \(g\) で飛ばした数列とみなして、Insertion Sortをラフに行う。
上記をInsertion Sortの上位ループとして繰り返すことで、全体としての計算量を抑制するやり方。		 gの与え方はm段階だと（任意に）設定する。
例えば段階の数\(m=3\)のとき、\(G_i=\{13,4,1\}\)のように\(g_{n+1}=3*g_n+1\)として与える。最後の\(G_{m-1}\)は必ず1である必要がある。
この与え方で、オーダーが\(O(n^{1.25})\)になることが予測されている。		 最後 Insertion Sortを \(g\) 拡張し、上位ループを左記の\(G_i\)により回す。 略（内部ループとしてはInsertion Sortとも位置付けられるか） \(O(n^{1.25})\) 安定では無い
未検証。予想として間隔\(g\)で飛ばしたソートを含むため。

No4 Shell Sortについて

  • これだけ考え方が難しいが、きっと以下の考え方で合っている？！
    1. 対象の数列をある数値間隔 g で飛ばした数列とみなしての部分は、Insertion Sortの内部における、外ループ i（No1を参照）のそれぞれのiの界が独立だと考えられる。
      • 究極はここをマルチスレッド化しても良い？
    2. よって、Insertion Sortのある程度整列されたデータに対しては高速である特性を活かすために、以下を変数とする知見が必要になるのでは無いか？
      • どれだけ大きな数列に対し
      • どれだけラフに上記表中の \(G_i=\{13,4,1\}\) を設定するか（もちろん\(m\)もいくつに設定するか）
        • \(g_{n+1}=3*g_n+1\) の +1がきっと重要（＝ずらす意味が）あるのだろう。
          • \(g_{n+1}=3*g_n+1\) の導出に関しては、今はこれ以上は疑問を持たないこととする。

Python Coding Tips

  1. マルチライン入力
    • AIZU ONLINE JUDGEの例題を利用したため、マルチライン入力を受け付けるコードが必要となった。
    • 以下で、1行目に数列の数、2行目に数列を空白区切りで入力して受け付ける。
if __name__ == "__main__":
    # input by multi-line
    N = int(input())
    A = [int(word) for word in input().split()]
  1. アルファベット1文字＋数字1文字のデータの分解
    • H9などを2次元のlistで扱うコード。dictionaryよりlistで扱ったほうが入れ替えが出来て楽。
if __name__ == "__main__":
    # input by multi-line
    N = int(input())
    A = [int(word) for word in input().split()]
    B = [ [mark, num] for mark, num in list(A) ]
  1. listの要素の置換
    • 超基本ではあるけれど...
A[i], A[j] = A[j], A[i]
  1. listを空白区切りで出力
    • 入力と同様の形式での標準出力
print(" ".join(map(str, A)))

まとめ

学習したこと

  1. 書籍に従い、4つのアルゴリズムを整理することは出来た。
  2. 扱った中ではShell Sortが、オーダーが良いので使えると良いか？（多分、まだメリットデメリットが分かっていないかも）
  3. プログラミングに慣れる意味では、ソートアルゴリズムは良いかもしれないし、真にはもっと深いらしい。

残課題

  • WiKi参考に、まだ独自実装できていないソート。
  • うち赤字は何となく手を出したい気がするもの。
    • 交換
      • シェーカーソート
      • コムソート
      • ノームソート
      • 奇遇転置ソート
      • シェアソート
    • 挿入
      • ２分木ソート（平衡２分探索木）
      • 図書館ソート
      • ペイシェンスソート
    • マージ
      • マージソート
        • 分解と併合によるもの。
      • In-placeマージソート
    • 選択
      • ヒープソート
        • 二分木を使う。
      • スムースソート
      • ストランドソート
    • パーティショニング
      • クイックソート
        • ピボットで分割、中央値等の工夫。
    • 混成
      • イントロソート

以上

social