Ordinamento rapido

1. Algoritmo di ordinamento rapido
2. Esempio di ordinamento rapido
3. Implementazione dell’algoritmo di ordinamento rapido
4. Complessità algoritmo di ordinamento rapido

L’ordinamento rapido è un algoritmo di ordinamento altamente efficiente basato sul principio dell’algoritmo divide et impera. L’ordinamento rapido funziona partizionando l’array in due parti attorno a un elemento pivot selezionato. Sposta gli elementi più piccoli sul lato sinistro del perno e gli elementi più grandi sul lato destro. Successivamente, le sottoparti sinistra e destra vengono ordinate in modo ricorsivo per ordinare l’intero array. Si chiama Ordinamento rapido perché è circa 2 o 3 volte più veloce dei comuni algoritmi di ordinamento. L’ordinamento rapido è ampiamente utilizzato per la ricerca di informazioni e calcoli numerici all’interno di strutture di dati.

Algoritmo di ordinamento rapido

Supponiamo di avere un array non ordinato A[] contenente n elementi. Prendi due variabili, beg e end, quindi memorizza l’indice dell’elemento iniziale e quello finale.

Partition()

QuickSort()

Esempio di ordinamento rapido

Supponiamo di avere l’array: (6,5,1,4,2,3). Lo ordineremo utilizzando l’algoritmo di ordinamento rapido.

Implementazione dell’algoritmo di ordinamento rapido

#include <bits/stdc++.h>
using namespace std;

int partition(int arr[], int beg, int end) {
  // Select the last element as pivot element
  int pivot = arr[end];
  int i = (beg - 1);
  // Move smaller elements to left side and larger on right side
  for (int j = beg; j < end; j++) {
    if (arr[j] <= pivot) {
      i++;
      swap(arr[i], arr[j]);
    }
  }
  swap(arr[i + 1],
       arr[end]);  // Move pivot element to its right position in array
  return (i + 1);
}

void quickSort(int arr[], int beg, int end) {
  if (beg < end) {
    int pi = partition(arr, beg, end);
    quickSort(arr, beg,
              pi - 1);  // Recursive Sort element on left side of partition
    quickSort(arr, pi + 1,
              end);  // Recursive Sort element on right side of partition
  }
}
int main() {
  int n = 6;
  int arr[6] = {5, 3, 4, 2, 1, 6};
  cout << "Input array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
  quickSort(arr, 0, n - 1);  // Sort elements in ascending order
  cout << "Output array: ";
  for (int i = 0; i < n; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}

Complessità algoritmo di ordinamento rapido

Complessità temporale

• Case nella media

Il tempo impiegato da Quick Sort è dato dalla seguente relazione di ricorrenza:

 T(n) = T(k) + T(n-k-1) + θ(n)

k qui rappresenta il numero di elementi più piccoli / più grandi dell’elemento pivot.

Questo risultato di questa relazione di ricorrenza dà T(n) = nLogn. Il caso medio si verifica quando otteniamo partizioni casuali in modo non uniforme. La complessità temporale è dell’ordine di [Big Theta]: O(nLogn).

• Peggiore caso

T(n) = T(n-1) + θ(n)

Il caso peggiore si verifica quando l’elemento pivot è sempre l’elemento più grande o più piccolo dell’array. In questo caso, tutti gli elementi cadono in un sottoarray e devono essere effettuate al massimo n chiamate. La complessità temporale nel caso peggiore è [Big O]: O(n²).

• Caso migliore

 T(n) = 2T(n/2) + θ(n)

Il caso migliore si verifica quando l’elemento pivot selezionato è sempre l’elemento centrale o quando entrambe le partizioni sono bilanciate in modo uniforme, ovvero la differenza di dimensione è 1 o inferiore. La complessità temporale nel migliore dei casi è [Big Omega]: O(nLogn).

Complessità spaziale

La complessità dello spazio caso medio per l’algoritmo di ordinamento rapido è O(logn). È lo spazio richiesto dallo stack di ricorsione. Ma nel peggiore dei casi, quando l’ordinamento di un array richiede n ricorsivo, la complessità dello spazio è O(n).