Algorithme de tri par compartiment

Dans ce didacticiel, vous apprendrez comment fonctionne le tri par compartiment. En outre, vous trouverez des exemples fonctionnels de tri par compartiment en C, C ++, Java et Python.

Bucket Sort est une technique de tri qui trie les éléments en divisant d'abord les éléments en plusieurs groupes appelés buckets . Les éléments à l'intérieur de chaque compartiment sont triés à l'aide de l'un des algorithmes de tri appropriés ou en appelant récursivement le même algorithme.

Plusieurs buckets sont créés. Chaque seau est rempli d'une gamme spécifique d'éléments. Les éléments à l'intérieur du compartiment sont triés à l'aide de n'importe quel autre algorithme. Enfin, les éléments du bucket sont rassemblés pour obtenir le tableau trié.

Le processus de tri par seau peut être compris comme une approche par dispersion . Les éléments sont d'abord dispersés dans des seaux puis les éléments des seaux sont triés. Enfin, les éléments sont rassemblés dans l'ordre.

Fonctionnement du tri de godets

Comment fonctionne le tri par compartiment?

Supposons que le tableau d'entrée soit: Tableau d'entrée
Créez un tableau de taille 10. Chaque emplacement de ce tableau est utilisé comme compartiment pour stocker des éléments. Tableau dans lequel chaque position est un compartiment
Insérez des éléments dans les buckets à partir du tableau. Les éléments sont insérés en fonction de la portée du godet.
Dans notre exemple de code, nous avons des compartiments dont chacun est compris entre 0 et 1, 1 à 2, 2 à 3,… (n-1) à n.
Supposons qu'un élément d'entrée .23soit pris. Il est multiplié par size = 10(ie. .23*10=2.3). Ensuite, il est converti en un entier (c'est-à-dire 2.3≈2). Enfin, .23 est inséré dans le seau-2 . Insérer des éléments dans les compartiments du tableau
De même, .25 est également inséré dans le même compartiment. À chaque fois, la valeur plancher du nombre à virgule flottante est prise.
Si nous prenons des nombres entiers en entrée, nous devons le diviser par l'intervalle (10 ici) pour obtenir la valeur plancher.
De même, d'autres éléments sont insérés dans leurs seaux respectifs. Insérez tous les éléments dans les seaux du tableau
Les éléments de chaque compartiment sont triés à l'aide de l'un des algorithmes de tri stables. Ici, nous avons utilisé quicksort (fonction intégrée). Trier les éléments dans chaque seau
Les éléments de chaque seau sont rassemblés.
Cela se fait en itérant dans le seau et en insérant un élément individuel dans le tableau d'origine à chaque cycle. L'élément du compartiment est effacé une fois copié dans le tableau d'origine. Rassemblez les éléments de chaque seau

Algorithme de tri par compartiment

 bucketSort () crée N buckets dont chacun peut contenir une plage de valeurs pour tous les buckets initialiser chaque bucket avec 0 valeurs pour tous les buckets mettre les éléments dans des buckets correspondant à la plage de tous les buckets trier les éléments dans chaque bucket rassembler les éléments de chaque bucket seau d'extrémité

Exemples Python, Java et C / C ++

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); )

Complexité

Pire complexité des cas: lorsqu'il y a des éléments de proximité dans le tableau, ils sont susceptibles d'être placés dans le même compartiment. Cela peut avoir pour résultat que certains compartiments contiennent plus d'éléments que d'autres. Cela fait dépendre la complexité de l'algorithme de tri utilisé pour trier les éléments du bucket. La complexité devient encore pire lorsque les éléments sont dans l'ordre inverse. Si le tri par insertion est utilisé pour trier les éléments du compartiment, la complexité temporelle devient .O(n²)

O(n²)
Meilleure complexité des cas: O(n+k)
cela se produit lorsque les éléments sont uniformément répartis dans les compartiments avec un nombre presque égal d'éléments dans chaque compartiment.
La complexité devient encore meilleure si les éléments à l'intérieur des seaux sont déjà triés.
Si le tri par insertion est utilisé pour trier les éléments d'un bucket, la complexité globale dans le meilleur des cas sera linéaire, c'est-à-dire. O(n+k). O(n)est la complexité pour faire les seaux et O(k)est la complexité pour trier les éléments du seau à l'aide d'algorithmes ayant une complexité temporelle linéaire dans le meilleur des cas.
Complexité moyenne des cas: O(n)
elle se produit lorsque les éléments sont distribués de manière aléatoire dans le tableau. Même si les éléments ne sont pas répartis uniformément, le tri par compartiment s'exécute en temps linéaire. Cela reste vrai jusqu'à ce que la somme des carrés des tailles de compartiment soit linéaire dans le nombre total d'éléments.