Problema algoritmi ordinamento

[lorenzo324]

Ho un problema a cui non riesco a dare una risposta,se ho un certo numero di numeri da ordinare sapendo che questi sono per l'80% gia ordinati , quale algoritmo per l'ordinamento tra:
-selctionsort
-inserctionsort
-bubblesort
-mergesort
-quicksort
-heapsort
-bucketsort
e' consigliabile usare e perche'?

[YuYevon]

In generale, gli algoritmi di ordinamento migliori sono quelli a complessità temporale asintotica O(nlogn), ossia mergesort, quicksort e heapsort. Tuttavia, per come sono definiti questi algoritmi, ricorrendo ad uno di essi in questo caso si perderebbe il vantaggio che si ha sulla conoscenza del fatto che l'80% degli elementi è già ordinato. Con ogni probabilità, il migliore sarebbe l'insertion sort, infatti si può dimostrare che questo algoritmo, richiamato su un array completamente ordinato (inutilmente, ma è solo per lo studio teorico) avrebbe una complessità di tempo asintotica O(n), di fatto perché non sarebbe mai eseguito il ciclo while interno caratteristico dell'algoritmo:

 insertionSort(array A)
 begin
 for i := 1 to length[A]-1 do
 begin
     value := A[i];
     j := i-1;
     while j >= 0 and A[j] > value do
     begin
         A[j + 1] := A[j];
         j := j-1;
     end;
     A[j+1] := value;
 end;
 end;

e quindi si ridurrebbe tutto a n-1 iterazioni del ciclo for esterno, dove n è la lunghezza dell'array. E come sappiamo, una complessità pari a O(n) per un algoritmo di ordinamento è quanto di meglio si possa ottenere (almeno allo stato attuale...).

C'è comunque da considerare che qui non abbiamo tutti gli elementi ordinati, ma soltanto l'80%... credo comunque che la chiave di lettura sia questa. Diciamo che in questo caso specifico non avremmo una complessità O(n) con l'insertion sort ma di sicuro il while verrebbe eseguito molte volte in meno rispetto ad un caso "medio", e questo a mio avviso lo rende preferibile.

In fondo anche andando per esclusione... quelli a complessità O(nlogn) no per i motivi di cui dicevo, il bubblesort è il peggiore in assoluto, il selection sort non mi sembra che abbia una complessità di tempo dipendende dalla natura dell'input visto che non fa altro che determinare il massimo (o il minimo) ripetutamente per sottoporzioni dell'array sempre minori... e il bucketsort dovrebbe essere preferibile in casi favorevoli della distribuzione dei valori, cioè quando sarebbe possibile avere lo stesso numero di elementi dell'array iniziale nei varii buckets, ma in questo caso mi pare che non sappiamo nulla a proposito di questo.

Insomma direi insertion sort... ovviamente l'analisi è soggetta a errori o-o"

Caso mai aggiorna il thread quando saprai la risposta...