PDA

Visualizza la versione completa : [C] Ordinamento array con Quick Sort (funzione qsort) su array giÓ ordinato


pcg4m3s
12-02-2010, 15:59
Salve,
vorrei sapere quant'Ŕ la complessitÓ del quick sort ed in particolare della funzione qsort di c nel caso in cui si esegue l'ordinamento di un array che per˛ Ŕ giÓ ordinato.
Grazie!

c_junior
12-02-2010, 16:06
qui (http://it.wikipedia.org/wiki/Quicksort)

pcg4m3s
12-02-2010, 16:11
Originariamente inviato da c_junior
qui (http://it.wikipedia.org/wiki/Quicksort)

so qual'Ŕ la complessit˛ asintotica di quick sort, quello che chiedo Ŕ che complessitÓ ha nel caso in cui l'array passatogli Ŕ giÓ ordinato, quindi in realtÓ non avrebbe bisogno di essere riordinato.

c_junior
12-02-2010, 16:13
beh se li passi un algoritmo giÓ ordinato si tratta del caso migliore(almeno penso) quindi:
Caso ottimo temporalmente Θ(nlogn)

Loading