Stabilitet i sorteringsalgoritmer - en behandling af lighed

Algoritmer er kernen i datalogi. Algoritmer, der bruges til sortering, er nogle af de mest fundamentale, nyttige og følgelig allestedsnærværende.

Algoritme - et endeligt sæt af entydige trin til løsning af et specifikt problem.

Vi sorterer konstant og ofte ubevidst på rækkefølgen af ​​grupperede objekter. For eksempel rangerer vi opgaver på en liste efter prioritet. Vi stabler bøger i hylder efter deres højde. Vi sorterer rækker i et regneark eller en database eller stoler på den alfabetiske rækkefølge af ord i en ordbog. Nogle gange opfatter vi endda en bestemt slags skønhed i ordnede arrangementer.

Som programmører er det vigtigt at vide, hvordan vi sorterer, fordi det påvirker, hvordan et sorteret arrangement kan se ud. Ikke alle slags ordrer genstande på samme måde! På grund af dette er resultaterne af sorteringsoperationer forskellige afhængigt af de anvendte algoritmer. Hvis dette ikke anerkendes, overrasker vi måske os selv eller de mennesker, der bruger vores software.

Stabiliteten af ​​sorteringsalgoritmer er en af ​​de kendetegnende egenskaber blandt dem. Det handler om, hvordan algoritmen behandler sammenlignelige emner med lige sorteringstaster.

Sorteringstast - En nøgle, der bruges til at bestemme rækkefølgen af ​​varer i en samling, f.eks. Alder, højde, placering i alfabetet osv.

En stabil sorteringsalgoritme opretholder den relative rækkefølge på elementerne med lige sorteringstaster. En ustabil sorteringsalgoritme gør det ikke. Med andre ord, når en samling sorteres med en stabil sorteringsalgoritme, bevarer varer med de samme sorteringstaster deres rækkefølge, efter at samlingen er sorteret.

Et eksempel, kode og en demo

Billedet ovenfor illustrerer effekten af ​​en stabil sortering. Til venstre blev dataene sorteret alfabetisk efter navn. Efter at have sorteret dataene efter karakter, kan du se, at den alfabetiske rækkefølge af navnene blev opretholdt for hver række med samme karakter.

Med en ustabil sortering er der ingen garanti for, at den alfabetiske rækkefølge opretholdes som vist på billedet ovenfor.

Du har ikke altid brug for en stabil sortering

Det er særlig vigtigt at vide, om den slags, du bruger, er stabil. Især i situationer, hvor dine data allerede har en rækkefølge, som du gerne vil opretholde, når du sorterer dem med en anden sorteringsnøgle. For eksempel har du rækker i et regneark, der indeholder elevdata, der som standard er sorteret efter navn. Du vil også gerne sortere det efter karakterer, mens du opretholder den sorterede rækkefølge på navnene.

På den anden side betyder sorteringens stabilitet ikke noget, når sorteringstasterne på objekterne i en samling er objekterne selv - f.eks. En række heltal eller strenge - fordi vi ikke kan se forskellen mellem de duplikerede nøgler.

// JavaScript
// $5 bucks if you can correctly tell which 4 in the sorted// array was the first 4 when the array was unsorted.
var numbers = [5, 4, 3, 4, 9];numbers.sort(); // [3, 4, 4, 5, 9]
// A one second trip around the world, courtesy of the Flash, to// whomever correctly tells me which 'harry' in the sorted array was// the second 'harry' in the unsorted array.
var names = ['harry', 'barry', 'harry', 'cisco'];names.sort(); // ['barry', 'cisco', 'harry', 'harry']

Sort er overalt - kend din slags

Det er ret nemt at finde ud af, om standardsorteringen i dit programmeringssprog eller bibliotek er stabil. Dokumentationen skal indeholde disse oplysninger. For eksempel er standardsortering stabil i Python, ustabil i Ruby og udefineret? i JavaScript (det afhænger af browserens implementering).

Her er et par almindelige sorteringsalgoritmer og deres stabilitet:

  • Insertion Sort - Stabil
  • Valg af sortering - ustabil
  • Boblesortering - stabil
  • Flet sortering - stabil
  • Shell Sort - ustabil
  • Timsort - Stabil

Se Wikipedia for en mere udtømmende liste.

Er det demo-tid? ‍?

Denne demo viser effekten af ​​at bruge en stabil (indsættelsessortering) og ustabil sorteringsalgoritme (udvælgelsessortering) til at sortere en lille datatabel. Jeg havde lidt sjov og praktisk talt reverse engineered React, mens jeg byggede dette. Se på kilden.

Hvad er det næste?

Hvis du er tørstig efter mere viden om stabiliteten i andre sorteringsalgoritmer, har Wikipedia en god sammenligningstabel og yderligere oplysninger om kendte sorteringsalgoritmer.

Indtil næste gang fred.

Lærte du noget nyt eller nød at læse denne artikel? Klap det op? Del det, så andre også kan læse, og følg efter for mere. Du er også velkommen til at efterlade en kommentar.