Algoritme voor emmersortering (Java, Python, C/C++ Codevoorbeelden)
Wat is bucketsortering?
Bucket sort, vaak bin sort genoemd, is een vergelijkingssorteermethode die een ongesorteerde array als invoer accepteert en als resultaat een gesorteerde array produceert. Deze methode werkt door de elementen over verschillende buckets te verdelen en elk van die buckets afzonderlijk te sorteren met behulp van een sorteeralgoritme, zoals invoegsortering. Vervolgens worden alle buckets samengevoegd om een gesorteerde array te vormen.
Emmersortering wordt vaak gebruikt wanneer de elementen:
- Waarden met drijvende komma
- Uniform verdeeld over een bereik
De tijdcomplexiteit van bucket sort hangt af van het aantal gebruikte buckets en de uniformiteit van de invoerdistributie. Hoewel verschillende sorteeralgoritmen zoals schelp soort, sorteer, heapsort en Snel sorteren kan de beste tijdcomplexiteit van O(n*logn) bereiken, het bucket-sorteeralgoritme kan hetzelfde bereiken in lineaire tijdcomplexiteit of O(n).
Bucket sort volgt de scatter-gather-benadering. Door deze benadering toe te passen, worden elementen verspreid in de bijbehorende buckets, gesorteerd in de buckets en verzameld om een gesorteerde array te vormen als laatste stap. Deze scatter-gather-benadering wordt besproken in de volgende sectie
Verspreid-verzamel-benadering
Grote, complexe problemen kunnen soms lastig op te lossen zijn. De scatter-gather-aanpak probeert dergelijke problemen op te lossen door de hele dataset in clusters te verdelen. Vervolgens wordt elk cluster apart aangepakt en alles weer bij elkaar gebracht om het uiteindelijke antwoord te krijgen.
Dit is hoe het bucket-sorteeralgoritme de scatter-gather-methode implementeert:
Hoe emmersortering werkt
Het fundamentele werkingsprincipe van emmersoort is als volgt:
- Er wordt een set lege emmers gemaakt. Op basis van verschillend beleid kan het aantal buckets verschillen.
- Plaats elk element vanuit de invoerarray in de bijbehorende bucket.
- Sorteer die emmers afzonderlijk.
- Voeg de gesorteerde buckets samen om één uitvoerarray te maken.
De gedetailleerde werkstappen worden in de volgende paragrafen beschreven.
Pseudo-code
Start Create N empty buckets For each array element: Calculate bucket index Put that element into the corresponding bucket For each bucket: Sort elements within each bucket Merge all the elements from each bucket Output the sorted array End
Methode 1: Bucket-sorteeralgoritme voor drijvende-komma Numbers
Het bucket-sorteeralgoritme voor drijvendekommagetallen in het bereik van 0.0 tot 1.0:
Stap 1) Maak tien (10) lege buckets, zodat de eerste bucket getallen bevat binnen het bereik [0.0, 0.1]. De tweede bucket zal getallen bevatten binnen [0.1, 0.2), enzovoort.
Stap 2) Voor elk array-element:
-
A. Bereken de bucketindex met behulp van de formule:
bucket index= geen_van_buckets *array_element
-
B. Plaats het element in de bucket[bucket_index]
Stap 3) Sorteer elke emmer afzonderlijk met behulp van invoegsortering.
Stap 4) Voeg alle buckets samen in één array.
Laten we een voorbeeld van bucket sort bekijken. Voor dit voorbeeld sorteren we de volgende array met behulp van het bucket sort-algoritme:
Stap 1) Eerst maken we 10 lege buckets. De eerste bucket bevat de getallen tussen [0.0, 0.1). De tweede bucket bevat de getallen tussen [0.1, 0.2) enzovoort.
Stap 2) Voor elk array-element berekenen we de bucketindex en plaatsen we het element in die bucket.
De bucketindex kan worden berekend met behulp van de formule:
bucket_index= geen_van_buckets*array_element
Berekening van de bucketindex:
a) 0.78
bucket_index = geen_van_buckets*array_element
= * 10 0.78
= 7.8
Het element 0.78 wordt dus opgeslagen op de emmer[vloer(7.8)] of emmer[7].
b) 0.17
bucket_index = no_of_buckets * array-element
= * 10 0.17
= 1.7
Het array-element 0.17 wordt opgeslagen op bucket[floor(1.7)] of bucket[1].
c) 0.39
bucket_index = no_of_buckets * array-element
= 10 * 0.39
= 3.9
0.39 wordt opgeslagen op bucket[floor(3.9)] of bucket[3].
Nadat alle elementen van de array zijn doorlopen, zijn de buckets als volgt:
Stap 3) Vervolgens wordt elke bucket gesorteerd met behulp van insertion sort. Na de sorteerbewerking zou de uitvoer zijn:
Stap 4) In de laatste stap worden de buckets samengevoegd tot één array. Die array zal het gesorteerde resultaat van de invoer zijn.
Elke bucket wordt samengevoegd met de uitvoerarray. Bijvoorbeeld de aaneenschakeling van de tweede bucket-elementen:
De samenvoeging van de laatste bucket-elementen is als volgt:
Na aaneenschakeling zal de resulterende array de gewenste gesorteerde array zijn.
Emmersorteerprogramma in C/C++
Input:
//Bucket Sort Program in C/C++ //For not having integer parts #include <bits/stdc++.h> #define BUCKET_SIZE 10 using namespace std; void bucketSort(float input[], int array_size) { vector <float>bucket[BUCKET_SIZE]; for (int i = 0; i < array_size; i++) { int index = BUCKET_SIZE*input[i]; bucket[index].push_back(input[i]); } for (int i = 0; i < BUCKET_SIZE; i++) sort(bucket[i].begin(), bucket[i].end()); int out_index = 0; for (int i = 0; i < BUCKET_SIZE; i++) for (int j = 0; j < bucket[i].size(); j++) input[out_index++] = bucket[i][j]; } int main() { float input[]={0.78,0.17,0.39,0.26,0.72,0.94,0.21,0.12,0.23,0.69}; int array_size = sizeof(input)/sizeof(input[0]); bucketSort(input, array_size); cout <<"Sorted Output: \n"; for (int i = 0; i< array_size; i++) cout<<input[i]<<" "; return 0; }
Output:
Sorted Output: 0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94
Emmersorteerprogramma in Python
Input:
# Bucket Sort Program in Python # For not having integer parts def bucketSort(input): output = [] bucket_size = 10 for bucket in range(bucket_size): output.append([]) for element in input: index = int(bucket_size * element) output[index].append(element) for bucket in range(bucket_size): output[bucket] = sorted(output[bucket]) out_index = 0 for bucket in range(bucket_size): for element in range(len(output[bucket])): input[out_index] = output[bucket][element] out_index += 1 return input input = [0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.69] print("Sorted Output:") print(bucketSort(input))
Output:
Sorted Output: [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.69, 0.72, 0.78, 0.94]
Emmer Sorteer in Java
Input:
import java.util.ArrayList; import java.util.Collections; import java.util.List; public class BucketSort { private static final int BUCKET_SIZE = 10; public static void bucketSort(float[] input, int arraySize) { List < Float > [] bucket = new ArrayList[BUCKET_SIZE]; for (int i = 0; i < arraySize; i++) { int index = (int)(BUCKET_SIZE * input[i]); if (bucket[index] == null) { bucket[index] = new ArrayList < > (); } bucket[index].add(input[i]); } for (int i = 0; i < BUCKET_SIZE; i++) { if (bucket[i] != null) { Collections.sort(bucket[i]); } } int outIndex = 0; for (int i = 0; i < BUCKET_SIZE; i++) { if (bucket[i] != null) { for (float value: bucket[i]) { input[outIndex++] = value; } } } } public static void main(String[] args) { float[] input = {0.78f,0.17f,0.39f,0.26f,0.72f,0.94f,0.21f,0.12f,0.23f,0.69f}; int arraySize = input.length; bucketSort(input, arraySize); System.out.println("Sorted Output:"); for (int i = 0; i < arraySize; i++) { System.out.print(input[i]+" "); } } }
Output:
Sorted Output: 0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94
Methode 2: Bucket-sorteeralgoritme voor gehele elementen
Het bucket-sorteeralgoritme voor de invoer die getallen bevat buiten het bereik [0.0, 1.0] is een beetje anders dan het vorige algoritme. De stappen die voor dit geval nodig zijn, zijn als volgt:
Stap 1) Zoek de maximale en minimale elementen.
Stap 2) Selecteer het aantal buckets, n, en initialiseer deze buckets als leeg.
Stap 3) Bereken het bereik of de reikwijdte van elke bucket met behulp van de formule:
span = (maximum - minimum)/n
Stap 4) Voor elk array-element:
-
1. Bereken de bucketindex:
bucket_index = (element - minimum)/span
-
2.Plaats het element in bucket[bucket_index]
Stap 5) Sorteer elke emmer met behulp van invoegsortering.
Stap 6) Voeg alle buckets samen in één array.
Laten we een voorbeeld bekijken van dit bucket sort-algoritme. Voor dit voorbeeld sorteren we de volgende array met behulp van het bucket sort-algoritme:
Stap 1) In de eerste stap moeten de maximale en minimale elementen van de gegeven array worden gevonden. Voor dit voorbeeld is het maximum 24 en het minimum 1.
Stap 2) Nu moeten we een aantal lege emmers selecteren, n. In dit voorbeeld nemen we 5 emmers. Vervolgens initialiseren we ze als leeg.
Stap 3) De overspanning van elke emmer moet worden berekend met de volgende formule:
span = (maximum-minimum)/n = (24-1)/5 = 4
;
De eerste bucket bevat dus de getallen binnen het bereik [0, 5). De tweede bucket bevat de getallen binnen [5, 10), enzovoort.
Stap 4) Voor elk array-element berekenen we de bucketindex en plaatsen we het element in die bucket. De bucketindex kan worden berekend met behulp van de formule:
bucket_index = (element - minimum)/span
Berekening van de bucketindex:
-
a) 11bucket_index = (element – minimum)/span
=(11-1)/4
=2
Element 11 wordt dus opgeslagen in emmer[2].
-
b) 9
bucket_index = (element – minimum)/span
=(9-1)/4
=2
Opmerking: Omdat 9 een grenselement is voor bucket[1], moet het worden toegevoegd aan bucket[1] in plaats van te worden toegevoegd aan dezelfde bucket als het vorige element.
Nadat de bewerkingen voor elk element zijn uitgevoerd, zien de buckets er als volgt uit:
Stap 5) Nu wordt elke bucket gesorteerd met behulp van invoegsortering. De emmers na sortering-
Stap 6) In de laatste stap worden de buckets samengevoegd tot één array. Dat reeks zal het gesorteerde resultaat van de invoer zijn.
Emmersorteerprogramma in C/C++
Input:
#include<bits/stdc++.h> using namespace std; void bucketSort(vector < double > & input, int No_Of_Buckets) { double max_value = * max_element(input.begin(), input.end()); double min_value = * min_element(input.begin(), input.end()); double span = (max_value - min_value) / No_Of_Buckets; vector<vector <double>> output; for (int i = 0; i < No_Of_Buckets; i++) output.push_back(vector <double> ()); for (int i = 0; i < input.size(); i++) { double difference = (input[i] - min_value) / span - int((input[i] - min_value) / span); if (difference == 0 && input[i] != min_value) output[int((input[i] - min_value) / span) - 1] .push_back(input[i]); else output[int((input[i] - min_value) / span)].push_back( input[i]); } for (int i = 0; i < output.size(); i++) { if (!output[i].empty()) sort(output[i].begin(), output[i].end()); } int index = 0; for (vector <double> & bucket: output) { if (!bucket.empty()) { for (double i: bucket) { input[index] = i; index++; } } } } int main() { vector <double> input ={11,9,21,8,17,19,13,1,24,12 }; int No_Of_Buckets = 5; bucketSort(input, No_Of_Buckets); cout<< "Sorted Output:"; for (int i; i < input.size(); i++) cout <<input[i]<<" "; return 0; }
Output:
Sorted Output:1 8 9 11 12 13 17 19 21 24
Emmersorteerprogramma in Python
Input:
def bucketSort(input, No_Of_Buckets): max_element = max(input) min_element = min(input) span = (max_element - min_element) / No_Of_Buckets output = [] for bucket in range(No_Of_Buckets): output.append([]) for element in range(len(input)): diff = (input[element] - min_element) / span - int( (input[element] - min_element) / span ) if diff == 0 and input[element] != min_element: output[int((input[element] - min_element) / span) - 1].append( input[element] ) else: output[int((input[element] - min_element) / span)].append(input[element]) for bucket in range(len(output)): if len(output[bucket]) != 0: output[bucket].sort() index = 0 for bucket in output: if bucket: for element in bucket: input[index] = element index = index + 1 input = [11, 9, 21, 8, 17, 19, 13, 1, 24, 12] No_Of_Buckets = 5 bucketSort(input, No_Of_Buckets) print("Sorted Output:\n", input)
Output:
Sorted Output: [1, 8, 9, 11, 12, 13, 17, 19, 21, 24]
Emmer Sorteer in Java
Input:
import java.util.ArrayList; import java.util.Collections; import java.util.List; public class BucketSort { public static void bucketSort(List < Double > input, int No_Of_Buckets) { double max_value = Collections.max(input); double min_value = Collections.min(input); double span =(max_value - min_value) / No_Of_Buckets; List < List < Double > > output = new ArrayList < > (); for (int i = 0; i < No_Of_Buckets; i++) { output.add(new ArrayList < > ()); } for (Double value: input) { double difference = (value - min_value) / span - ((value - min_value) / span); if (difference == 0 && value != min_value) { output.get((int)((value - min_value) / span) - 1).add(value); } else { output.get((int)((value - min_value) / span)).add(value); } } for (List <Double> bucket: output) { if (!bucket.isEmpty()) { Collections.sort(bucket); } } int index = 0; for (List <Double> bucket: output) { if (!bucket.isEmpty()) { for (Double value: bucket) { input.set(index,value); index++; } } } } public static void main(String[] args) { List <Double> input = new ArrayList <> (); input.add(11.0); input.add(9.0); input.add(21.0); input.add(8.0); input.add(17.0); input.add(19.0); input.add(13.0); input.add(1.0); input.add(24.0); input.add(12.0); int No_Of_Buckets = 5; bucketSort(input, No_Of_Buckets); System.out.println("Sorted Output:"); for (Double value: input) { System.out.print(value + " "); } } }
Output:
Sorted Output: 1.0 8.0 9.0 11.0 12.0 13.0 17.0 19.0 21.0 24.0
Voor-en nadelen
VOORDELEN | NADELEN |
---|---|
Voer snellere berekeningen uit | Verbruikt meer ruimte vergeleken met andere algoritmen |
Het kan worden gebruikt als een externe sorteermethode | Presteert slecht als de gegevens niet uniform zijn verdeeld |
Emmers kunnen onafhankelijk worden verwerkt |
Complexiteitsanalyse van bucketsortering
Tijdcomplexiteit van Bucket Sort
- Beste geval complexiteit:Als alle array-elementen vooraf uniform zijn verdeeld en gesorteerd, zou het O(n) tijd nodig hebben om de elementen in de overeenkomstige emmers te verspreiden. Sorteer vervolgens elke emmer met behulp van invoegsoort zou O(k) kosten. De totale complexiteit zou dus O(n+k) zijn.
- Gemiddelde casuscomplexiteit:Voor gemiddelde gevallen nemen we aan dat de invoer gelijkmatig verdeeld is. Het bucket sorting-algoritme bereikt dus een lineaire tijdcomplexiteit van O(n+k). Hier is O(n) tijd nodig om de elementen te verstrooien en O(k) tijd om die elementen te sorteren met behulp van insertion sort.
- Complexiteit in het ergste geval:In het ergste geval zullen de elementen niet gelijkmatig verdeeld en geconcentreerd zijn over één of twee specifieke emmers. In dat geval werkt bucketsortering als een algoritme voor het sorteren van bellen. In het slechtste geval zou de tijdcomplexiteit van een bucket sortering dus O(n^2) zijn.
Ruimtecomplexiteit van emmersortering
De ruimtelijke complexiteit van bucket sort is O(n*k). Hierbij is n het aantal elementen en k het aantal vereiste buckets.