getaji / learn-algorithms Goto Github PK

シェーカーソート (英: shaker sort) は、ソートのアルゴリズムの一つ。バブルソートを、効率がよくなるように改良したもの。別名は、双方向バブルソート、改良交換法。

バブルソートではスキャンを一方向にしか行わないのに対し、シェーカーソートでは交互に二方向に行う。バブルソートと同じく安定な内部ソートで、最悪の場合の時間計算量はO(n2)である。

シェーカーソート - Wikipedia

コムソート（英: comb sort）やコームソートや櫛（くし）ソートは、ソートのアルゴリズムの一つ。1980年に Włodzimierz Dobosiewicz が発表し、1991年に Stephen Lacey と Richard Box が再発見しコムソートと命名した。

バブルソートの改良版。内部ソートだが、安定ソートではない。実行速度は、ほぼO(n log n)になる。

コムソート - Wikipedia

型チェックをしたい。

選択ソート（英: selection sort）は、ソートのアルゴリズムの一つ。 配列から最小値を探し、配列の先頭要素と入れ替えていくことで並べ替える。

最悪時間計算量は O(n2) と遅いため、一般にはクイックソートなどのより高速な方法が利用される。しかし、空間計算量が限られるため他の高速な手法が使えない場合や、ソートする配列が充分小さく、選択ソートが高速に動作することが保証されている場合に利用されることがある。

選択ソートは内部ソートである。また、安定ソートではない。

選択ソートの改良として、ヒープソートが挙げられる。

また、各ループ毎に最小値と最大値との両方を探し、両端の要素を同時に確定させる手法もあり、double selection sortと呼ばれる。

選択ソート - Wikipedia

両方実装する。

隣接する要素と比較し順序が逆であれば入れ替える。これを要素数-1回繰り返すことでソートを行なう。なおこの繰り返しは、入れ替えが起こらなくなった時点で（それ以降は何度繰り返しても変化が起こらなくなるので）中断することができる。

バブルソート - Wikipedia

線型探索（せんけいたんさく、英: linear search, sequential search）は、検索のアルゴリズムの一つ。 リストや配列に入ったデータに対する検索を行うにあたって、 先頭から順に比較を行い、それが見つかれば終了する。

n個のデータからm個のデータを検索する場合、時間計算量は O(nm) 、空間計算量は O(1) である。

線型探索 - Wikipedia

ノームソート（英: gnome sort）はソートアルゴリズムの一種で、挿入ソートに似ているが、要素の移動は挿入ではなくバブルソートのような一連の交換で行う。その名称の由来は、オランダのノームが一列に並んだ鉢植えの花をソートする話である。

（試訳）「ノームソートは一般的なオランダのガーデンノーム（蘭: tuinkabouter）が使う技法に基づいている。以下がガーデンノームが植木鉢の列を並べ替える方法である。基本的に、ノームは自分の前に並んでいる植木鉢と後ろに並んでいる植木鉢を見る。もしそれらの順序が正しいなら、ノームは植木鉢一つ分だけ前に移動するが、そうでない場合は、それら二つの植木鉢の位置を交換してから、自分は植木鉢一つ分だけ後ろに移動する。境界条件：　もし後ろに植木鉢がない場合ノームは前に移動する；　もしノームの前に植木鉢がなかったら並べ替えは完了である。」

ノームソート - Wikipedia

バケットソート（英: bucket sort）は、ソートのアルゴリズムの一つ。バケツソート、ビンソート（英: bin sort）などともいう。バケツ数 k 個使った場合、オーダーはO(n + k)となり、ソートする要素数nとk を無関係にできる場合線形時間ソートとなるが、要素間の全順序関係を用いるソートとは異なり、キーの取りうる値がk種類である、という入力により強い制限を要求するソートである。

https://ja.wikipedia.org/wiki/%E3%83%90%E3%82%B1%E3%83%83%E3%83%88%E3%82%BD%E3%83%BC%E3%83%88