Рубрики

Сортировка по голубям

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

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

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

Сравнение с подсчетом сортировки:
Это похоже на подсчет сортировки , но отличается тем, что «перемещает элементы дважды: один раз в массив сегментов и снова в конечный пункт назначения».

C ++

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

}

Джава

/ * Java-программа для реализации Pigeonhole Sort * /

  

import java.lang.*;

import java.util.*;

  

public class GFG

{

    public static void pigeonhole_sort(int arr[],

                                           int n)

    {

        int min = arr[0];

        int max = arr[0];

        int range, i, j, index; 

  

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

        {

            if(arr[a] > max)

                max = arr[a];

            if(arr[a] < min)

                min = arr[a];

        }

  

        range = max - min + 1;

        int[] phole = new int[range];

        Arrays.fill(phole, 0);

  

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

            phole[arr[i] - min]++;

  

          

        index = 0;

  

        for(j = 0; j<range; j++)

            while(phole[j]-->0)

                arr[index++]=j+min;

  

    }

  

    public static void main(String[] args)

    {

        GFG sort = new GFG();

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

  

        System.out.print("Sorted order is : ");

  

        sort.pigeonhole_sort(arr,arr.length);

          

        for(int i=0 ; i<arr.length ; i++)

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

    }

  
}

  
// Код предоставлен Mohit Gupta_OMG <(0_o)>

python3

# Программа Python для реализации Pigeonhole Sort * /

  
# исходный код: " https://en.wikibooks.org/wiki/
# Algorithm_Implementation / Sorting / Pigeonhole_sort "

def pigeonhole_sort(a):

    # размер диапазона значений в списке

    # (т.е. количество нужных ямок)

    my_min = min(a)

    my_max = max(a)

    size = my_max - my_min + 1

  

    # наш список ям

    holes = [0] * size

  

    # Заполните голубиные отверстия.

    for x in a:

        assert type(x) is int, "integers only please"

        holes[x - my_min] += 1

  

    # Поместить элементы обратно в массив по порядку.

    i = 0

    for count in range(size):

        while holes[count] > 0:

            holes[count] -= 1

            a[i] = count + my_min

            i += 1

              

  

a = [8, 3, 2, 7, 4, 6, 8]

print("Sorted order is : ", end = ' ')

  
pigeonhole_sort(a)

          

for i in range(0, len(a)):

    print(a[i], end = ' ')

     

C #

// C # программа для реализации
// Pigeonhole Sort

using System;

  

class GFG

{

public static void pigeonhole_sort(int []arr,

                                   int n)

{

    int min = arr[0];

    int max = arr[0];

    int range, i, j, index; 

  

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

    {

        if(arr[a] > max)

            max = arr[a];

        if(arr[a] < min)

            min = arr[a];

    }

  

    range = max - min + 1;

    int[] phole = new int[range];

      

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

    phole[i] = 0;

  

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

        phole[arr[i] - min]++;

  

      

    index = 0;

  

    for(j = 0; j < range; j++)

        while(phole[j] --> 0)

            arr[index++] = j + min;

  
}

  
// Код драйвера

static void Main()

{

    int[] arr = {8, 3, 2, 7, 

                 4, 6, 8};

  

    Console.Write("Sorted order is : ");

  

    pigeonhole_sort(arr,arr.Length);

      

    for(int i = 0 ; i < arr.Length ; i++)

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

}
}

  
// Этот код добавлен
// Sam007


Выход:

Sorted order is : 2 3 4 6 7 8 8 

Сорт с голубями имеет ограниченное применение, так как требования редко выполняются. Для массивов, где диапазон намного больше n , сортировка по сегментам является обобщением, которое более эффективно в пространстве и времени.

Ссылки:
https://en.wikipedia.org/wiki/Pigeonhole_sort

Эта статья предоставлена Аюш Говил . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме


Другие алгоритмы сортировки на GeeksforGeeks / GeeksQuiz

Сортировка выбора , пузырьковая сортировка , сортировка вставкой, сортировка слиянием, сортировка кучи , быстрая сортировка , сортировка по радикалу , счетная сортировка , сортировка по корзинам , ShellSort , сортировка по гребне ,

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

Сортировка по голубям

0.00 (0%) 0 votes