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

Опубликовано: 20 Января, 2022

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

 Ввод: arr [] = {-0,897, 0,565, 0,656, -0,1234, 0, 0,3434}. 
Выход: -0,897 -0,1234 0 0,3434 0,565 0,656

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

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

 sortMixed (обр [], n)
1) Разделить массив на две части 
   создать два пустых вектора Neg [], Pos [] 
   (для отрицательного и положительного элемента соответственно)
   Сохраните все отрицательные элементы в Neg [] путем преобразования
   в положительное (Neg [i] = -1 * Arr [i])
   Сохранить все + ve в pos [] (pos [i] = Arr [i])
2) Вызов функции bucketSortPositive (Pos, pos.size ())
   Вызов функции bucketSortPositive (Neg, Neg.size ())

bucketSortPositive (arr [], n)
3) Создайте n пустых корзин (или списков).
4) Выполните следующие действия для каждого элемента массива arr [i]. 
       а) Вставьте arr [i] в bucket [n * array [i]]
5) Сортировка отдельных сегментов с помощью сортировки вставкой.
6) Объедините все отсортированные ведра.

Below is implementation of above idea (for floating point number )
 

CPP

// C++ program to sort an array of positive
// and negative numbers using bucket sort
#include <bits/stdc++.h>
using namespace std;
 
// Function to sort arr[] of size n using
// bucket sort
void bucketSort(vector<float> &arr, int n)
{
    // 1) Create n empty buckets
    vector<float> b[n];
 
    // 2) Put array elements in different
    //    buckets
    for (int i=0; i<n; i++)
    {
        int bi = n*arr[i]; // Index in bucket
        b[bi].push_back(arr[i]);
    }
 
    // 3) Sort individual buckets
    for (int i=0; i<n; i++)
        sort(b[i].begin(), b[i].end());
 
    // 4) Concatenate all buckets into 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]);
}
 
// This function mainly slpits array into two
// and then calls bucketSort() for two arrays.
void sortMixed(float arr[], int n)
{
    vector<float>Neg ;
    vector<float>Pos;
 
    // traverse array elements
    for (int i=0; i<n; i++)
    {
        if (arr[i] < 0)
 
            // store -Ve elements by
            // converting into +ve element
            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());
 
    // First store elements of Neg[] array
    // by converting into -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()];
}
 
/* Driver program to test above function */
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 ";
    for (int i=0; i<n; i++)
        cout << arr[i] << " ";
    return 0;
}

Java

// Java program to sort an array of positive
// and negative numbers using bucket sort
import java.util.*;
class GFG
{
 
  // Function to sort arr[] of size n using
  // bucket sort
  static void bucketSort(Vector<Double> arr, int n)
  {
 
    // 1) Create n empty buckets
    @SuppressWarnings("unchecked")
    Vector<Double> b[] = new Vector[n];
    for (int i = 0; i < b.length; i++)
      b[i] = new Vector<Double>();
 
    // 2) Put array elements in different
    // buckets
    for (int i = 0; i < n; i++)
    {
      int bi = (int)(n*arr.get(i)); // Index in bucket
      b[bi].add(arr.get(i));
    }
 
    // 3) Sort individual buckets
    for (int i = 0; i < n; i++)
      Collections.sort(b[i]);
 
    // 4) Concatenate all buckets into arr[]
    int index = 0;
    arr.clear();
    for (int i = 0; i < n; i++)
      for (int j = 0; j < b[i].size(); j++)
        arr.add(b[i].get(j));
  }
 
  // This function mainly slpits array into two
  // and then calls bucketSort() for two arrays.
  static void sortMixed(double arr[], int n)
  {
    Vector<Double>Neg = new Vector<>();
    Vector<Double>Pos = new Vector<>(); 
 
    // traverse array elements
    for (int i = 0; i < n; i++)
    {
      if (arr[i] < 0)
 
        // store -Ve elements by
        // converting into +ve element
        Neg.add (-1 * arr[i]) ;
      else
 
        // store +ve elements
        Pos.add (arr[i]) ;
    }
    bucketSort(Neg, (int)Neg.size());
    bucketSort(Pos, (int)Pos.size());
 
    // First store elements of Neg[] array
    // by converting into -ve
    for (int i = 0; i < Neg.size(); i++)
      arr[i] = -1 * Neg.get( Neg.size() -1 - i);
 
    // store +ve element
    for(int j = Neg.size(); j < n; j++)
      arr[j] = Pos.get(j - Neg.size());
  }
 
  /* Driver program to test above function */
  public static void main(String[] args)
  {
    double arr[] = {-0.897, 0.565, 0.656,
                    -0.1234, 0, 0.3434};
    int n = arr.length;
    sortMixed(arr, n);
 
    System.out.print("Sorted array is ");
    for (int i = 0; i < n; i++)
      System.out.print(arr[i] + " ");
  }
}
 
// This code is contributed by Rajput-Ji

C#

// C# program to sort an array of positive
// and negative numbers using bucket sort
using System;
using System.Collections.Generic;
 
public class GFG
{
 
  // Function to sort []arr of size n using
  // bucket sort
  static void bucketSort(List<Double> arr, int n)
  {
 
    // 1) Create n empty buckets
 
    List<Double> []b = new List<Double>[n];
    for (int i = 0; i < b.Length; i++)
      b[i] = new List<Double>();
 
    // 2) Put array elements in different
    // buckets
    for (int i = 0; i < n; i++)
    {
      int bi = (int)(n*arr[i]); // Index in bucket
      b[bi].Add(arr[i]);
    }
 
    // 3) Sort individual buckets
    for (int i = 0; i < n; i++)
      b[i].Sort();
 
    // 4) Concatenate all buckets into []arr
    int index = 0;
    arr.Clear();
    for (int i = 0; i < n; i++)
      for (int j = 0; j < b[i].Count; j++)
        arr.Add(b[i][j]);
  }
 
  // This function mainly slpits array into two
  // and then calls bucketSort() for two arrays.
  static void sortMixed(double []arr, int n)
  {
    List<Double>Neg = new List<Double>();
    List<Double>Pos = new List<Double>(); 
 
    // traverse array elements
    for (int i = 0; i < n; i++)
    {
      if (arr[i] < 0)
 
        // store -Ve elements by
        // converting into +ve element
        Neg.Add (-1 * arr[i]) ;
      else
 
        // store +ve elements
        Pos.Add (arr[i]) ;
    }
    bucketSort(Neg, (int)Neg.Count);
    bucketSort(Pos, (int)Pos.Count);
 
    // First store elements of Neg[] array
    // by converting into -ve
    for (int i = 0; i < Neg.Count; i++)
      arr[i] = -1 * Neg[ Neg.Count -1 - i];
 
    // store +ve element
    for(int j = Neg.Count; j < n; j++)
      arr[j] = Pos[j - Neg.Count];
  }
 
  /* Driver program to test above function */
  public static void Main(String[] args)
  {
    double []arr = {-0.897, 0.565, 0.656,
                    -0.1234, 0, 0.3434};
    int n = arr.Length;
    sortMixed(arr, n);
 
    Console.Write("Sorted array is ");
    for (int i = 0; i < n; i++)
      Console.Write(arr[i] + " ");
  }
}
 
// This code is contributed by Rajput-Ji

Выход:

Sorted array is 
-0.897  -0.1234 0 0.3434 0.565 0.656 

Эта статья предоставлена Нишантом Сингхом. Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

РЕКОМЕНДУЕМЫЕ СТАТЬИ