Рубрики

Java программа для сортировки по голубям

Java Программы, Сортировка

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

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

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

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

Выход:

Sorted order is : 2 3 4 6 7 8 8

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

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

Java программа для сортировки по голубям

0.00 (0%) 0 votes