Stabilitet i sorteringsalgoritmer - en behandling av likhet

Algoritmer er kjernen i informatikk. Algoritmer som brukes til sortering er noen av de mest grunnleggende, nyttige og følgelig allestedsnærværende.

Algoritme - et endelig sett med entydige trinn for å løse et spesifikt problem.

Vi sorterer og stoler kontinuerlig og ofte ubevisst på rekkefølgen på grupperte objekter. For eksempel rangerer vi oppgaver på en liste etter prioritet. Vi stabler bøker i hyllene etter høyden. Vi sorterer rader i et regneark eller en database, eller stoler på den alfabetiske rekkefølgen av ord i en ordbok. Noen ganger oppfatter vi til og med en viss skjønnhet i bestilte arrangementer.

Som programmerere er det viktig å vite hvordan vi sorterer fordi det påvirker hvordan et sortert arrangement kan se ut. Ikke alle slags bestiller gjenstander på samme måte! På grunn av dette varierer resultatene av sorteringsoperasjoner basert på algoritmene som brukes. Hvis dette ikke blir godkjent, kan vi overraske oss selv eller menneskene som bruker programvaren vår.

Stabiliteten til sorteringsalgoritmer er en av de karakteristiske egenskapene blant dem. Den tar for seg hvordan algoritmen behandler sammenlignbare elementer med like sorteringstaster.

Sorteringstast - En nøkkel som brukes til å bestemme rekkefølgen på varer i en samling, f.eks. Alder, høyde, posisjon i alfabetet, etc.

En stabil sorteringsalgoritme opprettholder den relative rekkefølgen på elementene med like sorteringstaster. En ustabil sorteringsalgoritme gjør det ikke. Med andre ord, når en samling er sortert med en stabil sorteringsalgoritme, bevarer elementer med de samme sorteringstastene sin rekkefølge etter at samlingen er sortert.

Et eksempel, kode og en demo

Bildet over illustrerer effekten av en stabil sortering. Til venstre ble dataene sortert alfabetisk etter navn. Etter å ha sortert dataene etter karakter, kan du se at den alfabetiske rekkefølgen på navnene ble opprettholdt for hver rad med samme karakter.

Med en ustabil sortering er det ingen garanti for at den alfabetiske rekkefølgen opprettholdes som vist på bildet ovenfor.

Du trenger ikke alltid en stabil sortering

Det er spesielt viktig å vite om sorten du bruker er stabil. Spesielt i situasjoner når dataene dine allerede har en viss orden som du vil opprettholde når du sorterer dem etter en annen sorteringsnøkkel. For eksempel har du rader i et regneark som inneholder studentdata som standard er sortert etter navn. Du vil også sortere det etter karakterer mens du opprettholder den sorterte rekkefølgen på navnene.

På den annen side, betyr ikke stabiliteten til sorten når sorteringstastene til objektene i en samling er objektene selv - for eksempel en rekke heltall eller strenger - fordi vi ikke kan se forskjellen mellom de dupliserte nøklene.

// 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']

Sorter er overalt - vet hva slags du er

Det er ganske enkelt å finne ut om standardsorteringen i programmeringsspråket eller biblioteket ditt er stabilt. Dokumentasjonen skal inneholde denne informasjonen. For eksempel er standard sortering stabil i Python, ustabil i Ruby, og udefinert? i JavaScript (det avhenger av nettleserens implementering).

Her er noen vanlige sorteringsalgoritmer og deres stabilitet:

  • Sortering av innsetting - stabil
  • Valgsortering - ustabil
  • Boblesortering - Stabil
  • Merge Sort - Stable
  • Shell Sort - ustabil
  • Timsort - Stabil

Se Wikipedia for en mer uttømmende liste.

Det er demo-tid? ‍?

Denne demoen viser effekten av å bruke en stabil (innsettingssortering) og ustabil sorteringsalgoritme (utvalgssortering) for å sortere en liten tabell med data. Jeg hadde det litt gøy og praktisk talt omvendt konstruert React mens jeg bygde dette. Ta en titt på kilden.

Hva blir det neste?

Hvis du er tørst etter mer kunnskap om stabiliteten til andre sorteringsalgoritmer, har Wikipedia en god sammenligningstabell og tilleggsinformasjon om kjente sorteringsalgoritmer.

Inntil neste gang, fred.

Lært noe nytt eller likte å lese denne artikkelen? Klapp det sammen? Del det slik at andre også kan lese, og følg med på mer. Legg gjerne igjen en kommentar også.