Αλγόριθμος ταξινόμησης κάδου (Java, Python, Γ/C++ Παραδείγματα κωδικών)
Σάρα Τσεν
Τι είναι το Bucket Sort;
Η ταξινόμηση κάδου, που συχνά ονομάζεται ταξινόμηση bin, είναι μια μέθοδος σύγκρισης ταξινόμησης που δέχεται έναν μη ταξινομημένο πίνακα ως είσοδο και παράγει έναν ταξινομημένο πίνακα ως αποτέλεσμα. Αυτή η μέθοδος λειτουργεί κατανέμοντας τα στοιχεία σε πολλούς κάδους και ταξινομώντας κάθε έναν από αυτούς τους κάδους ξεχωριστά με οποιονδήποτε αλγόριθμο ταξινόμησης, όπως η ταξινόμηση εισαγωγής. Στη συνέχεια, όλοι οι κάδοι συγχωνεύονται για να σχηματίσουν έναν ταξινομημένο πίνακα.
Η ταξινόμηση κάδου χρησιμοποιείται συνήθως όταν τα στοιχεία είναι-
- Τιμές κινητής υποδιαστολής
- Ομοιόμορφα κατανεμημένο σε ένα εύρος
Η χρονική πολυπλοκότητα της ταξινόμησης κάδου εξαρτάται από τον αριθμό των κάδων που χρησιμοποιούνται και την ομοιομορφία της κατανομής εισόδου. Ενώ διαφορετικοί αλγόριθμοι ταξινόμησης όπως π.χ είδος κελύφους, συγχώνευση ταξινόμησης, ομαδικής ταξινόμησης και γρήγορη ταξινόμηση μπορεί να επιτύχει τη χρονική πολυπλοκότητα στην καλύτερη περίπτωση του O(n*logn), ο αλγόριθμος ταξινόμησης κάδου μπορεί να επιτύχει το ίδιο σε γραμμική χρονική πολυπλοκότητα ή O(n).
Η ταξινόμηση με κάδο ακολουθεί την προσέγγιση του scatter-gather. Εφαρμόζοντας αυτή την προσέγγιση, τα στοιχεία διασκορπίζονται στους αντίστοιχους κάδους, ταξινομούνται στους κάδους και συγκεντρώνονται για να σχηματίσουν έναν ταξινομημένο πίνακα ως το τελικό βήμα. Αυτή η προσέγγιση διασποράς-συσσώρευσης συζητείται στην επόμενη ενότητα
Σκορπίζω-Συγκεντρώνω-Προσέγγιση
Μεγάλης κλίμακας, σύνθετα προβλήματα μπορεί περιστασιακά να είναι δύσκολο να λυθούν. Η προσέγγιση scatter-gather επιχειρεί να λύσει τέτοια προβλήματα διαιρώντας ολόκληρο το σύνολο δεδομένων σε συστάδες. Στη συνέχεια, κάθε σύμπλεγμα αντιμετωπίζεται ξεχωριστά και συγκεντρώνει τα πάντα για να ληφθεί η τελική απάντηση.
Αυτός είναι ο τρόπος με τον οποίο ο αλγόριθμος ταξινόμησης κάδου εφαρμόζει τη μέθοδο scatter-gather:
Πώς λειτουργεί η ταξινόμηση κάδου
Η βασική αρχή λειτουργίας της ταξινόμησης με κάδο είναι η εξής:
- Δημιουργείται ένα σύνολο κενών κάδων. Με βάση διαφορετικές πολιτικές, ο αριθμός των κουβάδων μπορεί να διαφέρει.
- Από τον πίνακα εισόδου, τοποθετήστε κάθε στοιχείο στον αντίστοιχο κάδο του.
- Ταξινομήστε αυτούς τους κάδους ξεχωριστά.
- Συνδέστε τους ταξινομημένους κάδους για να δημιουργήσετε έναν ενιαίο πίνακα εξόδου.
Τα αναλυτικά βήματα εργασίας παρέχονται στις ακόλουθες ενότητες.
Ψευδοκώδικας
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
Μέθοδος 1: Αλγόριθμος ταξινόμησης κάδου για κινητή υποδιαστολή Numbers
Ο αλγόριθμος ταξινόμησης κάδου για αριθμούς κινητής υποδιαστολής εντός του εύρους από 0.0 έως 1.0:
Βήμα 1) Δημιουργήστε δέκα (10) άδειους κάδους έτσι ώστε ο πρώτος κάδος να περιέχει αριθμούς εντός του εύρους [0.0, 0.1). Τότε ο δεύτερος κάδος θα περιέχει εντός [0.1, 0.2) και ούτω καθεξής.
Βήμα 2) Για κάθε στοιχείο πίνακα:
-
ένα. Υπολογίστε τον δείκτη κάδου χρησιμοποιώντας τον τύπο:
bucket index= no_of_buckets *array_element
-
σι. Εισαγάγετε το στοιχείο στον κάδο[bucket_index]
Βήμα 3) Ταξινομήστε κάθε κάδο ξεχωριστά χρησιμοποιώντας ταξινόμηση εισαγωγής.
Βήμα 4) Συνδέστε όλους τους κάδους σε έναν ενιαίο πίνακα.
Ας δούμε ένα παράδειγμα ταξινόμησης κάδου. Για αυτό το παράδειγμα, θα ταξινομήσουμε τον ακόλουθο πίνακα χρησιμοποιώντας τον αλγόριθμο ταξινόμησης κάδου-
Βήμα 1) Αρχικά, θα δημιουργήσουμε 10 άδειους κάδους. Ο πρώτος κάδος θα περιέχει τους αριθμούς μεταξύ [0.0, 0.1). Στη συνέχεια, ο δεύτερος κάδος θα περιέχει τους αριθμούς μεταξύ [0.1, 0.2) και ούτω καθεξής.
Βήμα 2) Για κάθε στοιχείο πίνακα, θα υπολογίσουμε τον δείκτη του κάδου και θα τοποθετήσουμε το στοιχείο σε αυτόν τον κάδο.
Ο δείκτης του κάδου μπορεί να υπολογιστεί χρησιμοποιώντας τον τύπο:
bucket_index= no_of_buckets*array_element
Υπολογισμός δείκτη κάδου:
α) 0.78
bucket_index = no_of_buckets*array_element
= 10 * 0.78
= 7.8
Επομένως, το στοιχείο 0.78 θα αποθηκευτεί στον κάδο[floor(7.8)] ή στον κάδο[7].
β) 0.17
bucket_index = no_of_buckets * στοιχείο πίνακα
= 10 * 0.17
= 1.7
Το στοιχείο πίνακα 0.17 θα αποθηκευτεί σε bucket[floor(1.7)] ή bucket[1].
γ) 0.39
bucket_index = no_of_buckets * στοιχείο πίνακα
= 10 * 0.39
= 3.9
Το 0.39 θα αποθηκευτεί σε bucket[floor(3.9)] ή bucket[3].
Μετά την επανάληψη όλων των στοιχείων πίνακα, οι κάδοι θα είναι οι εξής:
Βήμα 3) Στη συνέχεια, κάθε κάδος θα ταξινομηθεί χρησιμοποιώντας ταξινόμηση εισαγωγής. Μετά τη λειτουργία ταξινόμησης, η έξοδος θα είναι:
Βήμα 4) Στο τελευταίο βήμα, οι κάδοι θα ενωθούν σε μια ενιαία διάταξη. Αυτός ο πίνακας θα είναι το ταξινομημένο αποτέλεσμα της εισόδου.
Κάθε κάδος θα ενωθεί με τον πίνακα εξόδου. Για παράδειγμα, η συνένωση των στοιχείων του δεύτερου κάδου:
Η συνένωση των στοιχείων του τελευταίου κάδου θα είναι η εξής:
Μετά τη συνένωση, ο πίνακας που προκύπτει θα είναι ο επιθυμητός ταξινομημένος πίνακας.
Πρόγραμμα ταξινόμησης κάδου σε C/C++
εισόδου:
//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;
}
Παραγωγή:
Sorted Output: 0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94
Πρόγραμμα ταξινόμησης κάδου σε Python
εισόδου:
# 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))
Παραγωγή:
Sorted Output: [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.69, 0.72, 0.78, 0.94]
Κάδος Ταξινόμηση Java
εισόδου:
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]+" ");
}
}
}
Παραγωγή:
Sorted Output: 0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94
Μέθοδος 2: Αλγόριθμος ταξινόμησης κάδου για ακέραια στοιχεία
Ο αλγόριθμος ταξινόμησης κάδου για την είσοδο που περιέχει αριθμούς πέρα από το εύρος [0.0, 1.0] είναι λίγο διαφορετικός από τον προηγούμενο αλγόριθμος. Τα βήματα που απαιτούνται για αυτή την περίπτωση είναι τα εξής:
Βήμα 1) Βρείτε τα μέγιστα και τα ελάχιστα στοιχεία.
Βήμα 2) Επιλέξτε τον αριθμό των κάδων, n, και αρχικοποιήστε αυτούς τους κάδους ως κενούς.
Βήμα 3) Υπολογίστε το εύρος ή το εύρος κάθε κάδου χρησιμοποιώντας τον τύπο:
span = (maximum - minimum)/n
Βήμα 4) Για κάθε στοιχείο πίνακα:
-
1.Υπολογισμός δείκτη κάδου:
bucket_index = (element - minimum)/span-
2. Εισαγάγετε το στοιχείο στον κάδο[bucket_index]
Βήμα 5) Ταξινομήστε κάθε κάδο χρησιμοποιώντας ταξινόμηση εισαγωγής.
Βήμα 6) Συνδέστε όλους τους κάδους σε έναν ενιαίο πίνακα.
Ας δούμε ένα παράδειγμα αυτού του αλγορίθμου ταξινόμησης κάδου. Για αυτό το παράδειγμα, θα ταξινομήσουμε τον ακόλουθο πίνακα χρησιμοποιώντας τον αλγόριθμο ταξινόμησης κάδου-
Βήμα 1) Στο πρώτο βήμα, πρέπει να βρεθούν τα μέγιστα και τα ελάχιστα στοιχεία του δεδομένου πίνακα. Για αυτό το παράδειγμα, το μέγιστο είναι 24 και το ελάχιστο είναι 1.
Βήμα 2) Τώρα, πρέπει να επιλέξουμε έναν αριθμό κενών κάδων, n. Σε αυτό το παράδειγμα, θα πάρουμε 5 κουβάδες. Στη συνέχεια θα τα αρχικοποιήσουμε ως άδεια.
Βήμα 3) Το άνοιγμα κάθε κάδου πρέπει να υπολογιστεί με τον ακόλουθο τύπο:
span = (maximum-minimum)/n = (24-1)/5 = 4;
Ως εκ τούτου, ο πρώτος κάδος θα περιέχει τους αριθμούς εντός του εύρους [0, 5). Ο δεύτερος κάδος θα περιέχει τους αριθμούς εντός του [5, 10) και ούτω καθεξής.
Βήμα 4) Για κάθε στοιχείο πίνακα, θα υπολογίσουμε τον δείκτη του κάδου και θα τοποθετήσουμε το στοιχείο σε αυτόν τον κάδο. Ο δείκτης του κάδου μπορεί να υπολογιστεί χρησιμοποιώντας τον τύπο:
bucket_index = (element - minimum)/span
Υπολογισμός δείκτη κάδου:
-
α) 11bucket_index = (στοιχείο – ελάχιστο)/span
=(11-1)/4
=2
Έτσι, το στοιχείο 11 θα αποθηκευτεί στον κάδο[2].
-
β) 9
bucket_index = (στοιχείο – ελάχιστο)/span
=(9-1)/4
=2
Σημείωση: Καθώς το 9 είναι ένα οριακό στοιχείο για τον κάδο[1], πρέπει να προσαρτηθεί στον κάδο[1] αντί να προσαρτηθεί στον ίδιο κάδο του προηγούμενου στοιχείου.
Μετά την εκτέλεση των πράξεων για κάθε στοιχείο, οι κάδοι θα είναι οι εξής:
Βήμα 5) Τώρα, κάθε κάδος θα ταξινομηθεί χρησιμοποιώντας ταξινόμηση εισαγωγής. Οι κάδοι μετά τη διαλογή-
Βήμα 6) Στο τελευταίο βήμα, οι κάδοι θα ενωθούν σε μια ενιαία διάταξη. Οτι παράταξη θα είναι το ταξινομημένο αποτέλεσμα της εισαγωγής.
Πρόγραμμα ταξινόμησης κάδου σε C/C++
εισόδου:
#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;
}
Παραγωγή:
Sorted Output:1 8 9 11 12 13 17 19 21 24
Πρόγραμμα ταξινόμησης κάδου σε Python
εισόδου:
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)
Παραγωγή:
Sorted Output: [1, 8, 9, 11, 12, 13, 17, 19, 21, 24]
Κάδος Ταξινόμηση Java
εισόδου:
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 + " ");
}
}
}
Παραγωγή:
Sorted Output: 1.0 8.0 9.0 11.0 12.0 13.0 17.0 19.0 21.0 24.0
Πλεονεκτήματα μειονεκτήματα
| ΥΠΕΡ | ΚΑΤΑ |
|---|---|
| Εκτελέστε ταχύτερους υπολογισμούς | Καταναλώνει περισσότερο χώρο σε σύγκριση με άλλους αλγόριθμους |
| Μπορεί να χρησιμοποιηθεί ως μέθοδος εξωτερικής ταξινόμησης | Έχει κακή απόδοση όταν τα δεδομένα δεν είναι ομοιόμορφα κατανεμημένα |
| Οι κάδοι μπορούν να υποβληθούν σε επεξεργασία ανεξάρτητα |
Ανάλυση πολυπλοκότητας ταξινόμησης κάδου
Χρονική πολυπλοκότητα του Bucket Sort
- Καλυτερα Case Complexity:Εάν όλα τα στοιχεία του πίνακα είναι ομοιόμορφα κατανεμημένα και ταξινομημένα εκ των προτέρων, θα χρειαστεί χρόνος O(n) για να διασκορπιστούν τα στοιχεία στους αντίστοιχους κάδους. Στη συνέχεια ταξινομήστε κάθε κουβά χρησιμοποιώντας είδος εισαγωγής θα κόστιζε O(k). Έτσι η συνολική πολυπλοκότητα θα ήταν O(n+k).
- Μέση πολυπλοκότητα υπόθεσης:Για τις μέσες περιπτώσεις, υποθέτουμε ότι οι εισροές είναι ομοιόμορφα κατανεμημένες. Έτσι ο αλγόριθμος ταξινόμησης κάδου επιτυγχάνει γραμμική χρονική πολυπλοκότητα O(n+k). Εδώ απαιτείται χρόνος O(n) για τη διασπορά των στοιχείων και χρόνος O(k) απαιτείται για την ταξινόμηση αυτών των στοιχείων χρησιμοποιώντας ταξινόμηση εισαγωγής.
- Η χειρότερη πολυπλοκότητα της υπόθεσης:Στη χειρότερη περίπτωση, τα στοιχεία δεν θα είναι ομοιόμορφα κατανεμημένα και συγκεντρωμένα σε έναν ή δύο συγκεκριμένους κάδους. Σε αυτήν την περίπτωση, η ταξινόμηση με κάδο θα λειτουργήσει ως α αλγόριθμος ταξινόμησης φυσαλίδων. Ως εκ τούτου, στη χειρότερη περίπτωση, η χρονική πολυπλοκότητα μιας ταξινόμησης κάδου θα ήταν O(n^2).
Διαστημική πολυπλοκότητα ταξινόμησης κάδου
Η πολυπλοκότητα του χώρου ταξινόμησης κάδου είναι O(n*k). Εδώ n είναι ο αριθμός των στοιχείων και k είναι ο αριθμός των κάδων που απαιτούνται.
