Algorithme de tri de seau (Java, Python, C /C++ Exemples de codes)
Sarah Chen
Qu’est-ce que le tri par seau ?
Le tri par compartiment, souvent appelé tri par bac, est une méthode de tri par comparaison qui accepte un tableau non trié comme entrée et produit en conséquence un tableau trié. Cette méthode fonctionne en distribuant les éléments dans plusieurs compartiments et en triant chacun de ces compartiments individuellement par n'importe quel algorithme de tri tel que le tri par insertion. Ensuite, tous les compartiments sont fusionnés pour former un tableau trié.
Le tri par compartiment est couramment utilisé lorsque les éléments sont :
- Valeurs à virgule flottante
- Uniformément réparti sur une plage
La complexité temporelle du tri par compartiments dépend du nombre de compartiments utilisés et de l'uniformité de la distribution des entrées. Alors que différents algorithmes de tri tels que sorte de coquille, fusionner le tri, le tri en tas et tri rapide peut atteindre la complexité temporelle dans le meilleur des cas de O(n*logn), l'algorithme de tri par compartiments peut atteindre la même complexité temporelle linéaire ou O(n).
Le tri par compartiment suit l'approche scatter-gather. En appliquant cette approche, les éléments sont dispersés dans les compartiments correspondants, triés dans les compartiments et rassemblés pour former un tableau trié lors de l'étape finale. Cette approche scatter-gather est discutée dans la section suivante
Approche Dispersion-Rassemblement
Des problèmes complexes et à grande échelle peuvent parfois être difficiles à résoudre. L'approche scatter-gather tente de résoudre de tels problèmes en divisant l'ensemble des données en clusters. Ensuite, chaque cluster est abordé séparément et le tout rassemblé pour obtenir la réponse finale.
Voici comment l'algorithme de tri par bucket implémente la méthode scatter-gather :
Comment fonctionne le tri par compartiment
Le principe de fonctionnement de base du tri par compartiments est le suivant :
- Un ensemble de compartiments vides est créé. En fonction des différentes politiques, le nombre de compartiments peut différer.
- À partir du tableau d'entrée, placez chaque élément dans son compartiment correspondant.
- Triez ces compartiments individuellement.
- Concaténez les compartiments triés pour créer un seul tableau de sortie.
Les étapes de travail détaillées sont fournies dans les sections suivantes.
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
Méthode 1 : algorithme de tri par compartiment pour la virgule flottante Numbers
L'algorithme de tri par compartiment pour les nombres à virgule flottante compris entre 0.0 et 1.0 :
Étape 1) Créez dix (10) compartiments vides de telle sorte que le premier compartiment contienne des nombres compris dans la plage [0.0, 0.1). Ensuite, le deuxième compartiment contiendra [0.1, 0.2), et ainsi de suite.
Étape 2) Pour chaque élément du tableau :
-
un. Calculez l'indice de compartiment à l'aide de la formule :
index du compartiment = no_of_buckets *array_element
-
b. Insérez l'élément dans le bucket[bucket_index]
Étape 3) Triez chaque compartiment individuellement à l’aide du tri par insertion.
Étape 4) Concaténez tous les compartiments dans un seul tableau.
Voyons un exemple de tri par bucket. Pour cet exemple, nous allons trier le tableau suivant à l'aide de l'algorithme de tri par compartiment :
Étape 1) Tout d’abord, nous allons créer 10 buckets vides. Le premier compartiment contiendra les nombres compris entre [0.0, 0.1). Ensuite, le deuxième compartiment contiendra les nombres compris entre [0.1, 0.2) et ainsi de suite.
Étape 2) Pour chaque élément du tableau, nous calculerons l’index du bucket et placerons l’élément dans ce bucket.
L'indice de compartiment peut être calculé à l'aide de la formule :
bucket_index= no_of_buckets*array_element
Calcul de l'indice de compartiment :
a) 0.78
bucket_index = no_of_buckets*array_element
= 10 * 0.78
= 7.8
Par conséquent, l'élément 0.78 sera stocké sur le bucket[floor(7.8)] ou le bucket[7].
b) 0.17
bucket_index = no_of_buckets * élément du tableau
= 10 * 0.17
= 1.7
L'élément de tableau 0.17 sera stocké sur bucket[floor(1.7)] ou bucket[1].
c) 0.39
bucket_index = no_of_buckets * élément du tableau
= 10 * 0.39
= 3.9
0.39 sera stocké sur bucket[floor(3.9)] ou bucket[3].
Après avoir parcouru tous les éléments du tableau, les buckets seront les suivants :
Étape 3) Ensuite, chaque compartiment sera trié à l’aide du tri par insertion. Après l'opération de tri, le résultat serait :
Étape 4) Dans la dernière étape, les buckets seront concaténés en un seul tableau. Ce tableau sera le résultat trié de l’entrée.
Chaque bucket sera concaténé au tableau de sortie. Par exemple, la concaténation des éléments du deuxième bucket :
La concaténation des derniers éléments du bucket sera la suivante :
Après concaténation, le tableau résultant sera le tableau trié souhaité.
Programme de tri de seaux en C/C++
Entrées :
//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;
}
Sortie :
Sorted Output: 0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94
Programme de tri par seau dans Python
Entrées :
# 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))
Sortie :
Sorted Output: [0.12, 0.17, 0.21, 0.23, 0.26, 0.39, 0.69, 0.72, 0.78, 0.94]
Seau Trier dans Java
Entrées :
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]+" ");
}
}
}
Sortie :
Sorted Output: 0.12 0.17 0.21 0.23 0.26 0.39 0.69 0.72 0.78 0.94
Méthode 2 : algorithme de tri par compartiment pour les éléments entiers
L'algorithme de tri par compartiment pour l'entrée contenant des nombres au-delà de la plage [0.0, 1.0] est un peu différent du précédent. algorithme. Les étapes requises pour ce cas sont les suivantes :
Étape 1) Trouvez les éléments maximum et minimum.
Étape 2) Sélectionnez le nombre de compartiments, n, et initialisez ces compartiments comme étant vides.
Étape 3) Calculez la plage ou la portée de chaque compartiment à l'aide de la formule :
span = (maximum - minimum)/n
Étape 4) Pour chaque élément du tableau :
-
1.Calculer l'indice du bucket :
bucket_index = (element - minimum)/span-
2.Insérez l'élément dans le bucket[bucket_index]
Étape 5) Triez chaque compartiment à l’aide du tri par insertion.
Étape 6) Concaténez tous les compartiments dans un seul tableau.
Voyons un exemple de cet algorithme de tri par compartiment. Pour cet exemple, nous allons trier le tableau suivant à l'aide de l'algorithme de tri par compartiment :
Étape 1) Dans la première étape, les éléments maximum et minimum du tableau donné doivent être trouvés. Pour cet exemple, le maximum est 24 et le minimum est 1.
Étape 2) Maintenant, nous devons sélectionner un nombre de compartiments vides, n. Dans cet exemple, nous prendrons 5 seaux. Ensuite nous les initialiserons comme vides.
Étape 3) La portée de chaque compartiment doit être calculée à l'aide de la formule suivante :
span = (maximum-minimum)/n = (24-1)/5 = 4;
Par conséquent, le premier compartiment contiendra les nombres compris dans la plage [0, 5). Le deuxième compartiment contiendra les nombres compris entre [5, 10) et ainsi de suite.
Étape 4) Pour chaque élément du tableau, nous calculerons l’index du bucket et placerons l’élément dans ce bucket. L'indice de compartiment peut être calculé à l'aide de la formule :
bucket_index = (element - minimum)/span
Calcul de l'indice de compartiment :
-
a) 11bucket_index = (élément – minimum)/span
=(11 1-4 )/
=2
Ainsi, l'élément 11 sera stocké dans bucket[2].
-
b) 9
bucket_index = (élément – minimum)/span
=(9 1-4 )/
=2
Remarque: Comme 9 est un élément de limite pour le bucket[1], il doit être ajouté dans bucket[1] au lieu d'être ajouté dans le même bucket de l'élément précédent.
Après avoir effectué les opérations pour chaque élément, les buckets seront les suivants :
Étape 5) Désormais, chaque compartiment sera trié à l’aide du tri par insertion. Les seaux après tri-
Étape 6) Dans la dernière étape, les buckets seront concaténés en un seul tableau. Que tableau sera le résultat trié de l’entrée.
Programme de tri de seaux en C/C++
Entrées :
#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;
}
Sortie :
Sorted Output:1 8 9 11 12 13 17 19 21 24
Programme de tri par seau dans Python
Entrées :
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)
Sortie :
Sorted Output: [1, 8, 9, 11, 12, 13, 17, 19, 21, 24]
Seau Trier dans Java
Entrées :
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 + " ");
}
}
}
Sortie :
Sorted Output: 1.0 8.0 9.0 11.0 12.0 13.0 17.0 19.0 21.0 24.0
Avantages et inconvénients
| Avantages | Inconvénients |
|---|---|
| Effectuer un calcul plus rapide | Consomme plus d'espace par rapport aux autres algorithmes |
| Il peut être utilisé comme méthode de tri externe | Fonctionne mal lorsque les données ne sont pas uniformément réparties |
| Les seaux peuvent être traités indépendamment |
Analyse de la complexité du tri par compartiment
Complexité temporelle du tri par seau
- Meilleur cas de complexité :Si tous les éléments du tableau sont uniformément distribués et triés au préalable, il faudrait un temps O(n) pour disperser les éléments dans les compartiments correspondants. Triez ensuite chaque seau en utilisant tri par insertion coûterait O(k). Ainsi, la complexité globale serait O(n+k).
- Complexité moyenne des cas :Pour les cas moyens, nous supposons que les entrées sont uniformément distribuées. Ainsi, l'algorithme de tri par compartiment atteint une complexité temporelle linéaire de O (n + k). Ici, un temps O(n) est nécessaire pour disperser les éléments et un temps O(k) est nécessaire pour trier ces éléments à l'aide du tri par insertion.
- Pire complexité des cas :Dans le pire des cas, les éléments ne seront pas uniformément répartis et concentrés sur un ou deux seaux spécifiques. Dans ce cas, le tri par compartiment fonctionnera comme un algorithme de tri à bulles. Par conséquent, dans le pire des cas, la complexité temporelle d’un tri par compartiment serait O(n^2).
Complexité spatiale du tri par seau
La complexité spatiale du tri par compartiment est O(n*k). Ici n est le nombre d'éléments et k est le nombre de compartiments requis.