Perché la selezione non è stabile?

Question

Questo potrebbe essere banale, ma non capisco perché l'implementazione predefinita di Selection Sort non sia stabile?

A ogni iterazione si trova l'elemento minimo nell'array rimanente. Quando trovi questo minimo, puoi scegliere il primo minimo che trovi e aggiornarlo solo quando un elemento è effettivamente più piccolo di quello. Quindi, l'elemento scelto ad ogni iterazione è il primo minimo - cioè, è il primo nell'ordinamento precedente. Quindi, a quanto mi risulta, l'ordinamento corrente non distruggerà un ordine generato da un ordinamento precedente su elementi uguali.

Cosa mi manca?

Answer 1

Un piccolo esempio:

Sia b = B in

< B>, < b>, < a>, < C> (con un < b < c)

Dopo un ciclo la sequenza è ordinata ma l'ordine di b e b è cambiato:

< a>, < b>, < b >, < c>

Ma è comunque possibile implementare selezioni Ordina stabile se, invece di commutare, inserire il valore minimo. Ma affinché ciò sia efficace, dovresti avere una struttura dati che supporti l'inserimento a un costo basso o altrimenti si finisce con la complessità quadratica.

Answer 2

Il problema è che l'ordinamento di selezione scambia elementi dalla parte anteriore dell'array nel punto lasciato libero dall'elemento minimo, che può rovinare l'ordine ordinato. Ad esempio, supponiamo che io sto ordinamento

(4, 0), (4, 1), (1, 0) 

Selezione sorta prima scambia la (1, 0) al fronte:

(1, 0), (4, 1), (4, 0) 

E ora la (4, 0) e (4, 1) sono fuori uso da dove sono iniziati nel genere. Eseguendo questo a completamento lascia gli elementi in questo ordine, e i 4 sono fuori uso.

Spero che questo aiuti!

Answer 3

Il mezzo stabile non calcola ulteriormente se gli elementi sono già ordinati, ma calcola fino alla fine, quindi non è stabile.