Un po 'riformulato, sotto forma di gioco, problema di vita reale:
Supponiamo che ci sia un insieme di elementi {1, 2, ..., n}. Il giocatore A ha scelto una singola permutazione di questo set. Il giocatore B vuole scoprire l'ordine degli elementi ponendo domande sulla forma "È X prima nella permutazione di Y?", Dove X e Y sono elementi dell'insieme.
Supponendo che B voglia minimizzare la quantità di domande, quante volte dovrebbe chiedere, e quale sarebbe l'algoritmo?
Questo è esattamente simile a un problema di ordinamento basato sul confronto. Cioè, abbiamo tutti gli elementi in ordine criptato e vogliamo ordinarli usando solo confronti (ad esempio X < Y)
Come tale, qualsiasi algoritmo di ordinamento basato sul confronto funzionerà. Le prestazioni di queste opzioni variano, ma sappiamo per certo che non è possibile ottenere un tempo di esecuzione inferiore a O (n * log (n)) per l'ordinamento basato sul confronto. In molti scenari di ordinamento reali, possiamo effettivamente fare meglio - ma in questo caso possiamo solo fare affidamento sui confronti, quindi questo è un limite difficile per il tempo di esecuzione.
Esistono diversi algoritmi per questo problema:
Best case Avg. case Worst case Worst case memory usage
Quicksort O(n log(n)) O(n log(n)) O(n^2) O(n)
Mergesort O(n log(n)) O(n log(n)) O(n log(n)) O(n)
Heapsort O(n log(n)) O(n log(n)) O(n log(n)) O(1)
Bubble Sort O(n) O(n^2) O(n^2) O(1)
Insertion Sort O(n) O(n^2) O(n^2) O(1)
Selection Sort O(n^2) O(n^2) O(n^2) O(1)
Oltre al tempo di esecuzione e all'utilizzo della memoria, è opportuno ricordare che Insertion Sort è più veloce per i piccoli array (le versioni ottimizzate di mergesort possono passare a Insertion Sort quando gli array diventano piccoli). L'ordinamento della selezione utilizza la quantità minima di scambi effettivi, che potrebbe essere rapida nei sistemi in cui tali scambi sono costosi.
Alcuni algoritmi sono instabili, il che significa che non è garantito che gli elementi uguali vengano fuori nell'ordine in cui li recuperiamo - tuttavia, in questo caso non dovrebbe fare alcuna differenza, in quanto non esiste un ordine iniziale in un set.
Infine, nota che Quicksort ha un tempo di esecuzione peggiore rispetto a Mergesort e Heapsort. Tuttavia, per la maggior parte degli input, Quicksort spesso si dimostra più veloce o più veloce di questi, a causa del modo in cui è possibile implementare l'algoritmo.
Leggi altre domande sui tag algorithms