Рубрики

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

Мы можем использовать бинарный поиск, чтобы уменьшить количество сравнений в обычной сортировке вставкой . Бинарная сортировка вставок использует бинарный поиск, чтобы найти правильное место для вставки выбранного элемента на каждой итерации.
При обычной сортировке вставкой в худшем случае требуется O (n) сравнений (на n-й итерации). Мы можем уменьшить его до O (log n), используя бинарный поиск .

C / C ++

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

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

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


Выход:

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

Сложность времени: алгоритм в целом все еще имеет время выполнения в наихудшем случае O (n 2 ) из-за серии перестановок, необходимых для каждой вставки.

Рекомендуемые посты:

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

0.00 (0%) 0 votes