Partizionamento e ordinamento di array con molte voci ripetute con esempi Java

1. Panoramica

La complessità di runtime degli algoritmi dipende spesso dalla natura dell'input.

In questo tutorial vedremo come la banale implementazione dell'algoritmo Quicksort ha una prestazione scarsa per elementi ripetuti .

Inoltre, impareremo alcune varianti di Quicksort per partizionare e ordinare in modo efficiente gli input con un'alta densità di chiavi duplicate.

2. Trivial Quicksort

Quicksort è un algoritmo di ordinamento efficiente basato sul paradigma divide et impera. Funzionalmente parlando, opera sul posto sull'array di input e riorganizza gli elementi con semplici operazioni di confronto e scambio .

2.1. Partizionamento a perno singolo

Una banale implementazione dell'algoritmo Quicksort si basa in gran parte su una procedura di partizionamento a perno singolo. In altre parole, il partizionamento divide l'array A = [a p , a p + 1 , a p + 2 ,…, a r ] in due parti A [p..q] e A [q + 1..r] tali quello:

  • Tutti gli elementi nella prima partizione, A [p..q] sono minori o uguali al valore pivot A [q]
  • Tutti gli elementi nella seconda partizione, A [q + 1..r] sono maggiori o uguali al valore pivot A [q]

Dopodiché, le due partizioni vengono trattate come array di input indipendenti e alimentate dall'algoritmo Quicksort. Vediamo il Quicksort di Lomuto in azione:

2.2. Performance con elementi ripetuti

Supponiamo di avere un array A = [4, 4, 4, 4, 4, 4, 4] che ha tutti gli elementi uguali.

Partizionando questo array con lo schema di partizionamento a pivot singolo, otterremo due partizioni. La prima partizione sarà vuota, mentre la seconda partizione avrà N-1 elementi. Inoltre, ogni successiva chiamata della procedura di partizione ridurrà la dimensione dell'input di uno solo . Vediamo come funziona:

Poiché la procedura di partizione ha una complessità temporale lineare, la complessità temporale complessiva, in questo caso, è quadratica. Questo è lo scenario peggiore per il nostro array di input.

3. Partizionamento a tre vie

Per ordinare in modo efficiente un array con un numero elevato di chiavi ripetute, possiamo scegliere di gestire le chiavi uguali in modo più responsabile. L'idea è di metterli nella giusta posizione quando li incontriamo per la prima volta. Quindi, quello che stiamo cercando è uno stato a tre partizioni dell'array:

  • La partizione più a sinistra contiene elementi che sono strettamente inferiori alla chiave di partizionamento
  • La partizione centrale contiene tutti gli elementi che sono uguali alla chiave di partizionamento
  • La partizione più a destra contiene tutti gli elementi che sono strettamente maggiori della chiave di partizionamento

Ora approfondiremo un paio di approcci che possiamo utilizzare per ottenere il partizionamento a tre vie.

4. L'approccio di Dijkstra

L'approccio di Dijkstra è un modo efficace per eseguire il partizionamento a tre vie. Per capirlo, esaminiamo un classico problema di programmazione.

4.1. Problema della bandiera nazionale olandese

Ispirato dalla bandiera tricolore dei Paesi Bassi, Edsger Dijkstra ha proposto un problema di programmazione chiamato Dutch National Flag Problem (DNF).

In poche parole, è un problema di riorganizzazione in cui ci vengono date palline di tre colori posizionate casualmente in una linea e ci viene chiesto di raggruppare le palline dello stesso colore insieme . Inoltre, la riorganizzazione deve garantire che i gruppi seguano l'ordine corretto.

È interessante notare che il problema DNF fa un'analogia sorprendente con il partizionamento a 3 vie di un array con elementi ripetuti.

Possiamo classificare tutti i numeri di un array in tre gruppi rispetto a una determinata chiave:

  • Il gruppo Rosso contiene tutti gli elementi che sono strettamente inferiori alla chiave
  • Il gruppo White contiene tutti gli elementi che sono uguali alla chiave
  • Il gruppo Blu contiene tutti gli elementi strettamente maggiori della chiave

4.2. Algoritmo

Uno degli approcci per risolvere il problema DNF consiste nel selezionare il primo elemento come chiave di partizionamento ed eseguire la scansione dell'array da sinistra a destra. Mentre controlliamo ogni elemento, lo spostiamo nel gruppo corretto, vale a dire Minore, Uguale e Maggiore.

Per tenere traccia dei nostri progressi nel partizionamento, avremmo bisogno dell'aiuto di tre puntatori, vale a dire lt , current e gt. In qualsiasi momento, gli elementi a sinistra di lt saranno rigorosamente inferiori alla chiave di partizionamento e gli elementi a destra di gt saranno rigorosamente maggiori della chiave .

Inoltre, useremo il puntatore corrente per la scansione, il che significa che tutti gli elementi che si trovano tra i puntatori corrente e gt devono ancora essere esplorati:

Per cominciare, possiamo impostare lt e i puntatori correnti all'inizio dell'array e il puntatore gt alla fine di esso:

Per ogni elemento letto tramite il puntatore corrente , lo confrontiamo con la chiave di partizionamento e intraprendiamo una delle tre azioni composite:

  • Se input [current] <key , allora scambiamo input [current] e input [lt] e incrementiamo entrambi i puntatori corrente e 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.

Come sempre, il codice sorgente completo per l'implementazione Java utilizzata in questo articolo è disponibile su GitHub.