Cosa significa per un algoritmo di ordinamento essere "stabile"?

Un ordinamento stabile è quello che conserva l'ordine originale dell'insieme di input, dove l'algoritmo di confronto non distingue tra due o più elementi.

Considera un algoritmo di ordinamento che ordina le carte per grado , ma non per seme. L'ordinamento stabile garantirà che l'ordine originale delle carte con lo stesso valore sia preservato; l'ordinamento instabile no.

Gli algoritmi stabili preservano l'ordine relativo degli elementi.

Quindi un algoritmo di ordinamento stabile manterrà l'ordine relativo di valori che si equivalgono.

Considera un algoritmo di ordinamento in cui ordiniamo una raccolta di punti 2D in base alla loro dimensione X.

Raccolta da ordinare: {(6, 3), (5, 5), (6, 1), (1, 3)}

Stable Sorted: {(1, 3), (5, 5), (6, 3), (6, 1)}

Ordinato regolarmente: O {(1, 3), (5, 5), (6, 3), (6, 1)} o {(1, 3), (5, 5), (6, 1), (6, 3)}

Per quanto riguarda il compromesso ... beh, l'ordinamento stabile è meno efficiente, ma a volte ne hai bisogno.

Ad esempio, quando un utente fa clic sull'intestazione di una colonna per ordinare i valori in un'interfaccia utente, è ragionevole aspettarsi che il suo ordine di ordinamento precedente venga utilizzato nel caso di valori uguali.