Partitionnement et tri de tableaux avec de nombreuses entrées répétées avec des exemples Java

1. Vue d'ensemble

La complexité d'exécution des algorithmes dépend souvent de la nature de l'entrée.

Dans ce tutoriel, nous verrons comment l' implémentation triviale de l'algorithme Quicksort a de mauvaises performances pour les éléments répétés .

En outre, nous allons apprendre quelques variantes de tri rapide pour partitionner et trier efficacement les entrées avec une haute densité de clés en double.

2. Trivial Quicksort

Quicksort est un algorithme de tri efficace basé sur le paradigme diviser pour conquérir. D'un point de vue fonctionnel, il fonctionne en place sur le tableau d'entrée et réorganise les éléments avec de simples opérations de comparaison et d'échange .

2.1. Partitionnement à un seul pivot

Une implémentation triviale de l'algorithme Quicksort repose fortement sur une procédure de partitionnement à pivot unique. En d'autres termes, le partitionnement divise le tableau A = [a p , a p + 1 , a p + 2 ,…, a r ] en deux parties A [p..q] et A [q + 1..r] telles cette:

  • Tous les éléments de la première partition, A [p..q] sont inférieurs ou égaux à la valeur pivot A [q]
  • Tous les éléments de la deuxième partition, A [q + 1..r] sont supérieurs ou égaux à la valeur pivot A [q]

Après cela, les deux partitions sont traitées comme des tableaux d'entrée indépendants et alimentées par l'algorithme Quicksort. Voyons le Quicksort de Lomuto en action:

2.2. Performance avec éléments répétés

Disons que nous avons un tableau A = [4, 4, 4, 4, 4, 4, 4] qui a tous les éléments égaux.

En partitionnant ce tableau avec le schéma de partitionnement à pivot unique, nous obtiendrons deux partitions. La première partition sera vide, tandis que la deuxième partition aura N-1 éléments. En outre, chaque appel ultérieur de la procédure de partition réduira la taille d'entrée d'une seule . Voyons voir comment ça fonctionne:

Puisque la procédure de partition a une complexité temporelle linéaire, la complexité temporelle globale, dans ce cas, est quadratique. C'est le pire des cas pour notre tableau d'entrée.

3. Partitionnement à trois voies

Pour trier efficacement un tableau ayant un nombre élevé de clés répétées, nous pouvons choisir de gérer les clés égales de manière plus responsable. L'idée est de les placer dans la bonne position lorsque nous les rencontrons pour la première fois. Donc, ce que nous recherchons, c'est un état à trois partitions du tableau:

  • La partition la plus à gauche contient des éléments strictement inférieurs à la clé de partitionnement
  • La partition du milieu contient tous les éléments qui sont égaux à la clé de partitionnement
  • La partition la plus à droite contient tous les éléments qui sont strictement supérieurs à la clé de partitionnement

Nous allons maintenant approfondir quelques approches que nous pouvons utiliser pour réaliser un partitionnement à trois voies.

4. L'approche de Dijkstra

L'approche de Dijkstra est un moyen efficace de faire un partitionnement à trois. Pour comprendre cela, examinons un problème de programmation classique.

4.1. Problème du drapeau national néerlandais

Inspiré par le drapeau tricolore des Pays-Bas, Edsger Dijkstra a proposé un problème de programmation appelé le problème du drapeau national néerlandais (DNF).

En un mot, c'est un problème de réarrangement où on nous donne des boules de trois couleurs placées au hasard sur une ligne, et on nous demande de regrouper les boules de même couleur ensemble . De plus, le réarrangement doit garantir que les groupes suivent le bon ordre.

Fait intéressant, le problème DNF fait une analogie frappante avec le partitionnement à 3 voies d'un tableau avec des éléments répétés.

Nous pouvons catégoriser tous les nombres d'un tableau en trois groupes par rapport à une clé donnée:

  • Le groupe Rouge contient tous les éléments strictement inférieurs à la clé
  • Le groupe Blanc contient tous les éléments égaux à la clé
  • Le groupe Bleu contient tous les éléments strictement supérieurs à la clé

4.2. Algorithme

L'une des approches pour résoudre le problème DNF consiste à choisir le premier élément comme clé de partitionnement et à parcourir le tableau de gauche à droite. Lorsque nous vérifions chaque élément, nous le déplaçons vers son groupe correct, à savoir Lesser, Equal et Greater.

Pour suivre la progression de notre partitionnement, nous aurions besoin de l'aide de trois pointeurs, à savoir lt , current et gt. À tout moment, les éléments à gauche de lt seront strictement inférieurs à la clé de partitionnement, et les éléments à droite de gt seront strictement supérieurs à la clé .

De plus, nous utiliserons le pointeur actuel pour le balayage, ce qui signifie que tous les éléments situés entre les pointeurs actuel et gt doivent encore être explorés:

Pour commencer, nous pouvons définir les pointeurs lt et current au tout début du tableau et le pointeur gt à la toute fin:

Pour chaque élément lu via le pointeur courant , nous le comparons à la clé de partitionnement et prenons l'une des trois actions composites:

  • Si input [current] <key , alors nous échangeons l' entrée [current] et input [lt] et incrémentons les pointeurs courant et lt
  • If input[current] == key, then we increment current pointer
  • If input[current] > key, then we exchange input[current] and input[gt] and decrement gt

Eventually, we'll stop when the current and gt pointers cross each other. With that, the size of the unexplored region reduces to zero, and we'll be left with only three required partitions.

Finally, let's see how this algorithm works on an input array having duplicate elements:

4.3. Implementation

First, let's write a utility procedure named compare() to do a three-way comparison between two numbers:

public static int compare(int num1, int num2) { if (num1 > num2) return 1; else if (num1 < num2) return -1; else return 0; }

Next, let's add a method called swap() to exchange elements at two indices of the same array:

public static void swap(int[] array, int position1, int position2) { if (position1 != position2) { int temp = array[position1]; array[position1] = array[position2]; array[position2] = temp; } }

To uniquely identify a partition in the array, we'll need its left and right boundary-indices. So, let's go ahead and create a Partition class:

public class Partition { private int left; private int right; }

Now, we're ready to write our three-way partition() procedure:

public static Partition partition(int[] input, int begin, int end) { int lt = begin, current = begin, gt = end; int partitioningValue = input[begin]; while (current <= gt) { int compareCurrent = compare(input[current], partitioningValue); switch (compareCurrent) { case -1: swap(input, current++, lt++); break; case 0: current++; break; case 1: swap(input, current, gt--); break; } } return new Partition(lt, gt); }

Finally, let's write a quicksort() method that leverages our 3-way partitioning scheme to sort the left and right partitions recursively:

public static void quicksort(int[] input, int begin, int end) { if (end <= begin) return; Partition middlePartition = partition(input, begin, end); quicksort(input, begin, middlePartition.getLeft() - 1); quicksort(input, middlePartition.getRight() + 1, end); }

5. Bentley-McIlroy's Approach

Jon Bentley and Douglas McIlroy co-authored an optimized version of the Quicksort algorithm. Let's understand and implement this variant in Java:

5.1. Partitioning Scheme

The crux of the algorithm is an iteration-based partitioning scheme. In the start, the entire array of numbers is an unexplored territory for us:

We then start exploring the elements of the array from the left and right direction. Whenever we enter or leave the loop of exploration, we can visualize the array as a composition of five regions:

  • On the extreme two ends, lies the regions having elements that are equal to the partitioning value
  • The unexplored region stays in the center and its size keeps on shrinking with each iteration
  • On the left of the unexplored region lies all elements lesser than the partitioning value
  • On the right side of the unexplored region are elements greater than the partitioning value

Eventually, our loop of exploration terminates when there are no elements to be explored anymore. At this stage, the size of the unexplored region is effectively zero, and we're left with only four regions:

Next, we move all the elements from the two equal-regions in the center so that there is only one equal-region in the center surrounding by the less-region on the left and the greater-region on the right. To do so, first, we swap the elements in the left equal-region with the elements on the right end of the less-region. Similarly, the elements in the right equal-region are swapped with the elements on the left end of the greater-region.

Finally, we'll be left with only three partitions, and we can further use the same approach to partition the less and the greater regions.

5.2. Implementation

In our recursive implementation of the three-way Quicksort, we'll need to invoke our partition procedure for sub-arrays that'll have a different set of lower and upper bounds. So, our partition() method must accept three inputs, namely the array along with its left and right bounds.

public static Partition partition(int input[], int begin, int end){ // returns partition window }

For simplicity, we can choose the partitioning value as the last element of the array. Also, let's define two variables left=begin and right=end to explore the array inward.

Further, We'll also need to keep track of the number of equal elements lying on the leftmost and rightmost. So, let's initialize leftEqualKeysCount=0 and rightEqualKeysCount=0, and we're now ready to explore and partition the array.

First, we start moving from both the directions and find an inversion where an element on the left is not less than partitioning value, and an element on the right is not greater than partitioning value. Then, unless the two pointers left and right have crossed each other, we swap the two elements.

In each iteration, we move elements equal to partitioningValue towards the two ends and increment the appropriate counter:

while (true) { while (input[left]  partitioningValue) { if (right == begin) break; right--; } if (left == right && input[left] == partitioningValue) { swap(input, begin + leftEqualKeysCount, left); leftEqualKeysCount++; left++; } if (left >= right) { break; } swap(input, left, right); if (input[left] == partitioningValue) { swap(input, begin + leftEqualKeysCount, left); leftEqualKeysCount++; } if (input[right] == partitioningValue) { swap(input, right, end - rightEqualKeysCount); rightEqualKeysCount++; } left++; right--; }

In the next phase, we need to move all the equal elements from the two ends in the center. After we exit the loop, the left-pointer will be at an element whose value is not less than partitioningValue. Using this fact, we start moving equal elements from the two ends towards the center:

right = left - 1; for (int k = begin; k = begin + leftEqualKeysCount) swap(input, k, right); } for (int k = end; k > end - rightEqualKeysCount; k--, left++) { if (left <= end - rightEqualKeysCount) swap(input, left, k); } 

In the last phase, we can return the boundaries of the middle partition:

return new Partition(right + 1, left - 1);

Finally, let's take a look at a demonstration of our implementation on a sample input

6. Algorithm Analysis

In general, the Quicksort algorithm has an average-case time complexity of O(n*log(n)) and worst-case time complexity of O(n2). With a high density of duplicate keys, we almost always get the worst-case performance with the trivial implementation of Quicksort.

However, when we use the three-way partitioning variant of Quicksort, such as DNF partitioning or Bentley's partitioning, we're able to prevent the negative effect of duplicate keys. Further, as the density of duplicate keys increase, the performance of our algorithm improves as well. As a result, we get the best-case performance when all keys are equal, and we get a single partition containing all equal keys in linear time.

Nevertheless, we must note that we're essentially adding overhead when we switch to a three-way partitioning scheme from the trivial single-pivot partitioning.

For DNF based approach, the overhead doesn't depend on the density of repeated keys. So, if we use DNF partitioning for an array with all unique keys, then we'll get poor performance as compared to the trivial implementation where we're optimally choosing the pivot.

But, Bentley-McIlroy's approach does a smart thing as the overhead of moving the equal keys from the two extreme ends is dependent on their count. As a result, if we use this algorithm for an array with all unique keys, even then, we'll get reasonably good performance.

In summary, the worst-case time complexity of both single-pivot partitioning and three-way partitioning algorithms is O(nlog(n)). However, the real benefit is visible in the best-case scenarios, where we see the time complexity going from O(nlog(n)) for single-pivot partitioning to O(n) for three-way partitioning.

7. Conclusion

In this tutorial, we learned about the performance issues with the trivial implementation of the Quicksort algorithm when the input has a large number of repeated elements.

With a motivation to fix this issue, we learned different three-way partitioning schemes and how we can implement them in Java.

Comme toujours, le code source complet de l'implémentation Java utilisée dans cet article est disponible sur GitHub.