この記事では、挿入ソート アルゴリズムについて説明します。挿入ソートの作業手順も簡単です。この記事は、挿入ソートが試験問題として出題される可能性がある学生にとって、非常に役立ち、興味深いものとなるでしょう。したがって、そのテーマについて話し合うことが重要です。
挿入ソートは、手持ちのトランプのソートと同様に機能します。カード ゲームでは最初のカードがすでにソートされていると仮定し、次に未ソートのカードを選択します。選択した未分類のカードが最初のカードより大きい場合は、右側に配置されます。それ以外の場合は、左側に配置されます。同様に、分類されていないカードはすべて取り出され、正しい場所に置かれます。
同じアプローチが挿入ソートにも適用されます。挿入ソートの背後にある考え方は、まず 1 つの要素を取得し、それをソートされた配列内で反復処理することです。使い方は簡単ですが、平均的な場合でも最悪の場合でも挿入ソートの時間が複雑になるため、大規模なデータセットには適していません。 の上2) ここで、n は項目の数です。挿入ソートは、ヒープ ソート、クイック ソート、マージ ソートなどの他のソート アルゴリズムよりも効率が低くなります。
挿入ソートには次のようなさまざまな利点があります。
- シンプルな実装
- 小規模なデータセットの場合は効率的
- 適応的、つまり、すでに実質的にソートされているデータセットに適しています。
次に、挿入ソートのアルゴリズムを見てみましょう。
アルゴリズム
挿入ソートを実現する簡単な手順は次のとおりです。
ステップ1 - この要素が最初の要素である場合、それはすでにソートされていると想定されます。 1を返します。
配列リストのソートJava
ステップ2 - 次の要素を選択し、それを別個に保存します。 鍵。
ステップ3 - さて、比較してみましょう 鍵 ソートされた配列内のすべての要素を使用します。
ステップ4 - ソートされた配列内の要素が現在の要素より小さい場合は、次の要素に移動します。それ以外の場合は、配列内の大きい要素を右にシフトします。
ステップ5 - 値を挿入します。
ステップ6 - 配列がソートされるまで繰り返します。
挿入ソートアルゴリズムの仕組み
ここで、挿入ソート アルゴリズムの仕組みを見てみましょう。
挿入ソート アルゴリズムの動作を理解するために、ソートされていない配列を取り上げてみましょう。例を使用すると、挿入ソートを理解しやすくなります。
配列の要素を次のようにします -
最初に、最初の 2 つの要素が挿入ソートで比較されます。
ここで、31 は 12 より大きいです。つまり、両方の要素がすでに昇順になっています。したがって、今のところ、12 はソートされた部分配列に格納されます。
次に、次の 2 つの要素に移動して比較します。
ここで、25 は 31 より小さいため、31 は正しい位置にありません。ここで、31 を 25 と交換します。交換に加えて、挿入ソートでは、ソートされた配列内のすべての要素もチェックします。
現時点では、ソートされた配列には要素が 1 つだけ、つまり 12 しかありません。したがって、25 は 12 より大きくなります。したがって、ソートされた配列は交換後もソートされたままになります。
ここで、ソートされた配列の 2 つの要素は 12 と 25 です。次の要素 31 と 8 に進みます。
31 と 8 は両方ともソートされていません。それで、交換してください。
交換後、要素 25 と 8 はソートされていません。
それで、交換してください。
現在、要素 12 と 8 はソートされていません。
ということで、こちらも交換。
現在、ソートされた配列には 8、12、25 の 3 つの項目があります。次の項目 31 と 32 に移動します。
したがって、それらはすでに並べ替えられています。現在、ソートされた配列には 8、12、25、31 が含まれています。
次の要素 32 と 17 に移動します。
17 は 32 より小さいので、それらを交換します。
交換すると、31 と 17 がソートされなくなります。ということで、こちらも交換。
ここで、入れ替えると 25 と 17 がソートされなくなります。そのため、再度交換作業を行ってください。
これで、配列が完全にソートされました。
挿入ソートの複雑さ
ここで、最良のケース、平均的なケース、最悪のケースにおける挿入ソートの時間計算量を見てみましょう。挿入ソートの空間の複雑さも見ていきます。
1. 時間計算量
| 場合 | 時間計算量 |
|---|---|
| 最良の場合 | の上） |
| 平均的なケース | の上2) |
| 最悪の場合 | の上2) |
2. 空間の複雑さ
| 空間の複雑さ | ○(1) |
| 安定した | はい |
- 挿入ソートの空間計算量は O(1) です。挿入ソートでは、入れ替えのために余分な変数が必要になるためです。
挿入ソートの実装
ここで、さまざまなプログラミング言語での挿入ソートのプログラムを見てみましょう。
プログラム： C言語で挿入ソートを実装するプログラムを書きます。
#include void insert(int a[], int n) /* function to sort an aay with insertion sort */ { int i, j, temp; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 && temp <= 17 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } void printarr(int a[], int n) function print array i; for (i="0;" i < n; i++) printf('%d ', a[i]); main() a[]="{" 12, 31, 25, 8, 32, }; n="sizeof(a)" sizeof(a[0]); printf('before sorting are -
'); printarr(a, n); insert(a, printf('
after return 0; pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-18.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in python.</p> <pre> def insertionSort(a): # Function to implement insertion sort for i in range(1, len(a)): temp = a[i] # Move the elements greater than temp to one position #ahead from their current position j = i-1 while j >= 0 and temp <a[j] : a[j + 1]="a[j]" j="j-1" def printarr(a): # function to print the array for i in range(len(a)): (a[i], end=" " ) a="[70," 15, 2, 51, 60] print('before sorting elements are - ') printarr(a) insertionsort(a) print('
after < pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-19.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in C++ language.</p> <pre> #include using namespace std; void insert(int a[], int n) /* function to sort an aay with insertion sort */ { int i, j, temp; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 && temp <= 2 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } void printarr(int a[], int n) function print array i; for (i="0;" i < n; i++) cout << a[i] <<' '; main() a[]="{" 89, 45, 35, 8, 12, }; n="sizeof(a)" sizeof(a[0]); cout<<'before sorting are - '<<endl; printarr(a, n); insert(a, cout<<'
after return 0; pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-20.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in C# language.</p> <pre> using System; class Insertion { static void insert(int[] a) /* function to sort an aay with insertion sort */ { int i, j, temp; int n = a.Length; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 && temp <= 12 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } static void printarr(int[] a) function print array int i; n="a.Length;" for (i="0;" i < n; i++) console.write(a[i] + ' '); main() int[] a="{" 98, 54, 53, 18, 21, }; console.write('before sorting are -
'); printarr(a); insert(a); console.write('
after pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-21.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in Java.</p> <pre> public class Insert { void insert(int a[]) /* function to sort an aay with insertion sort */ { int i, j, temp; int n = a.length; for (i = 1; i <n; i++) { temp="a[i];" j="i" - 1; while(j>=0 && temp <= 22 a[j]) * move the elements greater than temp to one position ahead from their current position* { a[j+1]="a[j];" j="j-1;" } void printarr(int a[]) function print array int i; n="a.length;" for (i="0;" i < n; i++) system.out.print(a[i] + ' '); public static main(string[] args) a[]="{" 92, 50, 5, 20, 11, }; insert i1="new" insert(); system.out.println('
before sorting are - i1.printarr(a); i1.insert(a); system.out.println('
after system.out.println(); pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-22.webp" alt="Insertion Sort Algorithm"> <p> <strong>Program:</strong> Write a program to implement insertion sort in PHP.</p> <pre> <?php $a = array( 92, 50, 5, 20, 11, 22 ); function printArray($a) { for($i = 0; $i < 6; $i++) { print_r($a[$i]); echo ' '; } } echo 'Before sorting array elements are - <br>'; printArray($a); for ($i = 1; $i = 0 && $temp <= $a[$j]) * move the elements greater than temp to one position ahead from their current position* { $a[$j+1]="$a[$j];" $j="$j-1;" } echo ' <br> After sorting array elements are - <br>'; printArray($a); ?> </=></pre> <p> <strong>Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/insertion-sort-algorithm-23.webp" alt="Insertion Sort Algorithm"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <p>This article was not only limited to the algorithm. We have also discussed the algorithm's complexity, working, and implementation in different programming languages.</p> <hr></=></n;></pre></=></n;></pre></=></n;></pre></a[j]></pre></=></n;> 出力：
それでは、この記事については以上です。この記事があなたにとって有益で有益であることを願っています。
この記事はアルゴリズムだけに限定されたものではありません。また、アルゴリズムの複雑さ、動作、さまざまなプログラミング言語での実装についても説明しました。