バイナリ挿入ソート
バイナリ挿入ソートは、 挿入ソート ただし、要素を挿入する場所を見つけるために線形検索を使用する代わりに、 二分探索 。したがって、単一要素の挿入の比較値を O (N) から O (log N) に減らします。
これは柔軟なアルゴリズムであり、同じ特定のメンバーが既に高度にソートされている場合、つまり、フィーチャの現在の位置がソートされたリスト内の実際の位置に近い場合、より高速に動作することを意味します。
これは安定したフィルタリング アルゴリズムです。同じ値を持つ要素は、最初のリストにあったときと同じ順序で同じシーケンスに表示されます。
バイナリ挿入ソートのアプリケーション:
- バイナリ挿入ソートは、配列の項目数が少ない場合に最適に機能します。
- クイック ソートまたはマージ ソートを実行する場合、部分配列のサイズが小さくなる場合 (要素 25 以下など)、バイナリ挿入ソートを使用するのが最適です。
- このアルゴリズムは、キー間の比較コストが十分に高い場合にも機能します。たとえば、複数の文字列をフィルタリングする場合、2 つの文字列の比較パフォーマンスが高くなります。
バイナリ挿入ソートはどのように機能しますか?
- バイナリ挿入ソート モードでは、同じメンバーを 2 つのサブ配列 (フィルター付きとフィルターなし) に分割します。同じメンバーの最初の要素は組織化されたサブ配列内にあり、他のすべての要素は計画外です。
- 次に、2 番目の要素から最後の要素まで繰り返します。 i 番目の繰り返しでは、現在のオブジェクトをキーにします。このキーは、以下の既存のリストに追加する必要がある機能です。
- これを行うには、まず以下のソートされた部分配列に対して二分検索を使用して、キーより大きい要素の位置を見つけます。この位置を pos と呼びましょう。次に、すべての要素を pos から 1 に右シフトし、Array[pos] = key を作成しました。
- i 番目の乗算ごとに、(i – 1) までの配列の左側の部分がすでにソートされていることがわかります。
バイナリ挿入ソートを実装するアプローチ:
- 配列を 2 番目の要素から最後の要素まで繰り返します。
- 現在の要素 A[i] を変数キーに保存します。
- 二分探索を使用して、A[0] から A[i-1] までの部分配列内で A[i] よりも大きい要素の位置を見つけます。この要素がインデックス pos にあるとします。
- すべての要素をインデックス pos から i-1 まで右にシフトします。
- A[pos] = キー。
上記のアプローチの実装を以下に示します。
C++
// C program for implementation of> // binary insertion sort> #include> using> namespace> std;> // A binary search based function> // to find the position> // where item should be inserted> // in a[low..high]> int> binarySearch(> int> a[],> int> item,> > int> low,> int> high)> {> > if> (high <= low)> > return> (item>a[低]) ?>> > (low + 1) : low;> > int> mid = (low + high) / 2;> > if> (item == a[mid])> > return> mid + 1;> > if> (item>a[中])>> void> insertionSort(> int> a[],> int> n)> {> > int> i, loc, j, k, selected;> > for> (i = 1; i { j = i - 1; selected = a[i]; // find location where selected should be inserted loc = binarySearch(a, selected, 0, j); // Move all elements after location to create space while (j>= loc) { a[j + 1] = a[j]; j--; a[j + 1] = 選択済み; } } // ドライバーコード int main() { int a[] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = sizeof(a) / sizeof(a[0]), i; 挿入ソート(a, n); コート < <'Sorted array:
'; for (i = 0; i cout < <' ' < < a[i]; return 0; } // this code is contribution by shivanisinghss2110> |
C
// C program for implementation of> // binary insertion sort> #include> // A binary search based function> // to find the position> // where item should be inserted> // in a[low..high]> int> binarySearch(> int> a[],> int> item,> > int> low,> int> high)> {> > if> (high <= low)> > return> (item>a[低])?>> > (low + 1) : low;> > int> mid = (low + high) / 2;> > if> (item == a[mid])> > return> mid + 1;> > if> (item>a[中])>> void> insertionSort(> int> a[],> int> n)> {> > int> i, loc, j, k, selected;> > for> (i = 1; i { j = i - 1; selected = a[i]; // find location where selected should be inserted loc = binarySearch(a, selected, 0, j); // Move all elements after location to create space while (j>= loc) { a[j + 1] = a[j]; j--; a[j + 1] = 選択済み; } } // ドライバーコード int main() { int a[] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = sizeof(a) / sizeof(a[0]), i; 挿入ソート(a, n); printf('ソートされた配列:
'); for (i = 0; i printf('%d ', a[i]); return 0; }> |
ジャワ
// Java Program implementing> // binary insertion sort> import> java.util.Arrays;> class> GFG> {> > > public> static> void> main(String[] args)> > {> > final> int> [] arr = {> 37> ,> 23> ,> 0> ,> 17> ,> 12> ,> 72> ,> > 31> ,> 46> ,> 100> ,> 88> ,> 54> };> > new> GFG().sort(arr);> > for> (> int> i => 0> ; i System.out.print(arr[i] + ' '); } // Driver Code public void sort(int array[]) { for (int i = 1; i { int x = array[i]; // Find location to insert // using binary search int j = Math.abs( Arrays.binarySearch(array, 0, i, x) + 1); // Shifting array to one // location right System.arraycopy(array, j, array, j + 1, i - j); // Placing element at its // correct location array[j] = x; } } } // Code contributed by Mohit Gupta_OMG> |
Python3
# Python Program implementation> # of binary insertion sort> def> binary_search(arr, val, start, end):> > > # we need to distinguish whether we> > # should insert before or after the> > # left boundary. imagine [0] is the last> > # step of the binary search and we need> > # to decide where to insert -1> > if> start> => => end:> > if> arr[start]>val:> > return> start> > else> :> > return> start> +> 1> > # this occurs if we are moving> > # beyond left's boundary meaning> > # the left boundary is the least> > # position to find a number greater than val> > if> start>終了:> > return> start> > mid> => (start> +> end)> /> /> 2> > if> arr[mid] return binary_search(arr, val, mid+1, end) elif arr[mid]>val: binary_search(arr, val, start, mid-1) を返します。 else: Mid def を返します。 insert_sort(arr): range(1, len(arr)) の i の場合: val = arr[i] j = binary_search(arr, val, 0, i-1) arr = arr[:j] + [val] + arr[j:i] + arr[i+1:] return arr print('ソートされた配列:') print(insertion_sort( [37, 23, 0, 31, 22, 17, 12, 72, 31, 46, 100, 88, 54])) # Mohit Gupta_OMG によって提供されたコード>> |
C#
// C# Program implementing> // binary insertion sort> using> System;> class> GFG {> > public> static> void> Main()> > {> > int> [] arr = { 37, 23, 0, 17, 12, 72,> > 31, 46, 100, 88, 54 };> > sort(arr);> > for> (> int> i = 0; i Console.Write(arr[i] + ' '); } // Driver Code public static void sort(int[] array) { for (int i = 1; i { int x = array[i]; // Find location to insert using // binary search int j = Math.Abs( Array.BinarySearch(array, 0, i, x) + 1); // Shifting array to one location right System.Array.Copy(array, j, array, j + 1, i - j); // Placing element at its correct // location array[j] = x; } } } // This code is contributed by nitin mittal.> |
PHP
// PHP program for implementation of // binary insertion sort // A binary search based function to find // the position where item should be // inserted in a[low..high] function binarySearch($a, $item, $low, $high) { if ($high <= $low) return ($item>$a[$low])? ($low + 1) : $low; $mid = (int)(($low + $high) / 2); if($item == $a[$mid]) $mid + 1 を返します。 if($item> $a[$mid]) return binarySearch($a, $item, $mid + 1, $high); return binarySearch($a, $item, $low, $mid - 1); } // サイズ 'n' の配列 a をソートする関数 function insertSort(&$a, $n) { $i; $loc; $j; $k; $選択済み; for ($i = 1; $i <$n; ++$i) { $j = $i - 1; $selected = $a[$i]; // find location where selected // item should be inserted $loc = binarySearch($a, $selected, 0, $j); // Move all elements after location // to create space while ($j>= $loc) { $a[$j + 1] = $a[$j]; $j--; $a[$j + 1] = $selected; } } // ドライバーコード $a = array(37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54); $n = sizeof($a); 挿入ソート($a, $n); echo 'ソートされた配列:
'; for ($i = 0; $i <$n; $i++) echo '$a[$i] '; // This code is contributed by // Adesh Singh ?>>> |
JavaScript
> // Javascript Program implementing> // binary insertion sort> function> binarySearch(a, item, low, high)> {> > > if> (high <= low)> > return> (item>a[低]) ?>> > (low + 1) : low;> > > mid = Math.floor((low + high) / 2);> > > if> (item == a[mid])> > return> mid + 1;> > > if> (item>a[中])>> |
出力
Sorted array: 0 12 17 23 31 37 46 54 72 88 100
時間計算量: アルゴリズム全体の実行時間は依然として最悪の場合でも O(n 2 ）挿入ごとに一連のスワップが必要になるためです。
別のアプローチ: 以下は、上記の再帰コードの反復実装です。
C++
#include> using> namespace> std;> // iterative implementation> int> binarySearch(> int> a[],> int> item,> int> low,> int> high)> {> > while> (low <= high) {> > int> mid = low + (high - low) / 2;> > if> (item == a[mid])> > return> mid + 1;> > else> if> (item>a[中])>> void> insertionSort(> int> a[],> int> n)> {> > int> i, loc, j, k, selected;> > for> (i = 1; i j = i - 1; selected = a[i]; // find location where selected should be inserted loc = binarySearch(a, selected, 0, j); // Move all elements after location to create space while (j>= loc) { a[j + 1] = a[j]; j--; a[j + 1] = 選択済み; } } // ドライバーコード int main() { int a[] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = sizeof(a) / sizeof(a[0]), i; 挿入ソート(a, n); コート < <'Sorted array:
'; for (i = 0; i cout < <' ' < < a[i]; return 0; } // This code is contributed by shivanisinghss2110.> |
C
#include> // iterative implementation> int> binarySearch(> int> a[],> int> item,> int> low,> int> high)> {> > while> (low <= high) {> > int> mid = low + (high - low) / 2;> > if> (item == a[mid])> > return> mid + 1;> > else> if> (item>a[中])>> void> insertionSort(> int> a[],> int> n)> {> > int> i, loc, j, k, selected;> > for> (i = 1; i j = i - 1; selected = a[i]; // find location where selected should be inserted loc = binarySearch(a, selected, 0, j); // Move all elements after location to create space while (j>= loc) { a[j + 1] = a[j]; j--; a[j + 1] = 選択済み; } } // ドライバーコード int main() { int a[] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = sizeof(a) / sizeof(a[0]), i; 挿入ソート(a, n); printf('ソートされた配列:
'); for (i = 0; i printf('%d ', a[i]); return 0; } // tmeid による提供>>' |
>
import>java.io.*;>class>GFG {>// iterative implementation>static>int>binarySearch(>int>a[],>int>item,>int>low,>int>high)>{>>while>(low <= high) {>>int>mid = low + (high - low) />2>;>>if>(item == a[mid])>>return>mid +>1>;>>else>if>(item>a[中])>>static>void>insertionSort(>int>a[],>int>n)>{>>int>i, loc, j, k, selected;>>for>(i =>1>; i j = i - 1; selected = a[i]; // find location where selected should be inserted loc = binarySearch(a, selected, 0, j); // Move all elements after location to create space while (j>= loc) { a[j + 1] = a[j]; j--; a[j + 1] = 選択済み; } } // ドライバーコード public static void main (String[] args) { int a[] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = a.length, i; 挿入ソート(a, n); System.out.println('ソートされた配列:'); for (i = 0; i System.out.print(a[i] +' '); } } // このコードは shivanisinghss2110 によって提供されました。>>
Python3
# iterative implementation>def>binarySearch(a, item, low, high):>>while>(low <>=>high):>>mid>=>low>+>(high>->low)>/>/>2>>if>(item>=>=>a[mid]):>>return>mid>+>1>>elif>(item>a[中]):>>def>insertionSort(a, n):>>for>i>in>range>(n):>>j>=>i>->1>>selected>=>a[i]>>># find location where selected should be inserted>>loc>=>binarySearch(a, selected,>0>, j)>>># Move all elements after location to create space>>while>(j>>>=>loc):>>a[j>+>1>]>=>a[j]>>j>->=>1>>a[j>+>1>]>=>selected># Driver Code>a>=>[>37>,>23>,>0>,>17>,>12>,>72>,>31>,>46>,>100>,>88>,>54>]>n>=>len>(a)>insertionSort(a, n)>print>(>'Sorted array: '>)>for>i>in>range>(n):>>print>(a[i], end>=>' '>)># This code is contributed by shivanisinghss2110>
C#
using>System;>class>GFG {>// iterative implementation>static>int>binarySearch(>int>[]a,>int>item,>int>low,>int>high)>{>>while>(low <= high) {>>int>mid = low + (high - low) / 2;>>if>(item == a[mid])>>return>mid + 1;>>else>if>(item>a[中])>>static>void>insertionSort(>int>[]a,>int>n)>{>>int>i, loc, j, selected;>>for>(i = 1; i j = i - 1; selected = a[i]; // find location where selected should be inserted loc = binarySearch(a, selected, 0, j); // Move all elements after location to create space while (j>= loc) { a[j + 1] = a[j]; j--; a[j + 1] = 選択済み; } } // ドライバーコード public static void Main (String[] args) { int []a = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = a.長さ, i; 挿入ソート(a, n); Console.WriteLine('ソートされた配列:'); for (i = 0; i Console.Write(a[i] +' '); } } // このコードは shivanisinghss2110 によって提供されています>>'
>
>// iterative implementation>function>binarySearch( a, item, low, high)>{>>while>(low <= high) {>>var>mid = low + (high - low) / 2;>>if>(item == a[mid])>>return>mid + 1;>>else>if>(item>a[中])>>function>insertionSort(a, n)>{>>var>i, loc, j, k, selected;>>for>(i = 1; i j = i - 1; selected = a[i]; // find location where selected should be inserted loc = binarySearch(a, selected, 0, j); // Move all elements after location to create space while (j>= loc) { a[j + 1] = a[j]; j--; a[j + 1] = 選択済み; } } // ドライバーコード var a = [ 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 ]; var n = a.length, i; 挿入ソート(a, n); document.write('ソートされた配列:' + ' '); for (i = 0; i document.write(a[i] +' '); // このコードは shivanisinghss2110 によって提供されました>>'
>
Next.js 次/リンク
