Hemos discutido la clasificación de cubos en la publicación principal sobre Clasificación de cubos .
La ordenación de cubos es principalmente útil cuando la entrada se distribuye uniformemente en un rango. Por ejemplo, considere el problema de ordenar un gran conjunto de números de punto flotante que están en el rango de 0,0 a 1,0 y están uniformemente distribuidos en el rango. En la publicación anterior, hemos discutido Bucket Sort para ordenar números que son mayores que cero.
¿Cómo modificar Bucket Sort para ordenar números positivos y negativos?
Ejemplo:
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
Aquí consideramos que el número está en el rango -1.0 a 1.0 (número de punto flotante)
Algoritmo:
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.
A continuación se muestra la implementación de la idea anterior (para el número de punto flotante)
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 splits 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 \n"; 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 splits 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 \n"); for (int i = 0; i < n; i++) System.out.print(arr[i] + " "); } } // This code is contributed by Rajput-Ji
Python3
# Python3 program to sort an array of positive # and negative numbers using bucket sort # Function to sort arr[] of size n using # bucket sort def bucketSort(arr, n): # 1) Create n empty buckets b = [] for i in range(n): b.append([]) # 2) Put array elements in different # buckets for i in range(n): bi = int(n*arr[i]) b[bi].append(arr[i]) # 3) Sort individual buckets for i in range(n): b[i].sort() # 4) Concatenate all buckets into arr[] index = 0 arr.clear() for i in range(n): for j in range(len(b[i])): arr.append(b[i][j]) # This function mainly splits array into two # and then calls bucketSort() for two arrays. def sortMixed(arr, n): Neg = [] Pos = [] # traverse array elements for i in range(n): if(arr[i]<0): # store -Ve elements by # converting into +ve element Neg.append(-1*arr[i]) else: # store +ve elements Pos.append(arr[i]) bucketSort(Neg,len(Neg)) bucketSort(Pos,len(Pos)) # First store elements of Neg[] array # by converting into -ve for i in range(len(Neg)): arr[i]=-1*Neg[len(Neg)-1-i] # store +ve element for i in range(len(Neg),n): arr[i]= Pos[i-len(Neg)] # Driver program to test above function arr = [-0.897, 0.565, 0.656, -0.1234, 0, 0.3434] sortMixed(arr, len(arr)) print("Sorted Array is") print(arr) # This code is contributed by Pushpesh raj
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 splits 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 \n"); for (int i = 0; i < n; i++) Console.Write(arr[i] + " "); } } // This code is contributed by Rajput-Ji
Producción:
Sorted array is -0.897 -0.1234 0 0.3434 0.565 0.656
Este artículo es una contribución de Nishant Singh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA