Sortare cu găleată este o tehnică de sortare care implică împărțirea elementelor în diferite grupuri, sau găleți. Aceste găleți sunt formate prin distribuirea uniformă a elementelor. Odată ce elementele sunt împărțite în găleți, acestea pot fi sortate folosind orice alt algoritm de sortare. În cele din urmă, elementele sortate sunt adunate împreună într-o manieră ordonată.
Algoritmul de sortare al găleților:
Crea n goliți găleți (Sau liste) și faceți următoarele pentru fiecare element de matrice arr[i].
- Introduceți arr[i] în bucket[n*array[i]]
- Sortați găleți individuale folosind sortarea prin inserție.
- Concatenează toate gălețile sortate.
Cum funcționează Bucket Sort?
Pentru a aplica sortarea găleților pe matricea de intrare [0,78, 0,17, 0,39, 0,26, 0,72, 0,94, 0,21, 0,12, 0,23, 0,68] , urmam acești pași:
Pasul 1: Creați o matrice de dimensiunea 10, în care fiecare slot reprezintă o găleată.
care a creat școala
Crearea de găleți pentru sortare
Pasul 2: Inserați elemente în găleți din matricea de intrare în funcție de intervalul lor.
lista imuabilă java
Introducerea elementelor în găleți:
- Luați fiecare element din tabloul de intrare.
- Înmulțiți elementul cu dimensiunea matricei de găleți (10 în acest caz). De exemplu, pentru elementul 0,23, obținem 0,23 * 10 = 2,3.
- Convertiți rezultatul într-un număr întreg, care ne oferă indicele găleții. În acest caz, 2.3 este convertit în întregul 2.
- Introduceți elementul în găleată corespunzătoare indicelui calculat.
- Repetați acești pași pentru toate elementele din matricea de intrare.
Inserarea elementelor Array în gălețile respective
Pasul 3: Sortați elementele din fiecare găleată. În acest exemplu, folosim sortarea rapidă (sau orice algoritm de sortare stabil) pentru a sorta elementele din fiecare găleată.
Sortarea elementelor din fiecare găleată:
- Aplicați un algoritm de sortare stabil (de exemplu, Sortare cu bule, Sortare îmbinare) pentru a sorta elementele din fiecare grupă.
- Elementele din fiecare găleată sunt acum sortate.
Sortare găleată individuală
Pasul 4: Adunați elementele din fiecare găleată și puneți-le înapoi în matricea originală.
Adunarea elementelor din fiecare găleată:
- Repetați fiecare găleată în ordine.
- Introduceți fiecare element individual din găleată în matricea originală.
- Odată ce un element este copiat, acesta este scos din găleată.
- Repetați acest proces pentru toate gălețile până când toate elementele au fost adunate.
Inserarea găleților în ordine crescătoare în matricea rezultată
șir de listă java
Pasul 5: Matricea originală conține acum elementele sortate.
Matricea sortată finală folosind sortarea găleților pentru intrarea dată este [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.68, 0.72, 0.78, 0.94].
model de proiectare a metodei din fabrică
Returnează matricea sortată
Implementarea algoritmului de sortare a găleților:
Mai jos este implementarea pentru sortarea găleții:
C++ #include #include using namespace std; // Insertion sort function to sort individual buckets void insertionSort(vector& găleată) { pentru (int i = 1; i< bucket.size(); ++i) { float key = bucket[i]; int j = i - 1; while (j>= 0 && găleată[j]> cheie) { găleată[j + 1] = găleată[j]; j--; } găleată[j + 1] = cheie; } } // Funcție pentru a sorta arr[] de dimensiunea n folosind bucket sort void bucketSort(float arr[], int n) { // 1) Creați n vector de găleți goaleb[n]; // 2) Pune elemente de matrice în diferite compartimente pentru (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(Listgăleată) { for (int i = 1; i< bucket.size(); ++i) { float key = bucket.get(i); int j = i - 1; while (j>= 0 && bucket.get(j)> key) { bucket.set(j + 1, bucket.get(j)); j--; } bucket.set(j + 1, cheie); } } // Funcție de sortare arr[] de dimensiunea n folosind bucket sort public static void bucketSort(float[] arr) { int n = arr.length; // 1) Creați n listă de găleți goale[] buckets = new ArrayList[n]; pentru (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 + ' '); } } }> Piton def insertion_sort(bucket): for i in range(1, len(bucket)): key = bucket[i] j = i - 1 while j>= 0 și bucket[j]> cheie: bucket[j + 1] = bucket[j] j -= 1 bucket[j + 1] = key def bucket_sort(arr): n = len(arr) buckets = [[] pentru _ în interval(n)] # Pune elemente de matrice în diferite găleți pentru num în arr: bi = int(n * num) găleți[bi].append(num) # Sortează găleți individuale folosind sortarea inserției pentru găleți în găleți: insertion_sort (găleată) # Concatenați toate gălețile în arr[] index = 0 pentru găleată în găleți: pentru num în găleată: arr[index] = num index += 1 arr = [0.897, 0.565, 0.656, 0.1234, 0.665, 0.3434] (arr) print('Matricea sortată este:') print(' '.join(map(str, arr)))> C# using System; using System.Collections.Generic; class Program { // Insertion sort function to sort individual buckets static void InsertionSort(Listgăleată) { for (int i = 1; i< bucket.Count; ++i) { float key = bucket[i]; int j = i - 1; while (j>= 0 && găleată[j]> cheie) { găleată[j + 1] = găleată[j]; j--; } găleată[j + 1] = cheie; } } // Funcție de sortare arr[] de dimensiunea n folosind bucket sort static void BucketSort(float[] arr) { int n = arr.Length; // 1) Creați n listă de găleți goale[] găleți = Listă nouă[n]; pentru (int i = 0; i< n; i++) { buckets[i] = new List(); } // 2) Pune elemente de matrice în diferite compartimente pentru (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 && găleată[j]> cheie) { găleată[j + 1] = găleată[j]; j--; } găleată[j + 1] = cheie; } } function bucketSort(arr) { let n = arr.length; let buckets = Array.from({lungime: n}, () => []); // Pune elemente de matrice în diferite găleți pentru (fie 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(' '));> Ieșire
Sorted array is 0.1234 0.3434 0.565 0.656 0.665 0.897>
Analiza complexității algoritmului de sortare a găleților:
Complexitatea timpului: Pe2),
- Dacă presupunem că inserarea într-o găleată durează O(1) timp, atunci pașii 1 și 2 ai algoritmului de mai sus iau în mod clar O(n) timp.
- O(1) este ușor posibil dacă folosim o listă legată pentru a reprezenta o găleată.
- Pasul 4 necesită, de asemenea, timp O(n), deoarece vor fi n articole în toate gălețile.
- Pasul principal de analizat este pasul 3. Acest pas necesită, de asemenea, timp O(n) în medie dacă toate numerele sunt distribuite uniform.
Spațiu auxiliar: O(n+k)