Merge sort vs performance quicksort

Se guardi il tuo codice per scambiarlo:

// If current element is lower than pivot
// then swap it with the element at store_index
// and move the store_index to the right.

Tuttavia, circa il 50% delle volte che la stringa appena scambiata deve essere spostata indietro, ecco perché le unioni più veloci ordinano il lavoro da entrambe le estremità allo stesso tempo.

Successivamente, se si controlla se il primo e l'ultimo elemento sono uguali prima di effettuare ciascuna chiamata ricorsiva, si evita di sprecare tempo chiamando una funzione solo per uscirne rapidamente. Questo succede 10000000 nel test finale che aggiunge notevoli quantità di tempo.

Usa,

if (pivot_index -1 > start)   quick_sort (righe, start, pivot_index - 1);

if (pivot_index + 1 < end)   quick_sort (righe, pivot_index + 1, fine);

Vuoi comunque una funzione esterna per fare un'iniziale if (start < end) ma deve solo succedere una volta in modo che la funzione possa solo chiamare una versione non sicura del tuo codice senza quel confronto esterno.

Inoltre, la scelta di un pivot casuale tende ad evitare N ^ 2 risultati peggiori, ma probabilmente non è un grosso problema con il set di dati casuali.

Infine, il problema nascosto è che QuickSort sta confrontando le stringhe in secchi sempre più piccoli che sono sempre più vicini,

(Modifica: Quindi, AAAAA, AAAAB, AAAAC, AAAAD poi AAAAA, AAAAB. Quindi, strcmp ha bisogno di intervenire su un sacco di A prima di cercare le parti utili delle stringhe.)

ma con Merge sort si guardano prima i bucket più piccoli mentre sono diversi casuali. Le passate finali di Mergsorts mettono a confronto un sacco di stringhe l'una vicina all'altra, ma non è un problema quindi. Un modo per rendere le stringhe Quick più veloci per le stringhe è confrontare le prime cifre delle stringhe esterne e se le stesse li ignorano quando eseguono i confronti interiori, ma devi fare attenzione che tutte le stringhe abbiano abbastanza cifre da non saltare oltre le null terminator.

are my results as expected?

Merge sort ha le seguenti caratteristiche di prestazione:

• Best case: O(n log n)
• Caso medio: O(n log n)
• Peggiore caso: O(n log n)

Quicksort ha le seguenti caratteristiche di prestazione:

• Best case: O(n log n)
• Caso medio: O(n log n)
• Peggiore caso: O(n^2)

Ricorda: Notazione Big-O indica i limiti asintotici ignorando i fattori costanti .

Quicksort ha prestazioni ottimali quando gli elementi pivot che sceglie tendono uniformemente a partizionare sotto-intervalli. Ha una prestazione quadratica nel caso peggiore quando il contrario vale, come quando l'input è ordinato al contrario o quasi in ordine inverso. Esistono molte varianti di quicksort e variano, in parte, nel modo in cui scelgono gli elementi pivot.

Unisci le prestazioni di ordinamento è molto più limitato e prevedibile rispetto alle prestazioni di Quicksort. Il prezzo per tale affidabilità è che il caso medio di un tipo di merge è più lento rispetto al caso medio di quicksort perché il fattore costante di un tipo di unione è maggiore . Tuttavia, questo fattore costante dipende molto dai particolari dettagli dell'implementazione . Una buona implementazione di tipo merge avrà prestazioni medie migliori rispetto a un'implementazione di quicksort scarsa.

Per provare a mettere questo in prospettiva, consideriamo cosa ci si può aspettare dalla libreria standard. Per avere un'idea, ho scritto questo in C ++:

#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
#include <string>
#include <time.h>

std::string gen_random() {
    size_t len = rand() % 25 + 5;

    std::string x;

    std::generate_n(std::back_inserter(x), len, rand);
    return x;
}

static const int num = 10000000;

int main(){
    std::vector<std::string> strings;

    std::generate_n(std::back_inserter(strings), num, gen_random);

    clock_t start = clock();
    std::sort(strings.begin(), strings.end());
    clock_t ticks = clock() - start;

    std::cout << ticks / (double)CLOCKS_PER_SEC;

    return 0;
}

Questo genera e quindi ordina il numero specificato di stringhe (ognuna compresa tra 5 e 30 caratteri). Sulla mia macchina (che è probabilmente un po 'più lenta della tua) ho un tempo di ~ 14 secondi per l'ordinamento, che immagino sia implementato come Introsort. Nel caso normale, mi aspetterei quasi la stessa prestazione da Introsort come Quicksort.

Bottom line: il risultato che ottieni per l'ordinamento di tipo merge è abbastanza ragionevole, ma il risultato che ottieni da Quicksort indica che l'implementazione ha un problema grave.

Il tuo risultato non è assolutamente previsto. Infatti, quicksort è usato perché tende a essere un po ' più veloce di un mergesort nel caso medio, cioè se quicksort non degenera a causa di elementi pivot male scelti.

Questo avvertimento suggerisce anche la prima cosa che dovresti provare: scegli l'elemento pivot per quicksort a caso, eliminando così i problemi con i dati (parzialmente) preordinati. i quicksorts "accordati" sceglieranno anche 3 o 5 elementi casuali e prenderanno la mediana per le corse iniziali, poiché la scelta del pivot ha un impatto sproporzionato.

E naturalmente potrebbe essere che la tua implementazione di quicksort sia semplicemente imperfetta (è più difficile da implementare in modo veramente corretto di quanto non sembri).

Sarò d'accordo con Michael; Quicksort è difficile da implementare correttamente. Quando ero al college a scrivere il mio esame finale (un confronto tra algoritmi di ordinamento) la mia implementazione di QuickSort è riuscita a schermare in blu un computer con Windows NT (non causava un GPF, era BSODed).

Il problema più grande che generalmente si verifica quando il quicksorting è la selezione del pivot. Ricorda che il tallone d'Achille di QuickSort è piuttosto comune; una lista quasi ordinata. Per questo motivo, la corretta selezione del pivot è fondamentale nonostante la complessità extra. Anche qualcosa di così semplice come scegliere l'elemento centrale del subarray è generalmente meglio del picking alle due estremità; per i due casi più comuni di un elenco quasi ordinato e di un elenco veramente casuale, questo generalmente produrrà un buon risultato. La mediana di 3 è ancora migliore.

Un'altra cosa da verificare è che hai un "caso base" intelligente. Una partizione di 2 elementi può essere ordinata in modo banale (sono in ordine? In caso contrario, scambia em), quindi la rotazione di una matrice a 2 elementi per raggiungere il caso base di zero o di un elemento è dispendiosa.

Un'altra cosa è assicurarsi che il tuo algoritmo sia "in-place" (un vantaggio importante del QuickSort "intuitivo" rispetto al "intuitivo" MergeSort; allocare memoria è costoso), e che non stai cercando di mantenere il fai perno tra le due metà mentre fai perno. Scegli il tuo pivot, scambialo con l'ultimo elemento, quindi lavora da sinistra alla ricerca di un elemento "grande", quindi da destra alla ricerca di un elemento "piccolo"; scambia e continua fino a trovare un valore "grande" senza un valore "piccolo" sul suo diritto di scambiarlo con (scambialo con il pivot sull'ultimo elemento e recurse). Questo impedisce lo scambio non necessario per mantenere il pivot nel "centro" delle due metà.

Dove penso che anche la tua analisi stia fallendo è che non stai considerando i tuoi dati.

Che cosa succede in Unisci ordinamento e Ordinamento veloce quando ogni elemento nell'array è esattamente lo stesso? Riesci a risolvere questo problema o questo caso 'edge' mantiene i tempi di esecuzione uguali? Chi è la prestazione è migliore?

Cosa succede se i dati sono completamente casuali? Chi è la prestazione è migliore?

So my question is: is there a better way to implement quick sort that is worthwhile trying out?

Hai considerato di eseguire Insertion Sort in Ordinamento rapido quando i tuoi array sono < 100 elementi? Quale valore è più efficace per iniziare a utilizzare Insertion Sort?

Il modo in cui viene scelto il perno è la chiave per il tempo di esecuzione di Quick Sorts. Come stai scegliendo il perno? Qual è il modo migliore?

Esistono due modi per implementare l'ordinamento rapido, hai scoperto entrambi?

Penso che sarai ben servito a pensare a queste domande.

Si noti che lo pseudo-codice nella wiki non è pratico. È scritto per capire.
Se un array è [0,0,0,1] pivot è 1 e altri elementi sono inferiori al pivot,
quindi scambiando (t < - a, a < - b, b < - t) funziona come t < - a, a < - a, a < - t.
In questo caso lo scambio non funziona niente.
Se un array è [4,2,1,3] quindi [ 4 , 2,1,3] - > [2, 4 , 1,3] - > [2,1, 4 , 3] - > [2,1,3, 4 ].
In questo caso, "4" si muove come in Bubble sort.

Suggerisco un nuovo pseudo-codice.

quicksort(A, i, k)
    if i < k
        p := partition(A, i, k)
        quicksort(A, i, p - 1)
        quicksort(A, p + 1, k)

partition(array, left, right)
    hole := choosePivot(Array, left, right)
    pivot := array[hole]        // dig a hole
    array[hole] := array[right]
    hole := right               // move the hole
    while left < hole
        if array[left] >= pivot
            array[hole] := array[left]
            hole := left
            while right > hole
                if array[right] < pivot
                    array[hole] := array[right]
                    hole := right
                right := right - 1
        left := left + 1
    array[hole] := pivot        // bury the hole
    return hole

Il confronto delle prestazioni è difficile, perché dipende da alcuni fattori.

1. Attuazione
   Il buon codice funziona veloce, il codice brutto funziona lentamente, lo sai.
2. Dimensione dei dati
   un. Dimensione dell'elemento dell'array.
   b. Le dimensioni dell'intero array superano una memoria cache o meno.
   c. Le dimensioni dell'intero array superano la memoria principale o meno.
3. Struttura dei dati
   un. Un array è archiviato in una memoria continua come linguaggio C..
   b. Una matrice consiste di puntatori a una memoria continua.
   c. Il puntatore è ottenuto da malloc (3) o "nuovo" operatore.
4. Dati diffusi
   Se viene utilizzato un numero casuale, l'ESD (stima della deviazione standard) del tempo di elaborazione è del 5%. Non utilizzato quindi al 2%. Ho studiato.
5. OS, H / W
   Linux / Unix, Microsoft Windows è un sistema operativo multi-task. Il programma è spesso interrotto.
   Molte CPU core sono migliori. Prova prima di accedere alla GUI è meglio. Il sistema operativo a singola operazione è migliore.

Esempio: N = 100000, 32 byte / elemento, pivot è un elemento intermedio, strcmp (3), memoria continua

qsort_middle()  usec = 522870   call = 999999   compare = 28048465  copy = 15404514
merge_sort()    usec = 533722   call = 999999   compare = 18673585  copy = 19673584

I programmi e gli script di Source C sono pubblicati in github . Thre è vari quicksort e unisci ordinamento.

Non si sta chiamando la libreria standard qsort (o la funzione standard di ordinamento C ++). Ciò che chiamate sono due funzioni casuali scritte da una persona casuale che è più o meno intelligente e che si rifletterà nello spettacolo. Non stai confrontando le prestazioni di due algoritmi, stai confrontando le prestazioni di due implementazioni casuali.

Di solito la cosa migliore da fare è usare ciò che la maggior parte delle persone sta usando, in questo caso chiamando qsort. Il che si può assumere ordinerà le cose il più velocemente possibile. Poiché l'ordinamento è così essenziale, è improbabile che l'implementazione di qsort sia semplice quicksort, e ancor meno probabile sia un'implementazione di quicksort semplice con evidenti problemi di prestazioni (come la funzione quick_sort che hai usato).

Se sei fortunato, qsort per esempio ordina gli array ordinati in tempo lineare e gli array quasi ordinati in un tempo vicino al lineare.