logo

TechCodeview

挿入ソート – データ構造とアルゴリズムのチュートリアル

挿入ソート は、並べ替えられていないリストの各要素を、リストの並べ替えられた部分の正しい位置に繰り返し挿入することによって機能する単純な並べ替えアルゴリズムです。それは 安定したソート これは、値が等しい要素が並べ替えられた出力内で相対的な順序を維持することを意味します。

挿入ソート 手の中のトランプを分類するようなものです。カードを、ソートされたカードとソートされていないカードの 2 つのグループに分割します。次に、未分類のグループからカードを 1 枚選び、分類済みのグループの正しい場所に置きます。



挿入ソートアルゴリズム:

挿入ソート は、一度に 1 要素ずつソートされた配列を構築することで機能する単純なソート アルゴリズムです。それは、 所定の位置に つまり、元の配列を超える追加のメモリ領域は必要ありません。

アルゴリズム：

挿入ソートを実行するには、次の手順に従います。



文字列にはJavaが含まれています
  • 配列の最初の要素はソートされていると想定されるため、配列の 2 番目の要素から開始する必要があります。
  • 2 番目の要素と最初の要素を比較し、2 番目の要素が小さいかどうかを確認してから、それらを交換します。
  • 3 番目の要素に移動し、2 番目の要素、次に最初の要素と比較し、必要に応じて交換して、最初の 3 つの要素の間で正しい位置に配置します。
  • このプロセスを続行し、各要素をその前の要素と比較し、必要に応じて入れ替えて、並べ替えられた要素の正しい位置に配置します。
  • 配列全体がソートされるまで繰り返します。

挿入ソートアルゴリズムの仕組み:

要素を含む配列を考えてみましょう : {23、1、10、5、2}

最初のパス:



  • 現在の要素は 23
  • 配列の最初の要素はソートされているとみなされます。
  • までのソートされた部分 0位 インデックスは: [23]

2 番目のパス:

  • 比較する 1 と 23 (ソートされた部分を含む現在の要素)。
  • 以来 1 小さい方は挿入してください 1 前に 23 。
  • までのソートされた部分 1位 インデックスは: [1、23]

3回目のパス:

Javaの線形探索
  • 比較する 10 と 1 そして 23 (ソートされた部分を含む現在の要素)。
  • 以来 10 より大きい 1 そしてそれよりも小さい 23 、 入れる 10 間 1 そして 23 。
  • までのソートされた部分 2番目 インデックスは: [1、10、23]

4 番目のパス:

  • 比較する 5 と 1 、 10 、 そして 23 (ソートされた部分を含む現在の要素)。
  • 以来 5 より大きい 1 そしてそれよりも小さい 10 、 入れる 5 間 1 そして 10 。
  • までのソートされた部分 3位 インデックスは : [1、5、10、23]

5 番目のパス:

シェルスクリプトを実行可能にする
  • 比較する 2 と 1、5、10 、 そして 23 (ソートされた部分を含む現在の要素)。
  • 以来 2 より大きい 1 そしてそれよりも小さい 5 入れる 2 間 1 そして 5 。
  • までのソートされた部分 4位 インデックスは: [1、2、5、10、23]

最終的な配列:

  • ソートされた配列は次のとおりです。 [1、2、5、10、23]
おすすめの練習用挿入ソート 試してみよう！

挿入ソートの実装:

C++ 
// C++ program for insertion sort #include  using namespace std; // Function to sort an array using // insertion sort void insertionSort(int arr[], int n) {  int i, key, j;  for (i = 1; i < n; i++) {  key = arr[i];  j = i - 1;  // Move elements of arr[0..i-1],  // that are greater than key,   // to one position ahead of their  // current position  while (j>= 0 && arr[j]> key) { arr[j + 1] = arr[j];  j = j - 1;  arr[j + 1] = キー;  } } // サイズ n の配列を出力するユーティリティ関数 // void printArray(int arr[], int n) { int i;  for (i = 0; i< n; i++)  cout << arr[i] << ' ';  cout << endl; } // Driver code int main() {  int arr[] = { 12, 11, 13, 5, 6 };  int N = sizeof(arr) / sizeof(arr[0]);  insertionSort(arr, N);  printArray(arr, N);  return 0; } // This is code is contributed by rathbhupendra>
C 
// C program for insertion sort #include  #include  /* Function to sort an array using insertion sort*/ void insertionSort(int arr[], int n) {  int i, key, j;  for (i = 1; i < n; i++) {  key = arr[i];  j = i - 1;  /* Move elements of arr[0..i-1], that are  greater than key, to one position ahead  of their current position */  while (j>= 0 && arr[j]> key) { arr[j + 1] = arr[j];  j = j - 1;  arr[j + 1] = キー;  } } // サイズ n の配列を出力するユーティリティ関数 void printArray(int arr[], int n) { int i;  for (i = 0; i< n; i++)  printf('%d ', arr[i]);  printf('
'); } /* Driver program to test insertion sort */ int main() {  int arr[] = { 12, 11, 13, 5, 6 };  int n = sizeof(arr) / sizeof(arr[0]);  insertionSort(arr, n);  printArray(arr, n);  return 0; }>
ジャワ 
// Java program for implementation of Insertion Sort public class InsertionSort {  /*Function to sort array using insertion sort*/  void sort(int arr[])  {  int n = arr.length;  for (int i = 1; i < n; ++i) {  int key = arr[i];  int j = i - 1;  /* Move elements of arr[0..i-1], that are  greater than key, to one position ahead  of their current position */  while (j>= 0 && arr[j]> key) { arr[j + 1] = arr[j];  j = j - 1;  arr[j + 1] = キー;  } } /* サイズ n の配列を出力するユーティリティ関数*/ static void printArray(int arr[]) { int n = arr.length;  for (int i = 0; i< n; ++i)  System.out.print(arr[i] + ' ');  System.out.println();  }  // Driver method  public static void main(String args[])  {  int arr[] = { 12, 11, 13, 5, 6 };  InsertionSort ob = new InsertionSort();  ob.sort(arr);  printArray(arr);  } }; /* This code is contributed by Rajat Mishra. */>
パイソン 
# Python program for implementation of Insertion Sort # Function to do insertion sort def insertionSort(arr): # Traverse through 1 to len(arr) for i in range(1, len(arr)): key = arr[i] # Move elements of arr[0..i-1], that are # greater than key, to one position ahead # of their current position j = i-1 while j>= 0 とキー< arr[j] : arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key # Driver code to test above arr = [12, 11, 13, 5, 6] insertionSort(arr) for i in range(len(arr)): print ('% d' % arr[i]) # This code is contributed by Mohit Kumra>
C# 
// C# program for implementation of Insertion Sort using System; class InsertionSort {  // Function to sort array  // using insertion sort  void sort(int[] arr)  {  int n = arr.Length;  for (int i = 1; i < n; ++i) {  int key = arr[i];  int j = i - 1;  // Move elements of arr[0..i-1],  // that are greater than key,  // to one position ahead of  // their current position  while (j>= 0 && arr[j]> key) { arr[j + 1] = arr[j];  j = j - 1;  arr[j + 1] = キー;  } } // 印刷するユーティリティ関数 // サイズ n の配列 static void printArray(int[] arr) { int n = arr.Length;  for (int i = 0; i< n; ++i)  Console.Write(arr[i] + ' ');  Console.Write('
');  }  // Driver Code  public static void Main()  {  int[] arr = { 12, 11, 13, 5, 6 };  InsertionSort ob = new InsertionSort();  ob.sort(arr);  printArray(arr);  } } // This code is contributed by ChitraNayal.>
JavaScript 
>>
PHP 
 // PHP program for insertion sort // Function to sort an array // using insertion sort function insertionSort(&$arr, $n) { for ($i = 1; $i < $n; $i++) { $key = $arr[$i]; $j = $i-1; // Move elements of arr[0..i-1], // that are greater than key, to  // one position ahead of their  // current position while ($j>= 0 && $arr[$j]> $key) { $arr[$j + 1] = $arr[$j]; $j = $j - 1; $arr[$j + 1] = $key; } } // サイズ n の配列を出力するユーティリティ関数 function printArray(&$arr, $n) { for ($i = 0; $i< $n; $i++) echo $arr[$i].' '; echo '
'; } // Driver Code $arr = array(12, 11, 13, 5, 6); $n = sizeof($arr); insertionSort($arr, $n); printArray($arr, $n); // This code is contributed by ChitraNayal. ?>>>
出力 
5 6 11 12 13>

時間計算量: O(N^2)
補助スペース: ○(1)

挿入ソートの複雑さの分析 :

挿入ソートの計算量

  • 最良の場合： の上） , リストがすでに並べ替えられている場合、n はリスト内の要素の数です。
  • 平均的なケース: の上 2 ) , リストがランダムに並べられている場合
  • 最悪の場合： の上 2 ) , リストの順序が逆の場合

空間の複雑さ 挿入ソートの

  • 補助スペース: O(1)、挿入ソートが必要です ○(1) 追加のスペースが追加され、スペース効率の高い並べ替えアルゴリズムになります。

利点 挿入ソートの:

  • シンプルで実装が簡単です。
  • 安定したソートアルゴリズム。
  • 小さなリストやほとんどソートされたリストの場合は効率的です。
  • スペース効率が良い。

短所 挿入ソートの:

  • 大規模なリストの場合は非効率的です。
  • ほとんどの場合、他のソート アルゴリズム (マージ ソート、クイック ソートなど) ほど効率的ではありません。

アプリケーション 挿入ソートの:

挿入ソートは通常、次のような状況で使用されます。

  • リストは小さいか、ほとんどソートされています。
  • シンプルさと安定性が重要です。

挿入ソートに関するよくある質問

Q1.挿入ソートアルゴリズムの境界ケースとは何ですか?

要素が逆順にソートされている場合、挿入ソートではソートに最大の時間がかかります。また、要素がすでにソートされている場合は、最小限の時間 (次数 n) がかかります。

Q2.挿入ソートアルゴリズムのアルゴリズムパラダイムとは何ですか?

挿入ソート アルゴリズムは増分アプローチに従っています。

Q3.挿入ソートはインプレースソートアルゴリズムですか?

C# チュートリアル

はい、挿入ソートはインプレースソートアルゴリズムです。

Q4.インサーションソートは安定したアルゴリズムですか?

はい、挿入ソートは安定したソート アルゴリズムです。

Q5.挿入ソートアルゴリズムはいつ使用されますか?

Javaの文字列形式

挿入ソートは要素数が少ない場合に使用されます。また、入力配列がほぼソートされており、完全な大きな配列の中で数個の要素だけが間違って配置されている場合にも役立ちます。