Bucket Sort Algorithm

I denne vejledning lærer du, hvordan skovlsortering fungerer. Du finder også arbejdseksempler på bucket-sortering i C, C ++, Java og Python.

Bucket Sort er en sorteringsteknik, der sorterer elementerne ved først at opdele elementerne i flere grupper kaldet spande . Elementerne inde i hver spand er sorteret ved hjælp af en hvilken som helst af de passende sorteringsalgoritmer eller ved rekursivt at kalde den samme algoritme.

Flere skovle oprettes. Hver spand er fyldt med et specifikt udvalg af elementer. Elementerne inde i skovlen sorteres ved hjælp af en hvilken som helst anden algoritme. Endelig samles elementerne i skovlen for at få det sorterede array.

Processen med spandesortering kan forstås som en scatter-collect- tilgang. Elementerne spredes først i spande, derefter sorteres elementerne i spande. Endelig er elementerne samlet i rækkefølge.

Arbejdet med Bucket Sort

Hvordan fungerer Bucket Sort?

  1. Antag, at input-arrayet er: Input-array
    Opret et array med størrelse 10. Hver slot i dette array bruges som en skovl til lagring af elementer. Matrix, hvor hver position er en spand
  2. Indsæt elementer i skovlene fra arrayet. Elementerne indsættes i henhold til skovlens rækkevidde.
    I vores eksempelkode har vi skovle, der hver er fra 0 til 1, 1 til 2, 2 til 3,… (n-1) til n.
    Antag, at der tages et inputelement .23. Det ganges med size = 10(dvs. .23*10=2.3). Derefter konverteres det til et heltal (dvs. 2.3≈2). Endelig indsættes .23 i spand-2 . Indsæt elementer i skovlene fra arrayet.
    På samme måde indsættes .25 også i den samme skovl. Hver gang tages gulvværdien af ​​det flydende punktummer.
    Hvis vi tager heltal som input, er vi nødt til at dele det med intervallet (10 her) for at få gulvværdien.
    Tilsvarende indsættes andre elementer i deres respektive spande. Indsæt alle elementerne i skovlene fra arrayet
  3. Elementerne i hver skovl sorteres ved hjælp af en hvilken som helst af de stabile sorteringsalgoritmer. Her har vi brugt quicksort (indbygget funktion). Sorter elementerne i hver spand
  4. Elementerne fra hver spand er samlet.
    Det gøres ved at gentage gennem skovlen og indsætte et individuelt element i det originale array i hver cyklus. Elementet fra skovlen slettes, når den er kopieret til den oprindelige matrix. Saml elementer fra hver spand

Bucket Sort Algorithm

 bucketSort () opret N skovle, som hver kan rumme en række værdier for alle skovle initialisere hver skovl med 0 værdier for alle skovle sætte elementer i skovle, der matcher rækkevidden for alle skovle sorteringselementer i hver skovl samle elementer fra hver skovl slutspand Sort

Python, Java og C / C ++ eksempler

Python Java C C ++ 
 # Bucket Sort in Python def bucketSort(array): bucket = () # Create empty buckets for i in range(len(array)): bucket.append(()) # Insert elements into their respective buckets for j in array: index_b = int(10 * j) bucket(index_b).append(j) # Sort the elements of each bucket for i in range(len(array)): bucket(i) = sorted(bucket(i)) # Get the sorted elements k = 0 for i in range(len(array)): for j in range(len(bucket(i))): array(k) = bucket(i)(j) k += 1 return array array = (.42, .32, .33, .52, .37, .47, .51) print("Sorted Array in descending order is") print(bucketSort(array)) 
 // Bucket sort in Java import java.util.ArrayList; import java.util.Collections; public class BucketSort ( public void bucketSort(float() arr, int n) ( if (n <= 0) return; @SuppressWarnings("unchecked") ArrayList() bucket = new ArrayList(n); // Create empty buckets for (int i = 0; i < n; i++) bucket(i) = new ArrayList(); // Add elements into the buckets for (int i = 0; i < n; i++) ( int bucketIndex = (int) arr(i) * n; bucket(bucketIndex).add(arr(i)); ) // Sort the elements of each bucket for (int i = 0; i < n; i++) ( Collections.sort((bucket(i))); ) // Get the sorted array int index = 0; for (int i = 0; i < n; i++) ( for (int j = 0, size = bucket(i).size(); j < size; j++) ( arr(index++) = bucket(i).get(j); ) ) ) // Driver code public static void main(String() args) ( BucketSort b = new BucketSort(); float() arr = ( (float) 0.42, (float) 0.32, (float) 0.33, (float) 0.52, (float) 0.37, (float) 0.47, (float) 0.51 ); b.bucketSort(arr, 7); for (float i : arr) System.out.print(i + " "); ) )
 // Bucket sort in C #include #include #define NARRAY 7 // Array size #define NBUCKET 6 // Number of buckets #define INTERVAL 10 // Each bucket capacity struct Node ( int data; struct Node *next; ); void BucketSort(int arr()); struct Node *InsertionSort(struct Node *list); void print(int arr()); void printBuckets(struct Node *list); int getBucketIndex(int value); // Sorting function void BucketSort(int arr()) ( int i, j; struct Node **buckets; // Create buckets and allocate memory size buckets = (struct Node **)malloc(sizeof(struct Node *) * NBUCKET); // Initialize empty buckets for (i = 0; i < NBUCKET; ++i) ( buckets(i) = NULL; ) // Fill the buckets with respective elements for (i = 0; i data = arr(i); current->next = buckets(pos); buckets(pos) = current; ) // Print the buckets along with their elements for (i = 0; i < NBUCKET; i++) ( printf("Bucket(%d): ", i); printBuckets(buckets(i)); printf(""); ) // Sort the elements of each bucket for (i = 0; i < NBUCKET; ++i) ( buckets(i) = InsertionSort(buckets(i)); ) printf("-------------"); printf("Bucktets after sorting"); for (i = 0; i < NBUCKET; i++) ( printf("Bucket(%d): ", i); printBuckets(buckets(i)); printf(""); ) // Put sorted elements on arr for (j = 0, i = 0; i data; node = node->next; ) ) return; ) // Function to sort the elements of each bucket struct Node *InsertionSort(struct Node *list) ( struct Node *k, *nodeList; if (list == 0 || list->next == 0) ( return list; ) nodeList = list; k = list->next; nodeList->next = 0; while (k != 0) ( struct Node *ptr; if (nodeList->data> k->data) ( struct Node *tmp; tmp = k; k = k->next; tmp->next = nodeList; nodeList = tmp; continue; ) for (ptr = nodeList; ptr->next != 0; ptr = ptr->next) ( if (ptr->next->data> k->data) break; ) if (ptr->next != 0) ( struct Node *tmp; tmp = k; k = k->next; tmp->next = ptr->next; ptr->next = tmp; continue; ) else ( ptr->next = k; k = k->next; ptr->next->next = 0; continue; ) ) return nodeList; ) int getBucketIndex(int value) ( return value / INTERVAL; ) void print(int ar()) ( int i; for (i = 0; i data); cur = cur->next; ) ) // Driver code int main(void) ( int array(NARRAY) = (42, 32, 33, 52, 37, 47, 51); printf("Initial array: "); print(array); printf("-------------"); BucketSort(array); printf("-------------"); printf("Sorted array: "); print(array); return 0; )
 // Bucket sort in C++ #include #include using namespace std; #define NARRAY 7 // Array size #define NBUCKET 6 // Number of buckets #define INTERVAL 10 // Each bucket capacity struct Node ( int data; struct Node *next; ); void BucketSort(int arr()); struct Node *InsertionSort(struct Node *list); void print(int arr()); void printBuckets(struct Node *list); int getBucketIndex(int value); // Sorting function void BucketSort(int arr()) ( int i, j; struct Node **buckets; // Create buckets and allocate memory size buckets = (struct Node **)malloc(sizeof(struct Node *) * NBUCKET); // Initialize empty buckets for (i = 0; i < NBUCKET; ++i) ( buckets(i) = NULL; ) // Fill the buckets with respective elements for (i = 0; i data = arr(i); current->next = buckets(pos); buckets(pos) = current; ) // Print the buckets along with their elements for (i = 0; i < NBUCKET; i++) ( cout << "Bucket(" << i << ") : "; printBuckets(buckets(i)); cout << endl; ) // Sort the elements of each bucket for (i = 0; i < NBUCKET; ++i) ( buckets(i) = InsertionSort(buckets(i)); ) cout << "-------------" << endl; cout << "Bucktets after sorted" << endl; for (i = 0; i < NBUCKET; i++) ( cout << "Bucket(" << i << ") : "; printBuckets(buckets(i)); cout << endl; ) // Put sorted elements on arr for (j = 0, i = 0; i data; node = node->next; ) ) for (i = 0; i next; free(tmp); ) ) free(buckets); return; ) // Function to sort the elements of each bucket struct Node *InsertionSort(struct Node *list) ( struct Node *k, *nodeList; if (list == 0 || list->next == 0) ( return list; ) nodeList = list; k = list->next; nodeList->next = 0; while (k != 0) ( struct Node *ptr; if (nodeList->data> k->data) ( struct Node *tmp; tmp = k; k = k->next; tmp->next = nodeList; nodeList = tmp; continue; ) for (ptr = nodeList; ptr->next != 0; ptr = ptr->next) ( if (ptr->next->data> k->data) break; ) if (ptr->next != 0) ( struct Node *tmp; tmp = k; k = k->next; tmp->next = ptr->next; ptr->next = tmp; continue; ) else ( ptr->next = k; k = k->next; ptr->next->next = 0; continue; ) ) return nodeList; ) int getBucketIndex(int value) ( return value / INTERVAL; ) // Print buckets void print(int ar()) ( int i; for (i = 0; i < NARRAY; ++i) ( cout << setw(3) << ar(i); ) cout << endl; ) void printBuckets(struct Node *list) ( struct Node *cur = list; while (cur) ( cout << setw(3)  next; ) ) // Driver code int main(void) ( int array(NARRAY) = (42, 32, 33, 52, 37, 47, 51); cout << "Initial array: " << endl; print(array); cout << "-------------" << endl; BucketSort(array); cout << "-------------" << endl; cout << "Sorted array: " << endl; print(array); )

Kompleksitet

  • Kompleksitet i værste tilfælde: Når der er elementer af tæt rækkevidde i matrixen, placeres de sandsynligvis i den samme spand. Dette kan resultere i, at nogle skovle har flere antal elementer end andre. Det gør kompleksiteten afhængig af sorteringsalgoritmen, der bruges til at sortere elementerne i skovlen. Kompleksiteten bliver endnu værre, når elementerne er i omvendt rækkefølge. Hvis indsætningssortering bruges til at sortere elementer i skovlen, bliver tidskompleksiteten .O(n2)

    O(n2)
  • Best case-kompleksitet: O(n+k)
    Det sker, når elementerne fordeles ensartet i spande med næsten lige så mange elementer i hver spand.
    Kompleksiteten bliver endnu bedre, hvis elementerne i skovlene allerede er sorteret.
    Hvis indsætningssortering bruges til at sortere elementer i en spand, vil den samlede kompleksitet i bedste fald være lineær, dvs. O(n+k). O(n)er kompleksiteten til fremstilling af skovle og O(k)er kompleksiteten til at sortere skovlens elementer ved hjælp af algoritmer, der i bedste fald har lineær tidskompleksitet.
  • Gennemsnitlig sagskompleksitet: O(n)
    Det opstår, når elementerne fordeles tilfældigt i arrayet. Selvom elementerne ikke er fordelt ensartet, kører skovlesortering lineært. Det gælder indtil summen af ​​firkanterne i skovlstørrelserne er lineær i det samlede antal elementer.

Bucket Sort applikationer

Spandesortering bruges, når:

  • input er jævnt fordelt over et interval.
  • der er flydende punktværdier

Interessante artikler...