Рубрики

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

Сортировка по Голубому отверстию — это алгоритм сортировки, который подходит для сортировки списков элементов, в которых количество элементов и число возможных ключевых значений примерно одинаковы.
Требуется время O (+), где n — количество элементов во входном массиве, а Range — количество возможных значений в массиве.

Работа алгоритма:

  1. Найти минимальные и максимальные значения в массиве. Пусть минимальные и максимальные значения равны 'min' и 'max' соответственно. Также найдите диапазон как «max-min-1».
  2. Создайте массив изначально пустых «ямок для сообщений» того же размера, что и диапазон.
  3. Посетите каждый элемент массива, а затем поместите каждый элемент в свое отверстие. Элемент arr [i] помещается в отверстие по индексу arr [i] — мин.
  4. Запустите цикл по всему массиву голубиных отверстий по порядку и поместите элементы из непустых отверстий обратно в исходный массив.

/ * C программа для реализации Pigeonhole Sort * /
#include <bits/stdc++.h>

using namespace std;

  
/ * Сортирует массив, используя алгоритм Pigeonhole * /

void pigeonholeSort(int arr[], int n)

{

    // Находим минимальное и максимальное значения в arr []

    int min = arr[0], max = arr[0];

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

        if (arr[i] < min)

            min = arr[i];

        if (arr[i] > max)

            max = arr[i];

    }

    int range = max - min + 1; // Найти диапазон

  

    // Создать массив векторов. Размер массива

    // ассортимент. Каждый вектор представляет собой отверстие, которое

    // будет содержать совпадающие элементы.

    vector<int> holes[range];

  

    // Пройдите через входной массив и поместите каждый

    // элемент в соответствующем отверстии

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

        holes[arr[i] - min].push_back(arr[i]);

  

    // Пройдите через все отверстия одно за другим. За

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

    // массив.

    int index = 0; // индекс в отсортированном массиве

    for (int i = 0; i < range; i++) {

        vector<int>::iterator it;

        for (it = holes[i].begin(); it != holes[i].end(); ++it)

            arr[index++] = *it;

    }

}

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

int main()

{

    int arr[] = { 8, 3, 2, 7, 4, 6, 8 };

    int n = sizeof(arr) / sizeof(arr[0]);

  

    pigeonholeSort(arr, n);

  

    printf("Sorted order is : ");

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

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

  

    return 0;

}

Выход:

Sorted order is : 2 3 4 6 7 8 8

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

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

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

0.00 (0%) 0 votes