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
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()

  • Seleziona l’ultimo elemento (può essere qualsiasi a seconda dell’implementazione) come elemento pivot.
  • Inizializza il valore del puntatore i su beg - 1 in modo che possiamo spostare elementi più piccoli di pivot all’inizio dell’array.
  • Attraversa in modo iterativo l’array ed esegui le seguenti operazioni per ogni elemento.
  • Se l’elemento A[i] < pivot incrementa i e scambia A[i] con A[j].
  • Scambia A[i] con A[end] per mettere l’elemento pivot nella sua posizione corretta.
  • Restituisce l’indice dell’elemento pivot.

QuickSort()

  • Seleziona l’indice pivot pi.
  • Partiziona l’array attorno all’indice pivot.
  • Ordina ricorsivamente gli elementi sul lato sinistro arr[beg,...,pi] dell’elemento pivot.
  • Ordina ricorsivamente gli elementi sul lato destro arr[pi+1,...,end] dell’elemento pivot.

algoritmo di ordinamento rapido

risultato dell&rsquo;algoritmo di ordinamento rapido

Esempio di ordinamento rapido

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

  • Il primo 3 è selezionato come elemento pivot, l’array è partizionato in due sottoparti (1,2) - elementi più piccoli e (6,5,4) - elementi più grandi. E poi 3 viene messo nella sua posizione ordinata. I due sottoarray formati vengono quindi ordinati in modo ricorsivo.
  • Per il sottoarray (1,2), 2 è selezionato come elemento perno e messo nella posizione corretta e viene formato il sottoarray (1) che è già ordinato.
  • Per il sottoarray (6,5,4), 4 viene messo in posizione ordinata, e viene formato il sottoarray (6,5), che viene quindi ordinato ricorsivamente.
  • Per il sottoarray (6,5), 5 è selezionato come perno e messo nella posizione corretta, che dà (6) come nuovo sottoarray. Il sottoarray di un singolo elemento (6) è già ordinato.
  • Infine, otteniamo l’array ordinato come (1, 2, 3, 4, 5, 6).

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(n2).

  • 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).

Ti piacciono i nostri tutorial? Iscriviti a DelftStack su YouTube per aiutarci a creare altre guide video di alta qualità. Iscriviti
Harshit Jindal avatar Harshit Jindal avatar

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

LinkedIn

Articolo correlato - Sort Algorithm