File:Insertion_sort.gif · Wikimedia Commons · See Wikimedia Commons
Key facts
- Class
- Sorting algorithm
- Data structure
- Array
- Worst case performance
- O ( n 2 ) {\displaystyle O(n^{2})} comparisons and swaps
- Best case performance
- O ( n ) {\displaystyle O(n)} comparisons, O ( 1 ) {\displaystyle O(1)} swaps
- Average performance
- O ( n 2 ) {\displaystyle O(n^{2})} comparisons and swaps
- Worst case space complexity
- O ( n ) {\displaystyle O(n)} total, O ( 1 ) {\displaystyle O(1)} auxiliary
- Optimal
- No
via Wikipedia infobox
Article · 日本語
挿入ソート（そうにゅうソート、英: insertion sort）あるいは基本挿入法は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。 時間計算量は平均・最悪ケースでともに Ο(n2) であり、クイックソートやマージソートなどと比べれば遅い。しかし、 * アルゴリズムが単純で実装が容易 * 小さな配列に対しては高速 * 安定 * in-placeアルゴリズム * オンラインアルゴリズム などの特徴から利用されることがある。 挿入ソートを高速化したソート法として、シェルソートが知られている。
Abstract from DBpedia / Wikipedia · CC BY-SA