Classe de galleda és una tècnica de classificació que consisteix a dividir elements en diversos grups, o galledes. Aquestes galledes es formen distribuint uniformement els elements. Un cop els elements es divideixen en cubs, es poden ordenar mitjançant qualsevol altre algorisme d'ordenació. Finalment, els elements ordenats es reuneixen de manera ordenada.
Algoritme d'ordenació de cubs:
Crear n buideu els cubs (O llistes) i feu el següent per a cada element de la matriu arr[i].
- Insereix arr[i] al cub[n*array[i]]
- Ordena els cubs individuals mitjançant l'ordenació per inserció.
- Concatenar tots els cubs ordenats.
Com funciona Bucket Sort?
Per aplicar l'ordenació de cubs a la matriu d'entrada [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68] , seguim aquests passos:
Pas 1: Creeu una matriu de mida 10, on cada ranura representi una galleda.
Creació de cubs per a la classificació
Pas 2: Inseriu elements als cubs de la matriu d'entrada en funció del seu rang.
Inserció d'elements a les galledes:
instància de java
- Agafeu cada element de la matriu d'entrada.
- Multipliqueu l'element per la mida de la matriu de cubs (10 en aquest cas). Per exemple, per a l'element 0,23, obtenim 0,23 * 10 = 2,3.
- Converteix el resultat a un nombre enter, que ens dóna l'índex de cub. En aquest cas, 2,3 es converteix en l'enter 2.
- Inseriu l'element a la galleda corresponent a l'índex calculat.
- Repetiu aquests passos per a tots els elements de la matriu d'entrada.
Inserció d'elements de la matriu als cubs respectius
Pas 3: Ordena els elements dins de cada galleda. En aquest exemple, fem servir quicksort (o qualsevol algorisme d'ordenació estable) per ordenar els elements dins de cada cub.
Classificació dels elements dins de cada galleda:
- Apliqueu un algorisme d'ordenació estable (p. ex., Bubble Sort, Merge Sort) per ordenar els elements dins de cada cub.
- Ara s'ordenen els elements de cada cub.
Classificació de cubeta individual
Pas 4: Recolliu els elements de cada galleda i torneu-los a posar a la matriu original.
Recollint elements de cada galleda:
convertir cadena a data
- Itera per cada cub en ordre.
- Inseriu cada element individual de la galleda a la matriu original.
- Un cop copiat un element, s'elimina de la galleda.
- Repetiu aquest procés per a totes les galledes fins que s'hagin reunit tots els elements.
Inserció de cubs en ordre ascendent a la matriu resultant
Pas 5: La matriu original ara conté els elements ordenats.
La matriu ordenada final que utilitza l'ordenació de cubs per a l'entrada donada és [0,12, 0,17, 0,21, 0,23, 0,26, 0,39, 0,68, 0,72, 0,78, 0,94].
Retorna la matriu ordenada
Implementació de l'algoritme d'ordenació de cubs:
A continuació es mostra la implementació de l'ordenació de cubs:
C++ #include #include using namespace std; // Insertion sort function to sort individual buckets void insertionSort(vector& cub) { per (int i = 1; i< bucket.size(); ++i) { float key = bucket[i]; int j = i - 1; while (j>= 0 && cub[j]> clau) { cub[j + 1] = cub[j]; j--; } cub[j + 1] = clau; } } // Funció per ordenar arr[] de mida n mitjançant bucket sort void bucketSort(float arr[], int n) { // 1) Crea n vector de cubs buitsb[n]; // 2) Posa elements de la matriu en diferents cubs per a (int i = 0; i< n; i++) { int bi = n * arr[i]; b[bi].push_back(arr[i]); } // 3) Sort individual buckets using insertion sort for (int i = 0; i < n; i++) { insertionSort(b[i]); } // 4) Concatenate all buckets into arr[] int index = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < b[i].size(); j++) { arr[index++] = b[i][j]; } } } // Driver program to test above function int main() { float arr[] = {0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434}; int n = sizeof(arr) / sizeof(arr[0]); bucketSort(arr, n); cout << 'Sorted array is
'; for (int i = 0; i < n; i++) { cout << arr[i] << ' '; } return 0; }>
Java import java.util.ArrayList; import java.util.List; public class Main { // Insertion sort function to sort individual buckets public static void insertionSort(Listcub) { per (int i = 1; i< bucket.size(); ++i) { float key = bucket.get(i); int j = i - 1; while (j>= 0 && bucket.get(j)> clau) { bucket.set(j + 1, bucket.get(j)); j--; } bucket.set(j + 1, clau); } } // Funció per ordenar arr[] de mida n utilitzant bucket sort public static void bucketSort(float[] arr) { int n = arr.length; // 1) Crea n llista de cubs buits[] cubs = nou ArrayList[n]; per (int i = 0; i< n; i++) { buckets[i] = new ArrayList(); } // 2) Put array elements in different buckets for (int i = 0; i < n; i++) { int bi = (int) (n * arr[i]); buckets[bi].add(arr[i]); } // 3) Sort individual buckets using insertion sort for (int i = 0; i < n; i++) { insertionSort(buckets[i]); } // 4) Concatenate all buckets into arr[] int index = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < buckets[i].size(); j++) { arr[index++] = buckets[i].get(j); } } } // Driver program to test above function public static void main(String[] args) { float[] arr = {0.897f, 0.565f, 0.656f, 0.1234f, 0.665f, 0.3434f}; bucketSort(arr); System.out.println('Sorted array is:'); for (float num : arr) { System.out.print(num + ' '); } } }> Python def insertion_sort(bucket): for i in range(1, len(bucket)): key = bucket[i] j = i - 1 while j>= 0 i cub[j]> clau: cub[j + 1] = cub[j] j -= 1 cub[j + 1] = clau def bucket_sort(arr): n = len(arr) cubs = [[] for _ in range(n)] # Posa els elements de la matriu en diferents cubs per num in arr: bi = int(n * num) buckets[bi].append(num) # Ordena els cubs individuals mitjançant l'ordenació d'inserció per al cub en cubs: insertion_sort (cub) # Concatenar tots els cubs a arr[] índex = 0 per al cub en cubs: per num al cub: arr[índex] = num índex += 1 arr = [0,897, 0,565, 0,656, 0,1234, 0,665, 0,3434] (arr) print('La matriu ordenada és:') print(' '.join(map(str, arr)))> C# using System; using System.Collections.Generic; class Program { // Insertion sort function to sort individual buckets static void InsertionSort(Listcub) { per (int i = 1; i< bucket.Count; ++i) { float key = bucket[i]; int j = i - 1; while (j>= 0 && cub[j]> clau) { cub[j + 1] = cub[j]; j--; } cub[j + 1] = clau; } } // Funció per ordenar arr[] de mida n utilitzant bucket sort static void BucketSort(float[] arr) { int n = arr.Length; // 1) Crea n llista de cubs buits[] cubs = llista nova[n]; per (int i = 0; i< n; i++) { buckets[i] = new List(); } // 2) Posa elements de la matriu en diferents cubs per a (int i = 0; i< n; i++) { int bi = (int)(n * arr[i]); buckets[bi].Add(arr[i]); } // 3) Sort individual buckets using insertion sort for (int i = 0; i < n; i++) { InsertionSort(buckets[i]); } // 4) Concatenate all buckets into arr[] int index = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < buckets[i].Count; j++) { arr[index++] = buckets[i][j]; } } } // Driver program to test above function static void Main(string[] args) { float[] arr = { 0.897f, 0.565f, 0.656f, 0.1234f, 0.665f, 0.3434f }; BucketSort(arr); Console.WriteLine('Sorted array is:'); foreach (float num in arr) { Console.Write(num + ' '); } } }> JavaScript function insertionSort(bucket) { for (let i = 1; i < bucket.length; ++i) { let key = bucket[i]; let j = i - 1; while (j>= 0 && cub[j]> clau) { cub[j + 1] = cub[j]; j--; } cub[j + 1] = clau; } } funció bucketSort(arr) { let n = arr.length; let buckets = Array.from({longitud: n}, () => []); // Posa elements de matriu en diferents cubs per a (deixar i = 0; i< n; i++) { let bi = Math.floor(n * arr[i]); buckets[bi].push(arr[i]); } // Sort individual buckets using insertion sort for (let i = 0; i < n; i++) { insertionSort(buckets[i]); } // Concatenate all buckets into arr[] let index = 0; for (let i = 0; i < n; i++) { for (let j = 0; j < buckets[i].length; j++) { arr[index++] = buckets[i][j]; } } } let arr = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434]; bucketSort(arr); console.log('Sorted array is:'); console.log(arr.join(' '));> Sortida
Sorted array is 0.1234 0.3434 0.565 0.656 0.665 0.897>
Anàlisi de complexitat de l'algoritme d'ordenació de cubs:
Complexitat temporal: O (n2),
- Si suposem que la inserció en una galleda triga O(1) temps, els passos 1 i 2 de l'algorisme anterior triguen clarament O(n) temps.
- L'O(1) és fàcilment possible si fem servir una llista enllaçada per representar un cub.
- El pas 4 també triga O (n) temps, ja que hi haurà n articles a tots els cubs.
- El pas principal a analitzar és el pas 3. Aquest pas també triga O(n) temps de mitjana si tots els nombres estan distribuïts uniformement.
Espai auxiliar: O(n+k)