Сортировка по сегменту для сортировки массива с отрицательными числами
Мы обсуждали сегментную сортировку в основном посте о 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
Здесь мы считаем, что число находится в диапазоне от -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.