Рубрики

Сортировка ведра для сортировки массива с отрицательными числами

Мы обсудили сортировку ведер в главном посте по сортировке ведер .
Сортировка по группам в основном полезна, когда входные данные равномерно распределены по диапазону. Например, рассмотрим проблему сортировки большого набора чисел с плавающей запятой, которые находятся в диапазоне от 0,0 до 1,0 и равномерно распределены по всему диапазону. В приведенном выше посте мы обсудили сортировку по группам для сортировки чисел, которые больше нуля.

Как изменить Bucket Sort для сортировки как положительных, так и отрицательных чисел?

Пример:

Input : arr[] = { -0.897, 0.565, 0.656, -0.1234, 0, 0.3434 } 
Output : -0.897 -0.1234  0 0.3434 0.565 0.656 

Здесь мы рассматриваем число в диапазоне от -1,0 до 1,0 (число с плавающей запятой)
Алгоритм:

sortMixed(arr[], n)
1) Split array into two parts 
   create two Empty vector Neg[], Pos[] 
   (for negative and positive element respectively)
   Store all negative element in Neg[] by converting
   into positive (Neg[i] = -1 * Arr[i] )
   Store all +ve in pos[]  (pos[i] =  Arr[i])
2) Call function bucketSortPositive(Pos, pos.size())
   Call function bucketSortPositive(Neg, Neg.size())

bucketSortPositive(arr[], n)
3) Create n empty buckets (Or lists).
4) Do following for every array element arr[i]. 
       a) Insert arr[i] into bucket[n*array[i]]
5) Sort individual buckets using insertion sort.
6) Concatenate all sorted buckets. 

Ниже приведена реализация вышеуказанной идеи на языке c ++ (для числа с плавающей запятой).

// C ++ программа для сортировки массива положительных
// и отрицательные числа с использованием сортировки по группам
#include <bits/stdc++.h>

using namespace std;

  
// Функция для сортировки arr [] размера n используя
// сортировка ведра

void bucketSort(vector<float> &arr, int n)

{

    // 1) Создать n пустых сегментов

    vector<float> b[n];

  

    // 2) Поместить элементы массива в разные

    // ведра

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

    {

        int bi = n*arr[i]; // Индекс в корзине

        b[bi].push_back(arr[i]);

    }

  

    // 3) Сортировка отдельных ведер

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

        sort(b[i].begin(), b[i].end());

  

    // 4) Объединить все сегменты в arr []

    int index = 0;

    arr.clear();

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

        for (int j = 0; j < b[i].size(); j++)

            arr.push_back(b[i][j]);

}

  
// Эта функция в основном разбивает массив на две части
// и затем вызывает bucketSort () для двух массивов.

void sortMixed(float arr[], int n)

{

    vector<float>Neg ;

    vector<float>Pos;

  

    // пройти элементы массива

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

    {

        if (arr[i] < 0)

  

            // сохраняем элементы

            // преобразование в + ve элемент

            Neg.push_back (-1 * arr[i]) ;

        else

            // store + ve elements

            Pos.push_back (arr[i]) ;

    }

  

    bucketSort(Neg, (int)Neg.size());

    bucketSort(Pos, (int)Pos.size());

  

    // Сначала сохраняем элементы массива Neg []

    // путем преобразования в -ve

    for (int i=0; i < Neg.size(); i++)

        arr[i] = -1 * Neg[ Neg.size() -1 - i];

  

    // store + ve element

    for(int j=Neg.size(); j < n; j++)

        arr[j] = Pos[j - Neg.size()];

}

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

int main()

{

    float arr[] = {-0.897, 0.565, 0.656,

                   -0.1234, 0, 0.3434};

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

    sortMixed(arr, n);

  

    cout << "Sorted array is \n";

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

        cout << arr[i] << " ";

    return 0;

}

Выход:

Sorted array is 
-0.897  -0.1234 0 0.3434 0.565 0.656 

Эта статья предоставлена Nishant Singh . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Сортировка ведра для сортировки массива с отрицательными числами

0.00 (0%) 0 votes