Бинарная сортировка вставок

// C программа для реализации бинарной сортировки вставок
#include <stdio.h>

  
// Функция на основе бинарного поиска для поиска позиции
// где элемент должен быть вставлен в [low..high]

int binarySearch(int a[], int item, int low, int high)

{

    if (high <= low)

        return (item > a[low])?  (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);

}

  
// Функция для сортировки массива a [] размера 'n'

void insertionSort(int a[], int n)

{

    int i, loc, j, k, selected;

    for (i = 1; i < n; ++i)

    {

        j = i - 1;

        selected = a[i];

        // найти место, где выбрано, может быть

        loc = binarySearch(a, selected, 0, j);

        // Переместить все элементы после расположения, чтобы создать пространство

        while (j >= loc)

        {

            a[j+1] = a[j];

            j--;

        }

        a[j+1] = selected;

    }

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int a[] = {37, 23, 0, 17, 12, 72, 31,

              46, 100, 88, 54};

    int n = sizeof(a)/sizeof(a[0]), i;

    insertionSort(a, n);

    printf("Sorted array: \n");

    for (i = 0; i < n; i++)

        printf("%d ",a[i]);

    return 0;

}

// Реализация Java-программы
// двоичная вставка

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<arr.length; i++)

            System.out.print(arr[i]+" ");

    }

    public void sort(int array[])

    {

        for (int i = 1; i < array.length; i++)

        {

            int x = array[i];

            // Найти место для вставки с помощью бинарного поиска

            int j = Math.abs(Arrays.binarySearch(array, 0, i, x) + 1);

            // Смещение массива в одну позицию вправо

            System.arraycopy(array, j, array, j+1, i-j);

            // Размещение элемента в правильном месте

            array[j] = x;

        }

    }

}

  
// Код предоставлен Mohit Gupta_OMG

# Реализация программы Python
# двоичного типа вставки

def binary_search(arr, val, start, end):

    # мы должны различать, должны ли мы вставить

    # до или после левой границы.

    # представьте [0] - последний шаг бинарного поиска

    # и нам нужно решить, куда вставить -1

    if start == end:

        if arr[start] > val:

            return start

        else:

            return start+1

    # это происходит, если мы выходим за левую границу

    # означает, что левая граница является наименьшей позицией для

    # найти число больше чем val

    if start > end:

        return start

    mid = (start+end)/2

    if arr[mid] < val:

        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):

    for i in xrange(1, len(arr)):

        val = arr[i]

        j = binary_search(arr, val, 0, i-1)

        arr = arr[:j] + [val] + arr[j:i] + arr[i+1:]

    return arr

print("Sorted array:")

print insertion_sort([37, 23, 0, 17, 12, 72, 31,

                        46, 100, 88, 54])

  
# Код предоставлен Mohit Gupta_OMG

// C # Реализация программы
// двоичная вставка

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 < arr.Length; i++)

            Console.Write(arr[i] + " ");

    }

    public static void sort(int []array)

    {

        for (int i = 1; i < array.Length; i++)

        {

            int x = array[i];

            // Найти место для вставки используя

            // бинарный поиск

            int j = Math.Abs(Array.BinarySearch(

                              array, 0, i, x) + 1);

            // Смещение массива в одну позицию вправо

            System.Array.Copy(array, j, array,

                                         j+1, i-j);

            // Размещение элемента в правильном

            // место расположения

            array[j] = x;

        }

    }

}

  
// Этот код предоставлен нитин митталь.

<?php
// PHP программа для реализации
// двоичная вставка

  
// Функция поиска на основе бинарного поиска
// позиция, где должен быть элемент
// вставляем в [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]) 

        return $mid + 1; 

    if($item > $a[$mid]) 

        return binarySearch($a, $item, 

                            $mid + 1, $high); 

    return binarySearch($a, $item, $low, 

                            $mid - 1); 

} 

  
// Функция для сортировки массива a размера 'n'

function insertionSort(&$a, $n) 

{ 

    $i; $loc; $j; $k; $selected; 

    for ($i = 1; $i < $n; ++$i) 

    { 

        $j = $i - 1; 

        $selected = $a[$i]; 

        // найти место где выбран

        // элемент должен быть вставлен

        $loc = binarySearch($a, $selected, 0, $j); 

        // Переместить все элементы после расположения

        // создать пространство

        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); 

insertionSort($a, $n); 

echo "Sorted array:\n"; 

for ($i = 0; $i < $n; $i++) 

    echo "$a[$i] "; 

  
// Этот код предоставлен
// Адеш Сингх
?>