Qualcuno può spiegare cosa significhi "stabile" e "instabile" in relazione a vari algoritmi di ordinamento> Come si può determinare se un algoritmo è stabile o meno, e quali applicazioni hanno solitamente algoritmi di ordinamento instabili (poiché sono instabili)?Qual è il significato di "stabile" e "instabile" per vari algoritmi di ordinamento?
Se un algoritmo di ordinamento si dice "instabile", ciò significa che per tutti gli articoli che si classificano allo stesso modo, non è garantito che l'ordine dei membri legati rimanga lo stesso con i successivi tipi di quella raccolta. Per un ordinamento "stabile", le voci legate finiscono sempre nello stesso ordine quando vengono ordinate.
Per un esempio di applicazioni, l'algoritmo di ordinamento rapido non è stabile. Ciò funzionerebbe bene per qualcosa come ordinare le azioni in base alla priorità (se due azioni hanno la stessa priorità, non è probabile che ti preoccupi di quali elementi di un legame vengono eseguiti per primi).
Un algoritmo di ordinamento stabile, d'altra parte, è buono per cose come una classifica per un gioco online. Se si dovesse utilizzare un ordinamento instabile, ordinando per punti (ad esempio), un utente che visualizza i risultati ordinati in una pagina Web potrebbe riscontrare risultati diversi in caso di aggiornamento della pagina e operazioni come il paging dei risultati non funzionerebbero correttamente.
modificato per includere alcuni esempi del motivo per cui la differenza è importante. –
Gli ordinamenti inutili di solito producono risultati prevedibili, ovvero non danno risposte diverse in base agli stessi dati. Pertanto, gli aggiornamenti delle pagine mostreranno solo un ordine diverso per gli uguali quando cambiano altri valori. La causa dell'instabilità è nell'uso di alberi o di una struttura di dati simile quando si organizzano i dati. –
Vale la pena notare che un uso più comune di ordinamenti stabili è l'ordinamento in base a più chiavi. Ad esempio, se hai una serie di oggetti che rappresentano persone e vuoi che siano ordinati in base alla loro età, con legami spezzati dai nomi (alfabetici), puoi ordinare prima per nome e poi per età, e un ordinamento stabile dovrebbe avere nello stato che stai cercando. –
Un ordinamento stabile conserva l'ordine degli elementi identici. Qualsiasi tipo può essere reso stabile aggiungendo l'indice di riga alla chiave. Gli ordinamenti instabili, come l'ordinamento heap e l'ordinamento rapido, ad esempio, non hanno questa proprietà intrinsecamente, ma vengono utilizzati perché tendono ad essere più veloci e più facili da codificare rispetto agli ordinamenti stabili. Per quanto ne so non ci sono altri motivi per usare tipi instabili.
Andando al punto sopra che Azron aveva fatto (sotto il tuo punto) e l'esempio che ha preso, questo significa che l'ordinamento della griglia che facciamo in Windows è implementato in uno dei tipi stabili? Grid sorting significa, ordinare i file nella cartella per data e tipo. –
gli ordinamenti fatti in cose come il file manager e Excel sono stabili, o usano un ordinamento stabile o la versione stabilizzata di uno degli ordinamenti instabili. –
Forse questo sarebbe più appropriato su http://programmers.stackexchange.com/ –