Αλγόριθμος ταξινόμησης κάδου (Java, Python, Γ/C++ Code Παραδείγματα)

Τι είναι το Bucket Sort;

Η ταξινόμηση σε κάδο, που συχνά ονομάζεται και ταξινόμηση σε bin, είναι μια μέθοδος ταξινόμησης με κατανομή που βασίζεται σε σύγκριση και δέχεται έναν μη ταξινομημένο πίνακα ως είσοδο και παράγει έναν ταξινομημένο πίνακα ως έξοδο. Αυτή η τεχνική κατανέμει τα στοιχεία σε διάφορους κάδους και ταξινομεί κάθε κάδο ξεχωριστά χρησιμοποιώντας έναν άλλο αλγόριθμο ταξινόμησης, όπως η ταξινόμηση με εισαγωγή. Στη συνέχεια, όλοι οι κάδοι συγχωνεύονται για να σχηματίσουν τον τελικό ταξινομημένο πίνακα.

Η ταξινόμηση κάδου χρησιμοποιείται συνήθως όταν τα στοιχεία είναι:

1. Τιμές κινητής υποδιαστολής
2. Ομοιόμορφα κατανεμημένο σε ένα γνωστό εύρος

Η χρονική πολυπλοκότητα της Ταξινόμησης σε Κάδους εξαρτάται από τον αριθμό των κάδου που χρησιμοποιούνται και την ομοιομορφία της κατανομής εισόδου. Ενώ άλλοι αλγόριθμοι ταξινόμησης, όπως π.χ. είδος κελύφους, συγχώνευση ταξινόμησης, ομαδικής ταξινόμησης και γρήγορη ταξινόμηση Για να επιτευχθεί η βέλτιστη χρονική πολυπλοκότητα O(n*logn), ο αλγόριθμος Bucket Sort μπορεί να φτάσει στη γραμμική χρονική πολυπλοκότητα O(n) υπό ευνοϊκές συνθήκες.

Η ταξινόμηση σε κάδους ακολουθεί την προσέγγιση scatter-gather. Τα στοιχεία διασκορπίζονται σε αντίστοιχους κάδους, ταξινομούνται μέσα σε κάθε κάδο και συγκεντρώνονται για να σχηματίσουν έναν ταξινομημένο πίνακα ως τελικό βήμα. Αυτή η προσέγγιση scatter-gather συζητείται στην επόμενη ενότητα.

Προσέγγιση Scatter-Gather

Η άμεση επίλυση προβλημάτων μεγάλης κλίμακας και σύνθετων προβλημάτων μπορεί περιστασιακά να είναι δύσκολη. Η προσέγγιση scatter-gather αντιμετωπίζει τέτοια προβλήματα διαιρώντας ολόκληρο το σύνολο δεδομένων σε συστάδες. Κάθε συστάδα υποβάλλεται σε ξεχωριστή επεξεργασία και τα αποτελέσματα συνδυάζονται για να παραχθεί η τελική απάντηση.

Δείτε πώς ο αλγόριθμος Bucket Sort υλοποιεί τη μέθοδο scatter-gather:

Πώς λειτουργεί η ταξινόμηση κάδου

Η βασική αρχή λειτουργίας της ταξινόμησης κάδου έχει ως εξής:

1. Δημιουργείται ένα σύνολο κενών κάδων. Ανάλογα με την επιλεγμένη πολιτική, ο αριθμός των κάδων μπορεί να διαφέρει.
2. Από τον πίνακα εισόδου, κάθε στοιχείο τοποθετείται στον αντίστοιχο κάδο του.
3. Κάθε κάδος ταξινομείται ξεχωριστά χρησιμοποιώντας έναν δευτερεύοντα αλγόριθμο ταξινόμησης.
4. Οι ταξινομημένοι κάδοι συνενώνονται για να παράγουν έναν ενιαίο πίνακα εξόδου.

Παρατσούκλι 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

Μέθοδος 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[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 αποθηκεύεται στο bucket[floor(7.8)] ή στο bucket[7].

β) 0.17
      bucket_index = no_of_buckets * array_element
              = 10 * 0.17
              = 1.7

Το στοιχείο πίνακα 0.17 αποθηκεύεται στο bucket[floor(1.7)] ή στο bucket[1].

γ) 0.39
      bucket_index = no_of_buckets * array_element
              = 10 * 0.39
              = 3.9
Το 0.39 αποθηκεύεται σε bucket[floor(3.9)] ή bucket[3].

Μετά την επανάληψη όλων των στοιχείων του πίνακα, οι κάδοι μοιάζουν ως εξής:

Βήμα 3) Κάθε κάδος ταξινομείται στη συνέχεια χρησιμοποιώντας την ταξινόμηση με εισαγωγή. Μετά τη λειτουργία ταξινόμησης, η έξοδος είναι:

Βήμα 4) Στο τελικό βήμα, οι κάδοι συνενώνονται σε έναν μόνο πίνακα. Αυτός ο πίνακας είναι το ταξινομημένο αποτέλεσμα της εισόδου.

Κάθε κάδος συνενώνεται με τον πίνακα εξόδου. Για παράδειγμα, η συνένωση των στοιχείων του δεύτερου κάδου:

Η συνένωση των τελευταίων στοιχείων του κάδου φαίνεται παρακάτω:

Μετά τη συνένωση, ο πίνακας που προκύπτει είναι ο επιθυμητός ταξινομημένος πίνακας.

Πρόγραμμα ταξινόμησης κάδου σε C/C++

εισόδου:

//Bucket Sort Program in C/C++
//For values without 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: 
";
  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 values without 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[bucket_index]

Βήμα 5) Ταξινομήστε κάθε κάδο χρησιμοποιώντας ταξινόμηση εισαγωγής.

Βήμα 6) Συνδέστε όλους τους κάδους σε έναν ενιαίο πίνακα.

Ας δούμε ένα παράδειγμα αυτού του αλγορίθμου Bucket Sort. Για αυτό το παράδειγμα, θα ταξινομήσουμε τον ακόλουθο πίνακα:

Βήμα 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

Υπολογισμός δείκτη κάδου:

α) 11
bucket_index = (στοιχείο – ελάχιστο) / span
        = (11 – 1) / 4
        = 2

Έτσι, το στοιχείο 11 αποθηκεύεται στον κάδο[2].

β) 9
bucket_index = (στοιχείο – ελάχιστο) / span
        = (9 – 1) / 4
        = 2

Σημείωση: Καθώς το 9 είναι ένα στοιχείο ορίου για το bucket[1], προστίθεται στο bucket[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=0; 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:
", 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

Πλεονεκτήματα και μειονεκτήματα της ταξινόμησης με κουβά

Ανάλυση πολυπλοκότητας ταξινόμησης κάδου

Χρονική πολυπλοκότητα ταξινόμησης κάδου

• Καλυτερα Case Complexity: Εάν όλα τα στοιχεία του πίνακα είναι ομοιόμορφα κατανεμημένα και προταξινομημένα μέσα σε κάθε κάδο, απαιτείται χρόνος O(n) για να διασκορπιστούν τα στοιχεία στους αντίστοιχους κάδους. Στη συνέχεια, ταξινομείται κάθε κάδος χρησιμοποιώντας είδος εισαγωγής κοστίζει O(k). Έτσι, η συνολική πολυπλοκότητα είναι O(n+k).
• Μέση πολυπλοκότητα υπόθεσης: Για μέσες περιπτώσεις, υποθέτουμε ότι οι είσοδοι είναι ομοιόμορφα κατανεμημένες. Έτσι, ο αλγόριθμος ταξινόμησης κάδου επιτυγχάνει μια γραμμική χρονική πολυπλοκότητα O(n+k). Εδώ, απαιτείται χρόνος O(n) για τη διασπορά των στοιχείων και χρόνος O(k) για την ταξινόμησή τους χρησιμοποιώντας ταξινόμηση εισαγωγής.
• Η χειρότερη πολυπλοκότητα της υπόθεσης: Στη χειρότερη περίπτωση, τα στοιχεία δεν κατανέμονται ομοιόμορφα και συγκεντρώνονται σε έναν ή δύο κάδους. Σε αυτήν την περίπτωση, η ταξινόμηση κάδου υποβαθμίζεται σε συμπεριφορά παρόμοια με ένα αλγόριθμος ταξινόμησης φυσαλίδωνΕπομένως, στη χειρότερη περίπτωση, η χρονική πολυπλοκότητα της Ταξινόμησης Κάδου είναι O(n²).

Διαστημική πολυπλοκότητα ταξινόμησης κάδου

Η πολυπλοκότητα χώρου της Ταξινόμησης Κάδου είναι O(n*k). Εδώ, n είναι ο αριθμός των στοιχείων και k είναι ο αριθμός των κάδων που απαιτούνται για να τα χωρέσουν κατά την ταξινόμηση.

Συχνές Ερωτήσεις