📓 memotty

ソートアルゴリズムを途中経過から見分ける

ソートアルゴリズムは、1 パス後の配列を見ればどれが使われたか判別できる。応用情報でも途中経過を見せてアルゴリズムを当てさせる形式が多く、問題文を読み込むより未確定部分の荒れ具合と計算量を先に覚えておくほうが速く解ける。

未確定部分の荒れ具合で見分ける #

1 パス後の配列を見るとき、確定した部分ではなく未確定の部分がどれだけ動いたかを見る。

  • バブル: 端が 1 つ確定し、未確定部分も細かく入れ替わっている。隣接交換を積み重ねるので通り道が全部動く
  • 選択: 端が 1 つ確定し、未確定部分は 1 箇所しか動いていない。1 パスの交換が 1 回だけだから
  • 挿入: 先頭から整列済みが伸び、後ろは元の並びのまま。未処理の領域を一切触らない
  • マージ: 2 要素ずつ、次は 4 要素ずつ、整列済みのブロックができていく
  • クイック: 1 要素だけ正しい位置に来て、その左右が基準値より小さい群と大きい群に分かれる
  • シェル: 離れた位置の要素同士が入れ替わっている。隣接でない交換はシェルだけ

バブル・選択・挿入はどれも 1 パスで端が確定するため、確定部分を見ても区別できない。未確定部分が全体的に動くか、1 箇所だけ動くか、まったく動かないかで分かれる。

計算量と安定性を押さえる #

平均最悪安定
バブルO(n^2)O(n^2)○
挿入O(n^2)O(n^2)○
選択O(n^2)O(n^2)×
シェルO(n^1.3) 程度間隔の決め方による×
クイックO(n log n)O(n^2)×
マージO(n log n)O(n log n)○
ヒープO(n log n)O(n log n)×

安定とは、値が等しい要素の元の順序が保たれること。安定なのはバブル・挿入・マージの 3 つだけ。

引っかけの定番を知る #

  • クイックソートの最悪は O(n^2)。すでに整列済みのデータで基準値に端の要素を選び続けると分割が偏る。「常に O(n log n)」という選択肢は誤り
  • マージソートは O(n) の作業領域が必要。「追加の記憶領域を必要としない」はヒープソートの特徴
  • シェルソートは挿入ソートの改良版だが安定ではない。離れた要素を交換するため等しい要素の順序が入れ替わる

バブルソートの走査方向はどちらでもよい #

左端から隣同士を比較して大きい値を右へ送る形が標準的だが、右端から始めて小さい値を左へ送っても正しくソートできる。1 パスで確定する端が逆になるだけで、計算量は変わらない。

func bubbleSort(a []int) {
	for i := 0; i < len(a)-1; i++ {
		for j := 0; j < len(a)-1-i; j++ {
			if a[j] > a[j+1] {
				a[j], a[j+1] = a[j+1], a[j]
			}
		}
	}
}

1 パスで大きい値が右端に確定するので、内側ループの上限を len(a)-1-i に縮められる。右から左へ走らせる場合は確定領域が左側になるので、内側ループの下限を上げていく。

1 パスの中で向きを変えて往復させるのは別アルゴリズムで、シェーカーソート(カクテルソート)と呼ぶ。

比較を > にすると値が等しいときに交換しないので安定になる。>= にすると安定性が崩れる。

擬似言語で問われたときに備える #

午後問題では判別ではなく穴埋めになるので、ループの境界条件を自分で書けるようにしておく。バブルなら内側ループの上限が len(a)-1-i、挿入なら整列済み部分を後ろへずらして空いた位置に入れる流れを添字レベルで追えればよい。