Home-theater-designers
挿入ソートは、ソートされたサブリストを利用し、リスト全体がソートされるまで、ソートされていないリストから継続的に値を追加することによって機能する手法です。
アルゴリズムは、ソートされたサブリストとして最初のリスト項目から始まります。次に、次の番号を最初の番号と比較します。大きい場合は、最初のインデックスに挿入されます。それ以外の場合は、インデックスに残ります。
次に、3番目の値が他の2つと比較され、正しいインデックスに挿入されます。このプロセスは、リスト全体がソートされるまで続きます。
挿入ソートの詳細
上記の説明はあなたには意味がないかもしれません。例はあなたがはるかによく理解するのに役立つはずです。
リストがあるとします：[39、6、2、51、30、42、7]。
アルゴリズムは、ソートされたサブリストの最初の値として39を識別します。次に、評価は2番目の位置に移動します。
関連：動的計画法：例、一般的な問題、および解決策
次に、6が39と比較されます。6は39未満であるため、6が最初の位置に挿入され、39が2番目の位置に挿入されます。新しいリストの順序は、最初のパスが次のようになった後です。
[6、39、2、51、30、42、7]
評価は3番目の位置に移動します。 2は、最後の2つの数値と比較され、正しい位置に挿入されます。新しいリストの順序は、2番目のパスが次のようになった後です。
[2、6、39、51、30、42、7]
3番目のパスの場合、リストの順序は次のとおりです。
[2、6、39、51、30、42、7]
このプロセスは、リスト全体がソートされるまで繰り返されます。
これらの操作を要約した以下の図を参照してください。
アルゴリズム分析
挿入ソートの時間計算量はO（n2）、 と同じように バブルソート 。最悪のシナリオでの比較の数は、1から（n-1）までのすべての整数の合計であり、2次の合計になります。
コードの実装
以下のPythonおよびJavaコードは、挿入ソートメソッドを実装する方法を示しています。
Python：
def insertionSort(mylist):
for step in range(1, len(mylist)):
current_element = mylist[step]
position = step
while position > 0 and mylist[position - 1] > current_element:
mylist[position] = mylist[position - 1]
position = position - 1
mylist[position] = current_elementJava：
void insertionSort(int[] myarray) {
int n = myarray.length;
for (int x = 1; x int key = myarray[x];
int y = x-1;
while ( (y > -1) && ( myarray [y] > key ) ) {
myarray [y+1] = myarray [y];
y--;
}
myarray[y+1] = key;
}
} 擬似コードによるより良いコーディング
上記のコード例は、他の言語でこのアルゴリズムを作成するために参照できる擬似コードなしで提供されています。ほとんどのプログラマー（著者を含む）は、プログラムがどのように機能するかについて「ささやき」と言われた後、キーボードに向かって走るのが好きです。
このアプローチは、プログラムロジックがより複雑になるため、残念ながらエラーが発生しやすくなります。擬似コードの使い方を学び、プログラミングゲームをどのようにレベルアップしたいですか？
共有 共有 つぶやき Eメール 擬似コードとは何ですか？それはどのようにしてあなたをより良い開発者にしますか？プログラミングを学ぶのに苦労していますか？擬似コードを学習して、コードを理解します。しかし、擬似コードとは何ですか？それは本当に役立ちますか？
次を読む 関連トピック- プログラミング
- Java
- Python
- コーディングチュートリアル
ジェロームはMakeUseOfのスタッフライターです。彼はプログラミングとLinuxに関する記事をカバーしています。彼は暗号愛好家でもあり、常に暗号業界を監視しています。
xbox360プロファイルを削除する方法ジェローム・デビッドソンのその他の作品
ニュースレターを購読する
ニュースレターに参加して、技術的なヒント、レビュー、無料の電子書籍、限定セールを入手してください。
購読するにはここをクリックしてください