logo

TechCodeview

Dvejetainis įterpimo rūšiavimas

Dvejetainis įterpimo rūšiavimas yra rūšiavimo algoritmas, panašus į įterpimo rūšiavimas , bet užuot naudoję linijinę paiešką, kad surastume vietą, kur turėtų būti įterptas elementas, mes naudojame dvejetainė paieška . Taigi mes sumažiname vieno elemento įterpimo lyginamąją vertę nuo O (N) iki O (log N).

Tai lankstus algoritmas, o tai reiškia, kad jis veikia greičiau, kai tie patys duoti nariai jau yra labai surūšiuoti, t. y. dabartinė funkcijos vieta yra arčiau jos tikrosios vietos surūšiuotame sąraše.



Tai stabilus filtravimo algoritmas – elementai su tomis pačiomis reikšmėmis ?atrodo ta pačia seka paskutine tvarka, kaip ir pirmame sąraše.

Dvejetainio įterpimo programos:

  • Dvejetainis įterpimo rūšiavimas geriausiai veikia, kai masyve yra mažesnis elementų skaičius.
  • Atliekant greitą rūšiavimą arba suliejimo rūšiavimą, kai pogrupio dydis tampa mažesnis (tarkime <= 25 elementai), geriausia naudoti dvejetainį įterpimo rūšiavimą.
  • Šis algoritmas taip pat veikia, kai raktų palyginimo kaina yra pakankamai didelė. Pavyzdžiui, jei norime filtruoti kelias eilutes, dviejų eilučių palyginimo našumas bus didesnis.

Kaip veikia dvejetainio įterpimo rūšiavimas?

  • Dvejetainio įterpimo rūšiavimo režimu tuos pačius narius padalijame į dvi dalis – filtruotą ir nefiltruotą. Pirmasis tų pačių narių elementas yra organizuotame pogrupyje, o visi kiti elementai yra neplanuoti.
  • Tada kartojame nuo antrojo elemento iki paskutinio. Kartodami i-ąjį, dabartinį objektą padarome savo raktu. Šis raktas yra funkcija, kurią turėtume įtraukti į žemiau esantį sąrašą.
  • Norėdami tai padaryti, pirmiausia naudojame dvejetainę paiešką žemiau esančioje surūšiuotoje pogrupyje, kad surastume elemento, didesnio už mūsų raktą, vietą. Pavadinkime šią poziciją poz. Tada dešinėn perkeliame visus elementus iš poz į 1 ir sukūrėme Array [pos] = raktą.
  • Galime pastebėti, kad kiekviename i-ajame daugyboje kairioji masyvo dalis iki (i – 1) jau yra surūšiuota.

Dvejetainio įterpimo rūšiavimo būdas:

  • Pakartokite masyvą nuo antrojo elemento iki paskutinio elemento.
  • Išsaugokite esamą elementą A[i] kintamajame rakte.
  • Naudodami dvejetainę paiešką suraskite elemento, kuris yra šiek tiek didesnis nei A[i], padėtį pogrupyje nuo A[0] iki A[i-1]. Tarkime, kad šis elementas yra indekso pozicijoje.
  • Perkelkite visus elementus iš indekso poz į i-1 į dešinę.
  • A[pos] = raktas.

Toliau pateikiamas pirmiau nurodyto metodo įgyvendinimas:

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[žemas]) ?> >(low + 1) : low;> >int> mid = (low + high) / 2;> >if> (item == a[mid])> >return> mid + 1;> >if> (item>a[mid])> >return> binarySearch(a, item,> >mid + 1, high);> >return> binarySearch(a, item, low,> >mid - 1);> }> // Function to sort an array a[] of size 'n'> 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] = pasirinkta; } } // Tvarkyklės kodas int main() { int a[] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = dydis(a) / dydis(a[0]), i; įterpimasRūšiuoti(a, n); cout<<'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 [žemas]) ?>> (low + 1) : low;> >int> mid = (low + high) / 2;> >if> (item == a[mid])> >return> mid + 1;> >if> (item>a[mid])> >return> binarySearch(a, item,> >mid + 1, high);> >return> binarySearch(a, item, low,> >mid - 1);> }> // Function to sort an array a[] of size 'n'> 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] = pasirinkta; } } // Tvarkyklės kodas int main() { int a[] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = dydis(a) / dydis(a[0]), i; įterpimasRūšiuoti(a, n); printf('Rūšiuotas masyvas: '); for (i = 0; i printf('%d ', a[i]); return 0; }> 

>

>

Java




// 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> 

>

greitas rūšiavimas 

>

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>pabaiga:> >return> start> >mid>=> (start>+>end)>/>/>2> >if> arr[mid] return binary_search(arr, val, mid+1, end) elif arr[mid]>val: return binary_search(arr, val, start, mid-1) else: return mid def insertion_sort(arr): i diapazone(1, len(arr)): val = arr[i] j = dvejetainis_search(arr, val, 0, i-1) arr = arr[:j] + [val] + arr[j:i] + arr[i+1:] return arr print('Surūšiuotas masyvas:') print(insertion_sort( [37, 23, 0, 31, 22, 17, 12, 72, 31, 46, 100, 88, 54])) # Kodas pateikė Mohit Gupta_OMG>> 

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
  
  // 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]) ?   ($žemas + 1) : $žemas;   $vidutinis = (int)(($žemas + $aukštas) / 2);   if($item == $a[$mid]) return $mid + 1;   if($item> $a[$mid]) return binarySearch($a, $item, $mid + 1, $ high);     return binarySearch($a, $item, $low, $mid - 1);  } // Funkcija rūšiuoti a dydžio masyvą 'n' function insertionSort(&$a, $n) { $i; $loc; $j; $k; $pasirinkta;   už ($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] = $pasirinkta;   } } // Tvarkyklės kodas $a = masyvas(37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54);    $n = dydis($a);  insertionSort($a, $n);  echo 'Rūšiuotas masyvas:
';  už ($i = 0; $i<$n; $i++)   echo '$a[$i] ';  // This code is contributed by  // Adesh Singh ?>>> 
  
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
  
  > // Javascript Program implementing> // binary insertion sort> function> binarySearch(a, item, low, high)> {> > >if> (high <= low)> >return> (item>a[žemas]) ?> >(low + 1) : low;> > >mid = Math.floor((low + high) / 2);> > >if>(item == a[mid])> >return> mid + 1;> > >if>(item>a[mid])> >return> binarySearch(a, item,> >mid + 1, high);> > >return> binarySearch(a, item, low,> >mid - 1);> }> function> sort(array)> {> >for> (let i = 1; i   {  let j = i - 1;  let x = array[i];    // Find location to insert  // using binary search  let loc = Math.abs(  binarySearch(array, x,  0, j));    // Shifting array to one  // location right    while (j>= loc) { masyvas[j + 1] = masyvas[j];  j--;  } // Elemento įdėjimas į teisingą vietą // masyvas[j+1] = x;  } } // Vairuotojo kodas tegul arr=[ 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54]; rūšiuoti(arr); for (tegul i = 0; i document.write(arr[i] + ' '); // Šį kodą sukūrė unknown2108 // C programa, skirta įgyvendinti // dvejetainį įterpimą rūšiuoti #include // Dvejetainė paieška pagrįsta funkcija // rasti vietą // kur reikia įterpti elementą // int a[low..high] int binarySearch(int a[], int item, int low, int high) { if (aukštas)<= low)  return (item>a [žemas]) ?  (žemas + 1) : žemas;  int mid = (žemas + aukštas) / 2;  if (item == a[mid]) return mid + 1;  if (item> a[mid]) return binarySearch(a, item, mid + 1, high);  return binarySearch(a, elementas, žemas, vidurys - 1); } // Funkcija rūšiuoti a[] dydžio masyvą 'n' void insertionSort(int a[], int n) { int i, loc, j, k, selected;  for (i = 1; i { j = i - 1; pasirinktas = a[i]; // rasti vietą, kur reikia įterpti pasirinktą vietą loc = dvejetainė paieška(a, pasirinkta, 0, j); // Perkelti visus elementus po vietos sukurti tarpą while (j>= loc) { a[j + 1] = a[j] } a[j + 1] = pasirinktas } } // Vairuotojo kodas int main() { int a; [] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = dydis(a) / dydis(a[0]), i; ); printf('Rūšiuotas masyvas: 
'); for (i = 0; i printf('%d ', a[i]); r// C programa, skirta // dvejetainiam įterpimui rūšiuoti #include // Dvejetainė paieška pagrįsta funkcija // norint rasti vietą // kur elementas turi būti įterptas // int binarySearch(int a[], int item, int low, int high) { jei (aukštas<= low)  return (item>a [žemas]) ?  (žemas + 1) : žemas;  int mid = (žemas + aukštas) / 2;  if (item == a[mid]) return mid + 1;  if (item> a[mid]) return binarySearch(a, item, mid + 1, high);  return binarySearch(a, elementas, žemas, vidurys - 1); } // Funkcija rūšiuoti a[] dydžio masyvą 'n' void insertionSort(int a[], int n) { int i, loc, j, k, selected;  for (i = 1; i { j = i - 1; pasirinktas = a[i]; // rasti vietą, kurioje pasirinkta turėtų būti įterpta loc = binarySearch(a, selected, 0, j); // Perkelti visus elementus po vietos sukurti tarpą while (j>= loc) { a[j + 1] = a[j] } a[j + 1] = pasirinktas } } // Vairuotojo kodas int main() { int a; [] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = dydis(a) / dydis(a[0]), i; ); printf('Rūšiuotas masyvas: 
'); for (i = 0; i printf('%d ', a[i]); // C programa, skirta // dvejetainio įterpimo rūšiavimo # include // Dvejetaine paieška pagrįstą funkciją // norėdami rasti vietą // kur elementas turi būti įterptas // int binarySearch(int a[], int item, int low, int high) { if (aukštas<= low)  return (item>a [žemas]) ?  (žemas + 1) : žemas;  int mid = (žemas + aukštas) / 2;  if (item == a[mid]) return mid + 1;  if (item> a[mid]) return binarySearch(a, item, mid + 1, high);  return binarySearch(a, elementas, žemas, vidurys - 1); } // Funkcija rūšiuoti a[] dydžio masyvą 'n' void insertionSort(int a[], int n) { int i, loc, j, k, selected;  for (i = 1; i { j = i - 1; pasirinktas = a[i]; // rasti vietą, kurioje pasirinkta turėtų būti įterpta loc = binarySearch(a, selected, 0, j); // Perkelti visus elementus po vietos sukurti tarpą while (j>= loc) { a[j + 1] = a[j] } a[j + 1] = pasirinktas } } // Vairuotojo kodas int main() { int a; [] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = dydis(a) / dydis(a[0]), i; ); printf('Rūšiuotas masyvas: 
'); for (i = 0; i printf('%d ', a[i]); // C programa, skirta // dvejetainio įterpimo rūšiavimo # include // Dvejetaine paieška pagrįstą funkciją // norėdami rasti vietą // kur elementas turi būti įterptas // int binarySearch(int a[], int item, int low, int high) { if (aukštas<= low)  return (item>a [žemas]) ?  (žemas + 1) : žemas;  int mid = (žemas + aukštas) / 2;  if (item == a[mid]) return mid + 1;  if (item> a[mid]) return binarySearch(a, item, mid + 1, high);  return binarySearch(a, elementas, žemas, vidurys - 1); } // Funkcija rūšiuoti a[] dydžio masyvą 'n' void insertionSort(int a[], int n) { int i, loc, j, k, selected;  for (i = 1; i { j = i - 1; pasirinktas = a[i]; // rasti vietą, kur reikia įterpti pasirinktą vietą loc = dvejetainė paieška(a, pasirinkta, 0, j); // Perkelti visus elementus po vietos sukurti tarpą while (j>= loc) { a[j + 1] = a[j] } a[j + 1] = pasirinktas } } // Vairuotojo kodas int main() { int a; [] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = dydis(a) / dydis(a[0]), i; ); printf('Rūšiuotas masyvas: 
'); for (i = 0; i printf('%d ', a[i]); // C programa, skirta // dvejetainio įterpimo rūšiavimo # include // Dvejetaine paieška pagrįstą funkciją // norėdami rasti vietą // kur elementas turi būti įterptas // int binarySearch(int a[], int item, int low, int high) { if (aukštas<= low)  return (item>a [žemas]) ?  (žemas + 1) : žemas;  int mid = (žemas + aukštas) / 2;  if (item == a[mid]) return mid + 1;  if (item> a[mid]) return binarySearch(a, item, mid + 1, high);  return binarySearch(a, elementas, žemas, vidurys - 1); } // Funkcija rūšiuoti a[] dydžio masyvą 'n' void insertionSort(int a[], int n) { int i, loc, j, k, selected;  for (i = 1; i { j = i - 1; pasirinktas = a[i]; // rasti vietą, kurioje pasirinkta turėtų būti įterpta loc = binarySearch(a, selected, 0, j); // Perkelti visus elementus po vietos sukurti tarpą while (j>= loc) { a[j + 1] = a[j] } a[j + 1] = pasirinktas } } // Vairuotojo kodas int main() { int a; [] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = dydis(a) / dydis(a[0]), i; ); printf('Rūšiuotas masyvas: 
'); for (i = 0; i printf('%d ', a[i]);// C programa, skirta // dvejetainio įterpimo rūšiavimo # include // Dvejetaine paieška pagrįstą funkciją // norėdami rasti vietą // kur elementas turi būti įterptas // int binarySearch(int a[], int item, int low, int high) { if (aukštas<= low)  return (item>a [žemas]) ?  (žemas + 1) : žemas;  int mid = (žemas + aukštas) / 2;  if (item == a[mid]) return mid + 1;  if (item> a[mid]) return binarySearch(a, item, mid + 1, high);  return binarySearch(a, elementas, žemas, vidurys - 1); } // Funkcija rūšiuoti a[] dydžio masyvą 'n' void insertionSort(int a[], int n) { int i, loc, j, k, selected;  for (i = 1; i { j = i - 1; pasirinktas = a[i]; // rasti vietą, kurioje pasirinkta turėtų būti įterpta loc = binarySearch(a, selected, 0, j); // Perkelti visus elementus po vietos sukurti tarpą while (j>= loc) { a[j + 1] = a[j] } a[j + 1] = pasirinktas } } // Vairuotojo kodas int main() { int a; [] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 }; int n = dydis(a) / dydis(a[0]), i; ); printf('Rūšiuotas masyvas: 
'); for (i = 0; i printf('%d ', a[i])> 
  
 
    
 
>
 
    
 
>
 
  Išvestis  
 
Sorted array: 0 12 17 23 31 37 46 54 72 88 100>
 
  Laiko sudėtingumas: Viso algoritmo veikimo laikas blogiausiu atveju yra O (n2), nes kiekvienam įterpimui reikalingos apsikeitimo sandorių serijos.
 
  Kitas požiūris: Toliau pateikiamas kartotinis aukščiau pateikto rekursinio kodo įgyvendinimas
 
C++
    
kas yra android velykinis kiaušinis

 
     
  
 
    
 
     
     
    
 
 
  
  #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[mid])> >low = mid + 1;> >else> >high = mid - 1;> >}> >return> low;> }> // Function to sort an array a[] of size 'n'> 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] = pasirinkta;  } } // Tvarkyklės kodas int main() { int a[] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 };  int n = dydis(a) / dydis(a[0]), i;  įterpimasRūšiuoti(a, n);  cout<<'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[mid])> >low = mid + 1;> >else> >high = mid - 1;> >}> >return> low;> }> // Function to sort an array a[] of size 'n'> 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] = pasirinkta;  } } // Tvarkyklės kodas int main() { int a[] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 };  int n = dydis(a) / dydis(a[0]), i;  įterpimasRūšiuoti(a, n);  printf('Rūšiuotas masyvas: 
');  for (i = 0; i printf('%d ', a[i]); grąžinti 0; } // pateikė tmeid> 
  
 
    
 
>
 
    
 
>
 
 
Java
    
 
     
  
 
    
 
     
     
    
 
 
  
  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[mid])> >low = mid +>1>;> >else> >high = mid ->1>;> >}> >return> low;> }> // Function to sort an array a[] of size 'n'> 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] = pasirinkta;  } } // Tvarkyklės kodas viešas statinis void main (String[] args) { int a[] = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 };  int n = a.ilgis, i;  įterpimasRūšiuoti(a, n);  System.out.println('Rūšiuotas masyvas:');  for (i = 0; i System.out.print(a[i] +' '); } } // Šį kodą pateikė shivanisinghss2110.>> 
  
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
 
 
  
  # 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[mid]):> >low>=> mid>+> 1> >else>:> >high>=> mid>-> 1> >return> low> > # Function to sort an array a[] of size 'n'> 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[mid])> >low = mid + 1;> >else> >high = mid - 1;> >}> >return> low;> }> // Function to sort an array a[] of size 'n'> 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] = pasirinkta;  } } // Tvarkyklės kodas public static void Pagrindinis (String[] args) { int []a = { 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 };  int n = a.Ilgis, i;  įterpimasRūšiuoti(a, n);  Console.WriteLine('Rūšiuotas masyvas:');  for (i = 0; i Console.Write(a[i] +' '); } } // Šį kodą pateikė 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[mid])> >low = mid + 1;> >else> >high = mid - 1;> >}> >return> low;> }> // Function to sort an array a[] of size 'n'> 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] = pasirinkta;  } } // Tvarkyklės kodas var a = [ 37, 23, 0, 17, 12, 72, 31, 46, 100, 88, 54 ];  var n = a.ilgis, i;  įterpimasRūšiuoti(a, n);  document.write('Rūšiuotas masyvas:' + ' ');  for (i = 0; i document.write(a[i] +' '); // Šį kodą pateikė shivanisinghss2110>> 
  
 
python // operatorius

    
 
> 
    
 Sorted array: 0 12 17 23 31 37 46 54 72 88 100>