Un buon algoritmo di ordinamento per i dati per lo più ordinati che non tutti si adattano alla memoria?

Question

Nel caso in cui si è data:

• certa quantità di dati
• memoria con dimensioni metà della dimensione dei dati
• parte dei dati vengono ordinati
• non si conosce la dimensione della ordinato dati.

Quale algoritmo di scelta sceglieresti? Sto discutendo tra inserimento e quicksort. So che il caso migliore per l'ordinamento di inserimento è O (n), ma il caso peggiore è O (n). Inoltre, considerando il fatto che la memoria è limitata, dividerei i dati in due parti, e su ciascuno di essi fare quicksort, quindi unire tutto. Occorrerà O (n) tempo per dividere i dati, O (n) per unire i dati e O (n log n) per ordinare i dati usando quicksort, per un runtime netto di O (n log n).

Qualcuno ha qualche suggerimento su come migliorare questo?

Answer 1

Il tuo approccio simil-mergesort sembra molto ragionevole. Più in generale, questo tipo di algoritmo di ordinamento è chiamato external sorting algorithm. Questi algoritmi funzionano spesso come descritto in precedenza, caricando in memoria alcuni sottoinsiemi di dati, ordinandoli e quindi riscrivendoli su disco. Alla fine, usa un algoritmo di fusione per unire di nuovo tutto. La scelta di quanto caricare e quale algoritmo di ordinamento utilizzare di solito sono le preoccupazioni dominanti. Mi concentrerò principalmente sulla scelta dell'algoritmo di ordinamento.

I tuoi dubbi circa il comportamento peggiore di quicksort sono in genere niente di cui preoccuparsi, poiché se si sceglie il pivot in modo casuale, la probabilità di ottenere un runtime veramente scadente è bassa. La strategia di pivot casuale funziona bene anche se i dati sono già ordinati, poiché non ha input di caso peggiore (a meno che qualcuno non conosca il generatore di numeri casuali e il seed). Puoi anche utilizzare una variante quicksort come introsort, che non ha il comportamento peggiore, come l'algoritmo di ordinamento per evitare questo caso peggiore.

Detto questo, dal momento che si sa che i dati sono già parzialmente ordinati, si consiglia di esaminare uno adaptive sorting algorithm per il passaggio di ordinamento. Hai menzionato l'insertion sort per questo, ma ci sono algoritmi adattivi molto migliori là fuori. Se la memoria è scarsa (come hai descritto), potresti provare a esaminare l'algoritmo smoothsort, che ha il runtime O (n) best-case, il tempo di esecuzione peggiore O (n log n), e usa solo O (1) memoria. Non è così adattivo come altri algoritmi (come Python timsort, natural mergesort o Cartesian tree sort), ma ha un utilizzo di memoria inferiore. Inoltre, non è veloce come un buon quicksort, ma se i dati sono in gran parte ordinati, può fare abbastanza bene.

Spero che questo aiuti!

Answer 2

A prima vista, vorrei dividere & conquistare con quicksort e chiamarlo un giorno. Molti problemi di algoritmi sono troppo pensati.

Ora, se si dispone di dati di test con cui lavorare e si desidera veramente afferrarlo, inserire una classe astratta nel mezzo e nel punto di riferimento. Siamo in grado di affrontare e superare le cose tutto il giorno, ma sapendo che i dati sono già parzialmente ordinati, dovrai testare. I dati ordinati determinano le prestazioni peggiori nella maggior parte delle implementazioni Quicksort.

Si consideri che ci sono many sorting algorithms e alcuni sono più adatti ai set ordinati. Inoltre, quando sai che un set è ordinato, puoi unirlo con un altro set in n time. Pertanto, l'identificazione di blocchi di dati ordinati prima potrebbe risparmiare un sacco di tempo quando si confronta l'aggiunta di un singolo passaggio (n) e riducendo notevolmente le possibilità di quicksort in (n).