stabilità dell'algoritmo quicksort

Quicksort non è stabile, poiché scambia elementi non adiacenti.stabilità dell'algoritmo quicksort

Per favore aiutami a capire questa affermazione.

So come funziona il partizionamento e che cos'è la stabilità. Ma non riesco a capire cosa rende questo come la ragione per questo non essere stabile? Quindi credo che si possa dire lo stesso per l'ordinamento di tipo merge - sebbene sia citato come un algoritmo stabile.

fonte

2012-11-21 IUnknown

Ciò significa che su più tipi, non è garantito avere lo stesso ordine di elementi che si risolvono nella stessa uguaglianza. quindi se hai 1,1,2,3,5,6,7, i due all'inizio potrebbero non essere in un ordine definito - questo è più importante quando si ordina su un certo tasto per oggetti più complessi, ovviamente –

è molto ben coperto [qui] (http://en.wikipedia.org/wiki/Sorting_algorithm#Stability) – axiom

Considerare cosa succede durante la partizione per la seguente matrice di coppie, dove il comparatore usa il numero intero (solo). La stringa è proprio lì in modo che abbiamo due elementi che si confrontano come se fossero uguali, ma in realtà sono distinguibili.

(4, "first"), (2, ""), (3, ""), (4, "second"), (1, "")

Per definizione una specie è stabile se, dopo l'ordinamento, i due elementi che mettono a confronto come se uguale (due 4 s) compaiono nello stesso ordine in seguito come prima.

Supponiamo di scegliere 3 come perno. I due elementi 4 finiranno dopo di esso e il 1 e il 2 prima di esso (c'è un po 'più di quello, ho ignorato lo spostamento del pivot dal momento che è già nella posizione corretta, ma tu dici di capire il partizionamento).

I Quicksorts in genere non forniscono alcuna garanzia particolare dove dopo la partizione i due 4 s saranno, e penso che la maggior parte delle implementazioni li invertirà. Ad esempio, se si usa Hoare's classic partitioning algorithm, la matrice viene partizionata come segue:

(1, ""), (2, ""), (3, ""), (4, "second"), (4, "first")

che viola la stabilità di smistamento.

Poiché ogni partizione non è stabile, è improbabile che l'ordinamento generale sia.

Come fa notare Steve314 in un commento, l'unione di ordinamento è stabile a condizione che durante l'unione, se si incontrano elementi uguali, si emette sempre per primo quello che viene dal "basso" delle due metà che si stanno unendo insieme . Cioè, ogni unione deve apparire come questa, dove la "sinistra" è il lato che viene dal basso nella matrice originale.

while (left not empty and right not empty): 
    if first_item_on_left <= first_item_on_right: 
     move one item from left to output 
    else: 
     move one item from right to output 
move everything from left to output 
move everything from right to output

Se il <= erano < poi l'unione non sarebbe stabile.

fonte

2012-11-21 17:15:52

+1 - si potrebbe aggiungere utilmente che in mergesort, il motivo per cui gli elementi uguali mantengono il loro ordine originale è perché in ogni unione, sai quale delle sequenze unite è arrivata prima nei dati originali - quando trovi elementi uguali, devi semplicemente selezionare quello dalla prima sequenza piuttosto che il secondo e l'ordinamento originale è preservato. Quindi, in un certo senso, gli elementi non sono uguali unione di WRT - l'unione applica un ordinamento basato sulla posizione originale quando i valori sono uguali. – Steve314

Molto utile - ha senso ora !! – IUnknown

Sarà come un utente ha una matrice ordinata e ordina da un'altra colonna, l'algoritmo di ordinamento conserva sempre l'ordine relativo degli elementi che differiscono per la chiave di ordinamento precedente ma hanno lo stesso valore nella nuova chiave di ordinamento ? Quindi, in un algoritmo di ordinamento che conserva sempre l'ordine degli elementi (che non differiscono nella nuova chiave di ordinamento) è chiamato "ordinamento stabile".

Please have a look of example