Tri par compartiment en Java

1. Introduction

Dans cet article, nous allons plonger dans l' algorithme de tri par compartiment. Nous allons commencer par un petit peu de théorie, avant de travailler sur l'implémentation Java en parallèle des tests unitaires de notre solution. Enfin, nous examinerons la complexité temporelle du tri par compartiment.

2. La théorie du tri par godets

Le tri par godets, parfois appelé tri par bac, est un algorithme de tri spécifique. Le tri fonctionne en distribuant les éléments que nous voulons trier dans plusieurs seaux triés individuellement. En faisant cela, nous pouvons réduire le nombre de comparaisons entre les éléments et aider à réduire le temps de tri.

Jetons un coup d'œil aux étapes nécessaires pour effectuer un tri par compartiment :

  1. Configurer un tableau de nos seaux initialement vides
  2. Distribuez nos éléments dans leurs seaux appropriés
  3. Trier chaque seau
  4. Concaténer les buckets triés ensemble pour recréer la liste complète

3. Implémentation Java

Bien que cet algorithme ne soit pas spécifique au langage, nous implémenterons le tri en Java. Passons en revue la liste ci-dessus étape par étape et écrivons le code pour trier une liste d'entiers.

3.1. Configuration du godet

Tout d'abord, nous devons déterminer un algorithme de hachage pour décider lequel de nos éléments est placé dans quel compartiment:

private int hash(int i, int max, int numberOfBuckets) { return (int) ((double) i / max * (numberOfBuckets - 1)); }

Avec notre méthode de hachage définie, nous pouvons maintenant spécifier le nombre de bins comme une racine carrée de la taille de la liste d'entrée :

final int numberOfBuckets = (int) Math.sqrt(initialList.size()); List
    
      buckets = new ArrayList(numberOfBuckets); for(int i = 0; i < numberOfBuckets; i++) { buckets.add(new ArrayList()); }
    

Enfin, nous avons besoin d'une méthode courte pour déterminer l'entier maximum dans notre liste d'entrée:

private int findMax(List input) { int m = Integer.MIN_VALUE; for (int i : input) { m = Math.max(i, m); } return m; }

3.2. Distribuer les éléments

Maintenant que nos buckets sont définis, nous pouvons distribuer chaque élément de notre liste d'entrée dans son bucket approprié en utilisant la méthode de hachage :

int max = findMax(initialList); for (int i : initialList) { buckets.get(hash(i, max, numberOfBuckets)).add(i); } 

3.3. Tri des godets individuels

Avec nos buckets définis et pleins d'entiers, utilisons un comparateur pour les trier :

Comparator comparator = Comparator.naturalOrder(); for(List bucket : buckets){ bucket.sort(comparator); }

3.4. Concaténation de nos seaux

Enfin, nous devons rassembler nos seaux pour recréer la liste unique. Puisque nos buckets sont triés, nous n'avons besoin de parcourir chaque bucket qu'une seule fois et d'ajouter les éléments à une liste principale:

List sortedArray = new LinkedList(); for(List bucket : buckets) { sortedArray.addAll(bucket); } return sortedArray;

4. Tester notre code

Une fois notre implémentation terminée, écrivons un test unitaire rapide pour nous assurer qu'il fonctionne comme prévu:

BucketSorter sorter = new IntegerBucketSorter(); List unsorted = Arrays.asList(80,50,60,30,20,10,70,0,40,500,600,602,200,15); List expected = Arrays.asList(0,10,15,20,30,40,50,60,70,80,200,500,600,602); List sorted = sorter.sort(unsorted); assertEquals(expected, sorted);

5. Complexité temporelle

Ensuite, examinons rapidement la complexité temporelle de l'exécution d'un tri par compartiment.

5.1. Pire scénario

Dans notre pire scénario, nous trouverions tous nos éléments dans le même seau et dans l'ordre inverse. Lorsque ce cas se produit, nous réduisons notre tri par compartiment à un tri simple dans lequel chaque élément est comparé à tous les autres éléments, ce qui donne une complexité temporelle de O (n²) .

5.2. Scénario de cas moyen

Dans notre cas moyen, nous constatons que les éléments sont relativement uniformément répartis entre nos compartiments d'entrée. Étant donné que chacune de nos étapes ne nécessite qu'une seule itération dans nos compartiments d'entrée, nous constatons que notre tri de compartiment se termine en temps O (n) .

6. Conclusion

Dans cet article, nous avons vu comment implémenter un tri par compartiment en Java. Nous avons également examiné la complexité temporelle de l'algorithme de tri par compartiment.

Comme toujours, le code affiché dans cet article est disponible à l'adresse over sur GitHub.