Algoritmo di analisi pre-ordinamento?

Question

È un noto problema con Quicksort che quando il set di dati è inserito o quasi nell'ordine, le prestazioni si riducono in modo orribile. In questo caso, Insertion Sort, che è normalmente molto lento, è facilmente la scelta migliore. La domanda è sapere quando usare quale.

Esiste un algoritmo disponibile per eseguire un set di dati, applicare un fattore di confronto e restituire un rapporto sul livello di chiusura del set di dati in ordine di classificazione? Preferisco Delphi/Pascal, ma posso leggere altre lingue se l'esempio non è eccessivamente complesso.

Answer 1

Come ci si aspetterebbe un bel po 'di riflessione. La tecnica della mediana di tre significa che il comportamento peggiore di quicksort non si verifica per i dati ordinati, ma per i casi meno ovvi.

Introsort è piuttosto eccitante, poiché evita del tutto il quadratico di Quicksort. Invece della tua domanda naturale, "come faccio a rilevare che i dati sono quasi ordinati", in effetti si chiede come sta andando avanti, "ci vuole troppo tempo?". Se la risposta è sì, passa da quicksort a heapsort.

Timsort combina merge sort con insertion sort e si comporta molto bene su dati ordinati o invertiti e su dati che includono sottoinsiemi ordinati o in ordine inverso.

Quindi probabilmente la risposta alla tua domanda è "non hai bisogno di un'analisi preliminare, hai bisogno di un algoritmo di ordinamento adattivo".

Answer 2

Non ho sentito di alcuna analisi di pre-selezione ma la mia opinione è che se si passerà attraverso il set di dati per analizzarlo, si sta già tagliando le prestazioni del tempo di ordinamento complessivo.

Answer 3

Una possibile soluzione consiste nel prendere il primo, l'ultimo e l'elemento centrale nell'intervallo di ordinamento corrente (durante l'operazione QuickSort) e scegliere quello centrale come elemento di pivot.

Answer 4

Per analizzare completamente al fine di decidere quale algoritmo utilizzare, si eseguirà quasi il lavoro di ordinamento. Si potrebbe fare qualcosa come controllare i valori con una piccola percentuale di indici casuali ma in aumento (cioè analizzare un piccolo campione degli articoli).

Answer 5

C'è anche SmoothSort, che è apparentemente abbastanza complicato da implementare, ma varia tra O (N log N) a O (N) a seconda di come vengono ordinati i dati.

http://en.wikipedia.org/wiki/Smoothsort

lungo PDF ingannevole: http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD796a.PDF

Tuttavia, se i dati è davvero enorme e si deve accedere in serie, mergesort è probabilmente il migliore. È sempre O (N log N) e ha eccellenti proprietà 'locality'.

Answer 6

Dovresti comunque eseguire tutti i record per determinare se è ordinato o meno, quindi per migliorare le prestazioni, inizia con il tuo primo record ed esegui il resto finché non noti qualcosa non correttamente ordinato, o raggiungi la fine di la lista. Se trovi miss, quindi ordina solo gli elementi da quella posizione fino alla fine (poiché l'inizio dell'elenco è già ordinato).

A ciascuna voce nella seconda parte, vedere se l'articolo è < rispetto all'ultimo elemento nella prima parte e in tal caso utilizzare un ordinamento di inserimento in SOLO la prima parte. Altrimenti Quicksort contro tutti gli altri oggetti nella seconda parte. In questo modo l'ordinamento è ottimizzato per il caso specifico.

Answer 7

QuickSort Beng un problema solo quando il set di dati è enorme e già lo più ordinato, vorrei utilizzare la seguente euristica (in attesa di una soluzione in piena regola):

• Non preoccupatevi se i dati impostare la dimensione è sotto la soglia.

• Se si dispone di un accesso rapido (indicizzato) ai record (elementi), prendere un campione con 1 record in ogni record N e vedere se sono già ordinati. Dovrebbe essere abbastanza veloce per un piccolo campione e quindi puoi decidere di usare l'ordinamento rapido o meno.

Answer 8

Per rendere un punto concettuale che le persone non hanno ancora fatto: Quicksort è un algoritmo di divisione e conquista di buon senso con un bug ovvio in rari casi. Supponiamo di voler ordinare una pila di carte per studenti. (Che devo fare con un po 'di regolarità.) Nell'algoritmo quicksort, scegli un po' di carta, il pivot. Quindi dividere gli altri documenti a seconda che siano prima o dopo il perno. Quindi ripeti quello con i due sotto-moduli. Qual è il bug? Il pivot potrebbe essere un nome che si trova vicino a un'estremità dell'elenco anziché al centro, in modo da non ottenere molto da dividere in due pile.

Unisci un altro algoritmo di divisione e conquista che funziona in un ordine diverso. È possibile unire due elenchi ordinati in tempo lineare. Dividete le carte in due pile uguali o quasi uguali, quindi ordinate ricorsivamente ciascuna, quindi unite. Unisci sort non ha bug. Uno dei motivi per cui quicksort è più popolare di merge sort è storico: Quicksort è veloce (di solito) e funziona senza memoria aggiuntiva. Ma in questi giorni, può essere più importante salvare i confronti che risparmiare memoria, e il riassetto attuale è spesso astratto dai puntatori di permutazione. Se le cose fossero sempre state così, sospetto che l'unire sort sarebbe stato semplicemente più popolare di quicksort. (E forse aggiungere "velocemente" al nome era un buon venditore.)