Třídění kbelíků je technika třídění, která zahrnuje rozdělování prvků do různých skupin nebo kbelíků. Tyto kbelíky jsou tvořeny rovnoměrným rozložením prvků. Jakmile jsou prvky rozděleny do segmentů, lze je třídit pomocí jakéhokoli jiného třídícího algoritmu. Nakonec jsou setříděné prvky shromážděny dohromady uspořádaným způsobem.
Algoritmus řazení segmentů:
Vytvořit n prázdné kbelíky (nebo seznamy) a pro každý prvek pole arr[i] proveďte následující.
- Vložit arr[i] do bucket[n*array[i]]
- Seřaďte jednotlivé segmenty pomocí řazení vložení.
- Spojte všechny setříděné segmenty.
Jak funguje Bucket Sort?
Chcete-li použít třídění segmentů na vstupní pole [0,78, 0,17, 0,39, 0,26, 0,72, 0,94, 0,21, 0,12, 0,23, 0,68] , postupujeme takto:
Krok 1: Vytvořte pole o velikosti 10, kde každý slot představuje segment.
Vytváření kbelíků pro třídění
Krok 2: Vložte prvky do segmentů ze vstupního pole na základě jejich rozsahu.
Vkládání prvků do kbelíků:
- Vezměte každý prvek ze vstupního pole.
- Vynásobte prvek velikostí pole bucket (v tomto případě 10). Například pro prvek 0,23 dostaneme 0,23 * 10 = 2,3.
- Převeďte výsledek na celé číslo, které nám dá index segmentu. V tomto případě se 2,3 převede na celé číslo 2.
- Vložte prvek do kbelíku odpovídající vypočítanému indexu.
- Opakujte tyto kroky pro všechny prvky ve vstupním poli.
Vkládání prvků Array do příslušných kbelíků
Krok 3: Seřaďte prvky v každém kbelíku. V tomto příkladu používáme quicksort (nebo jakýkoli stabilní třídicí algoritmus) k třídění prvků v každém segmentu.
Řazení prvků v každém kbelíku:
- Použijte stabilní třídicí algoritmus (např. Bubble Sort, Sloučit Sort) k řazení prvků v každém segmentu.
- Prvky v každém segmentu jsou nyní seřazeny.
Třídění jednotlivých kbelíků
Krok 4: Shromážděte prvky z každého kbelíku a vložte je zpět do původního pole.
Shromažďování prvků z každého kbelíku:
- Procházejte každý kbelík v pořadí.
- Vložte každý jednotlivý prvek z kbelíku do původního pole.
- Jakmile je prvek zkopírován, je odstraněn z nádoby.
- Tento postup opakujte pro všechny kbelíky, dokud nebudou shromážděny všechny prvky.
Vkládání segmentů ve vzestupném pořadí do výsledného pole
Krok 5: Původní pole nyní obsahuje seřazené prvky.
Konečné seřazené pole pomocí segmentového třídění pro daný vstup je [0,12, 0,17, 0,21, 0,23, 0,26, 0,39, 0,68, 0,72, 0,78, 0,94].
Vraťte Sorted Array
Implementace algoritmu třídění segmentů:
Níže je uvedena implementace pro třídění segmentů:
C++ #include #include using namespace std; // Insertion sort function to sort individual buckets void insertionSort(vector& vědro) { for (int i = 1; i< bucket.size(); ++i) { float key = bucket[i]; int j = i - 1; while (j>= 0 && bucket[j]> key) { bucket[j + 1] = bucket[j]; j--; } kbelík[j + 1] = klíč; } } // Funkce pro třídění arr[] velikosti n pomocí bucket sort void bucketSort(float arr[], int n) { // 1) Vytvořte n prázdných bucket vectorb[n]; // 2) Vložte prvky pole do různých segmentů pro (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; }>
Jáva import java.util.ArrayList; import java.util.List; public class Main { // Insertion sort function to sort individual buckets public static void insertionSort(Listvědro) { 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, klíč); } } // Funkce pro třídění arr[] velikosti n pomocí bucket sort public static void bucketSort(float[] arr) { int n = arr.length; // 1) Vytvořte n prázdných bucketů List[] buckets = new ArrayList[n]; for (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 + ' '); } } }> Krajta def insertion_sort(bucket): for i in range(1, len(bucket)): key = bucket[i] j = i - 1 while j>= 0 a bucket[j]> klíč: bucket[j + 1] = bucket[j] j -= 1 bucket[j + 1] = klíč def bucket_sort(arr): n = len(arr) buckets = [[] for _ in range(n)] # Vložte prvky pole do různých segmentů pro num in arr: bi = int(n * num) segmenty[bi].append(num) # Seřaďte jednotlivé segmenty pomocí řazení vložení pro segment v segmentech: insertion_sort (bucket) # Zřetězit všechny segmenty do arr[] index = 0 pro segment v segmentech: pro num in bucket: arr[index] = num index += 1 arr = [0,897, 0,565, 0,656, 0,1234, 0,663, 0,663] bucket_bucket_ (arr) print('Sorted array is:') print(' '.join(map(str, arr)))> C# using System; using System.Collections.Generic; class Program { // Insertion sort function to sort individual buckets static void InsertionSort(Listvědro) { for (int i = 1; i< bucket.Count; ++i) { float key = bucket[i]; int j = i - 1; while (j>= 0 && bucket[j]> key) { bucket[j + 1] = bucket[j]; j--; } kbelík[j + 1] = klíč; } } // Funkce pro třídění arr[] velikosti n pomocí bucket sort static void BucketSort(float[] arr) { int n = arr.Length; // 1) Vytvořte n prázdných bucketů List[] buckets = nový seznam[n]; for (int i = 0; i< n; i++) { buckets[i] = new List(); } // 2) Vložte prvky pole do různých segmentů pro (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 && bucket[j]> key) { bucket[j + 1] = bucket[j]; j--; } kbelík[j + 1] = klíč; } } function bucketSort(arr) { let n = arr.length; let buckets = Array.from({délka: n}, () => []); // Vložte prvky pole do různých segmentů pro (nechť 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(' '));> Výstup
Sorted array is 0.1234 0.3434 0.565 0.656 0.665 0.897>
Analýza složitosti algoritmu řazení segmentů:
Časová náročnost: Na2),
- Pokud předpokládáme, že vložení do kbelíku trvá O(1) čas, pak kroky 1 a 2 výše uvedeného algoritmu jasně trvají O(n) čas.
- O(1) je snadno možné, pokud k reprezentaci segmentu použijeme propojený seznam.
- Krok 4 také trvá O(n), protože ve všech segmentech bude n položek.
- Hlavním krokem k analýze je krok 3. Tento krok také zabere v průměru čas O(n), pokud jsou všechna čísla rovnoměrně rozložena.
Pomocný prostor: O(n+k)