読者です 読者をやめる 読者になる 読者になる

大学院生(情報科学)のブログ

モチベーション維持のためのブログです。

・ソーティング問題の定式化と言葉の定義

入力: {n}個の数の列({a_{1},a_{2},\cdots,a_{n})}
出力: {a_{1}^{'} \leq a_{2}^{'} \leq \cdots \leq a_{n}^{'}} である入力列の置換({a_{1}^{'},a_{2}^{'},...,a_{n}^{'})}

キー(key):ソートしたいと思っている数値

・挿入ソート
少数の要素を効率よくソートするアルゴリズム

ex) トランプの手札をソート

  1. 左手を空にする
  2. 裏向きに置かれたカードを1枚ずつ引き、左手の正しい位置に挿入
  3. 正しい位置は右から左へと順に既に持っているカードと比較する

以下にpythonで書いたinsert_sortを示す.
引数にはソートする長さ{n}の配列を取る.
アルゴリズムは入力された数列をその場でソートする.
出力はソートされた配列が返される.

def insert_sort(A):
		for j in range(1,len(A)):
			key = A[j]
			i = j - 1
			while i >= 0 and A[i] > key:
				A[i+1] = A[i]
				i = i - 1
			A[i+1] = key
		return A

実行結果
Input:[5, 2, 4, 6, 1, 3]
Output:[1, 2, 3, 4, 5, 6]

アルゴリズムの正当性を示すことは次にまわす.