non ho capito almeno sul piano teorico quale algoritmo mi conviene fare per ordinare un array fra l'insertionsort e il selectionsort, che io sappia hanno tutti e due tempi quadratici.
Sapete di preciso le formule per confronarli?
non ho capito almeno sul piano teorico quale algoritmo mi conviene fare per ordinare un array fra l'insertionsort e il selectionsort, che io sappia hanno tutti e due tempi quadratici.
Sapete di preciso le formule per confronarli?
Si è vero hanno entrambi un tempo di esecuzione quadratico nel senso che nel caso peggiore ci impiegano entrambi un tempo proporzionale a O(n^2) con n dimensione dell'array.Nel caso migliore (array già ordinato) l'insertion ci mette un tempo O(n),a giudicare dal codice anche l'altro è un O(n) nel caso migliore quindi penso tu possa scegliere proprio ad occhi chiusi perchè si equivalgono.Forse l'unica cosa è che il selection effettua uno scambio anche quando il minimo si trova già al suo posto,ma questo puoi evitarlo con un semplice controllo sugli indici.la mia conclusione è :hanno entrambi le medesime pessime prestazioni con array di dimensioni anche appena apena modeste,molto meglio un buon vecchio quicksort.
Il centro dell'attenzione non è sempre un buon posto in cui trovarsi
Mai discutere con uno stupido, la gente potrebbe non capire la differenza. (O. W.)
Permessi di invio
Rispondi quotando