Рубрики

Программа C для бинарной сортировки

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

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;

}

Пожалуйста, обратитесь к полной статье о бинарной сортировке для более подробной информации!

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

Программа C для бинарной сортировки

0.00 (0%) 0 votes