Emmer sorteren is een sorteertechniek waarbij elementen in verschillende groepen of emmers worden verdeeld. Deze emmers worden gevormd door de elementen gelijkmatig te verdelen. Zodra de elementen in buckets zijn verdeeld, kunnen ze worden gesorteerd met elk ander sorteeralgoritme. Ten slotte worden de gesorteerde elementen op een geordende manier verzameld.
Algoritme voor emmersortering:
Creëren N lege buckets (of lijsten) en doe het volgende voor elk array-element arr[i].
- Plaats arr[i] in bucket[n*array[i]]
- Sorteer individuele buckets met behulp van invoegsortering.
- Voeg alle gesorteerde buckets samen.
Hoe werkt Bucket Sorteren?
Om bucketsortering toe te passen op de invoerarray [0,78, 0,17, 0,39, 0,26, 0,72, 0,94, 0,21, 0,12, 0,23, 0,68] , volgen we deze stappen:
Stap 1: Maak een array van grootte 10, waarbij elke sleuf een bucket vertegenwoordigt.
ssis-tutorial
Emmers maken voor sorteren
Stap 2: Voeg elementen in de buckets uit de invoerarray in op basis van hun bereik.
Elementen in de emmers plaatsen:
- Neem elk element uit de invoerarray.
- Vermenigvuldig het element met de grootte van de bucketarray (in dit geval 10). Voor element 0,23 krijgen we bijvoorbeeld 0,23 * 10 = 2,3.
- Converteer het resultaat naar een geheel getal, wat ons de bucketindex geeft. In dit geval wordt 2,3 omgezet naar het gehele getal 2.
- Plaats het element in de bucket die overeenkomt met de berekende index.
- Herhaal deze stappen voor alle elementen in de invoerarray.
Array-elementen in de respectievelijke buckets invoegen
Stap 3: Sorteer de elementen binnen elke emmer. In dit voorbeeld gebruiken we quicksort (of een stabiel sorteeralgoritme) om de elementen binnen elke bucket te sorteren.
De elementen binnen elke emmer sorteren:
Java-referentietypen
- Pas een stabiel sorteeralgoritme toe (bijvoorbeeld Bubble Sort, Merge Sort) om de elementen binnen elke bucket te sorteren.
- De elementen binnen elke emmer zijn nu gesorteerd.
Individuele emmer sorteren
Stap 4: Verzamel de elementen uit elke emmer en plaats ze terug in de oorspronkelijke array.
Elementen uit elke emmer verzamelen:
verwijder npm-cache
- Herhaal elke bucket in volgorde.
- Plaats elk afzonderlijk element uit de bucket in de originele array.
- Zodra een element is gekopieerd, wordt het uit de bucket verwijderd.
- Herhaal dit proces voor alle emmers totdat alle elementen zijn verzameld.
Buckets in oplopende volgorde in de resulterende array invoegen
Stap 5: De originele array bevat nu de gesorteerde elementen.
De uiteindelijk gesorteerde array die gebruik maakt van bucket-sortering voor de gegeven invoer is [0,12, 0,17, 0,21, 0,23, 0,26, 0,39, 0,68, 0,72, 0,78, 0,94].
string.vergelijk c#
Retourneer de gesorteerde array
Implementatie van het bucketsorteeralgoritme:
Hieronder ziet u de implementatie voor de Bucket Sort:
C++ #include #include using namespace std; // Insertion sort function to sort individual buckets void insertionSort(vector& emmer) { voor (int i = 1; i< bucket.size(); ++i) { float key = bucket[i]; int j = i - 1; while (j>= 0 && emmer[j]> sleutel) { emmer[j + 1] = emmer[j]; J--; } emmer[j + 1] = sleutel; } } // Functie om arr[] van grootte n te sorteren met behulp van bucket sort void bucketSort(float arr[], int n) {// 1) Maak n lege buckets-vectorb[n]; // 2) Plaats array-elementen in verschillende buckets voor (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(Listemmer) { voor (int i = 1; i< bucket.size(); ++i) { float key = bucket.get(i); int j = i - 1; while (j>= 0 && bucket.get(j)> sleutel) { bucket.set(j + 1, bucket.get(j)); J--; } bucket.set(j + 1, sleutel); } } // Functie om arr[] van grootte n te sorteren met behulp van bucket sort public static void bucketSort(float[] arr) { int n = arr.length; // 1) Maak een lege bucketlijst[] buckets = nieuwe ArrayList[n]; voor (int i = 0; ik< 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 en bucket[j]> sleutel: bucket[j + 1] = bucket[j] j -= 1 bucket[j + 1] = sleutel def bucket_sort(arr): n = len(arr) buckets = [[] for _ in range(n)] # Zet array-elementen in verschillende buckets voor num in arr: bi = int(n * num) buckets[bi].append(num) # Sorteer individuele buckets met behulp van invoegsortering voor bucket in buckets: insertion_sort (bucket) # Voeg alle buckets samen in arr[] index = 0 voor bucket in buckets: voor num in bucket: arr[index] = num index += 1 arr = [0,897, 0,565, 0,656, 0,1234, 0,665, 0,3434] bucket_sort (arr) print('Gesorteerde 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(Listemmer) { voor (int i = 1; i< bucket.Count; ++i) { float key = bucket[i]; int j = i - 1; while (j>= 0 && emmer[j]> sleutel) { emmer[j + 1] = emmer[j]; J--; } emmer[j + 1] = sleutel; } } // Functie om arr[] van grootte n te sorteren met behulp van bucket sort static void BucketSort(float[] arr) { int n = arr.Length; // 1) Maak een lege bucketlijst[] buckets = nieuwe lijst[N]; voor (int i = 0; ik< n; i++) { buckets[i] = new List(); } // 2) Plaats array-elementen in verschillende buckets voor (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 && emmer[j]> sleutel) { emmer[j + 1] = emmer[j]; J--; } emmer[j + 1] = sleutel; } } functie bucketSort(arr) { laat n = arr.lengte; laat buckets = Array.from({lengte: n}, () => []); // Plaats array-elementen in verschillende buckets voor (laat 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(' '));> Uitvoer
Sorted array is 0.1234 0.3434 0.565 0.656 0.665 0.897>
Complexiteitsanalyse van het bucketsorteeralgoritme:
Tijdcomplexiteit: Op2),
- Als we aannemen dat het inbrengen in een emmer O(1) tijd kost, dan nemen de stappen 1 en 2 van het bovenstaande algoritme duidelijk O(n) tijd in beslag.
- De O(1) is gemakkelijk mogelijk als we een gekoppelde lijst gebruiken om een bucket weer te geven.
- Stap 4 kost ook O(n) tijd, omdat er in alle buckets n items zitten.
- De belangrijkste stap om te analyseren is stap 3. Deze stap kost ook gemiddeld O(n) tijd als alle getallen uniform verdeeld zijn.
Hulpruimte: O(n+k)