Algoritmo più efficente

[ciccionet78]

Ciao a tutti
Ho questo problema
Dato un arry di dimensione n continuo intero non ordinato, sapendo che tale array è diviso in buona sostanza in tre parti
[0...100] [100...200] [200...300]
Trovare l'algoritmo di ordinamento più efficiente per ordinare il problema.
Ora visto come si presenta l'algoritmo, dovrei utilzzare un sistema che sfrutta
il fatto che l'array risulta in qualche modo partizionato.
Quindi potrei utilizzare quicksort ricorsivamente 3 volte su ciascun array avendo min e max già noti.
che ne dite?

[apatriarca]

Non mi è del tutto chiaro il testo del problema. Nella prima parte del post dici per esempio che la dimensione dell'array è n, ma poi la dimensione sembra fissa. Che cosa significa poi esattamente che l'array è "diviso in buona sostanza in tre parti"? Che tipo di dati contiene l'array?

[xsl]

Io propongo l'uso del Merge Sort.

[ciccionet78]

"apatriarca":Non mi è del tutto chiaro il testo del problema. Nella prima parte del post dici per esempio che la dimensione dell'array è n, ma poi la dimensione sembra fissa. Che cosa significa poi esattamente che l'array è "diviso in buona sostanza in tre parti"? Che tipo di dati contiene l'array?

Ho riportato il problema per come è scritto.
Secondo me la dimensione è fissa a 300.
L'array va è unico [0.....100......200.....300] da 0 a 100, da 100 a 200 e da 200 a 300 non è ordinato.
Anche io avevo pensato merge sort, solo che forse è più oneroso in termini di complessità computazionale

[apatriarca]

La complessità computazionale del quicksort è peggiore di quella del mergesort, ma è spesso più veloce e utilizza meno memoria. Trovo che il problema sia mal posto e alla fine poco interessante. 300 valori è molto poco e anche il selection sort sarebbe abbastanza veloce da ordinare così pochi valori in un tempo decente. La stessa separazione dell'array in 3 parti non cambia in modo sostanziale l'operazione di ordinamento. Sarà infatti sufficiente ordinare separatamente le 3 parti come se fossero 3 array separati. Il metodo più efficiente sarebbe ovviamente quello di eseguire i 3 ordinamenti in parallelo. Dal punto di vista di comportamento asintotico, supponendo di dover ricorrere ad un algoritmo di ordinamento comparativo, qualsiasi algoritmo con complessità di $n*log(n)$ sarebbe "il più efficiente". Se si vuole qualcosa di più specifico, i dati forniti non sono sufficienti a dare una risposta.

[canemacchina]

Concordo, considerando la struttura dell'array non c'è niente di più efficiente di quanto non si possa fare nel caso generale dell'ordinamento (a meno di parallelizzare il processo, cosa che però non è dipendente dall'algoritmo scelto).

Quicksort teoricamente ha una complessità asintotica peggiore di Mergesort, però di fatto va più veloce (non a caso è stato chiamato QUICKsort). Ed esistono versioni di quicksort con scelta del pivot diversa dal solito che migliorano la sua complessità asintotica.

Al massimo, ma si tratta sempre di considerazioni di carattere generale e non dipendenti dal problema per come è posto, in genere si può ordinare con quicksort fino ad aver ottenuto array di piccole dimensioni disordinati, i quali vengono ordinati con insertionsort. Non ricordo i valori, ma ricordo che alcuni studi hanno dimostrato che, sperimentalmente, array di 5-10 elementi vengono ordinati più velocemente da insertionsort che da quicksort o altri.