Finora, la maggior parte del metodo di ordinamento più rapido e comune è quicksort. Anche se ha i suoi pro e contro. Tuttavia, sto pensando che sebbene questo metodo di ordinamento sia veloce ma fornisce il passo di scambio più breve? Perché quicksort divide un insieme di elementi in 2 e poi ordina, raddoppierà il passo dello swap?
will it double up the swapping step?
Nella maggior parte dei casi: il contrario. Suppongo che scambiando si faccia riferimento al numero totale di confronti. Scambiare non ha davvero importanza secondo me, poiché dovrebbe essere un'operazione a tempo costante ed è il risultato di un confronto. Il numero di confronti è importante.
Dividendo l'insieme in due metà puoi sempre pensarlo come un albero binario. La quantità di confronti da effettuare è quindi logaritmica e dipende dall'altezza di questo albero. Tuttavia, per quicksort, questo non è vero per tutti i vettori di input. Quando l'input è già ordinato e viene scelto il pivot sbagliato, quicksort verrà eseguito in O (n ^ 2), che è terribilmente lento. Si può pensare ad un albero piuttosto alto perché quicksort non è in grado di dividere correttamente il vettore di input. Caso peggiore: non swap affatto e costoso in fase di runtime.
In generale si può dire che il numero di swap è correlato al numero di confronti. Meno confronti, meno scambi. Il numero di scambi dipende sempre dallo specifico vettore di input!
In media Quicksort ordina un array in n (log n) time (che è quasi buono come si ottiene). Nel peggiore dei casi ci vuole n² (ma questo accade raramente).
Un altro algoritmo di ordinamento comune che impiega n (log n) per ordinare è Merge Sort. Noterai che entrambi usano il metodo "Divide and Conquer", ma ognuno con una strategia diversa.
Come per lo scambio di passaggi, dipende da come viene implementato ciascun algoritmo. Ad esempio, il numero di passaggi su Merge Sort dipende in gran parte da come si implementa la funzione Merge (ad esempio, è possibile unire in posizione, utilizzare un array ausiliario, ecc.)
Nel complesso si presume che i fattori costanti (passaggi di swap, confronti e così via) siano più piccoli su Quicksort, tuttavia, di solito è preferibile rispetto a Merge Sort.
Infine, confrontare il numero di passaggi di swap con algoritmi più lenti, come Insertion o Bubble sort, non ha senso secondo me, perché il tempo di esecuzione ha un ruolo molto più importante.
La presentazione fornita nel link mostra il numero di swap di diversi algoritmi di ordinamento utilizzando la notazione O. Spero che questo ti possa aiutare.
presentazione in power point per il sistema di classificazione diverso ALG. mostrare la complessità
Leggi altre domande sui tag algorithms sorting