Sortering av algoritmer: Lær hvorfor du ikke bør bruke Bubblesort

Formidling: Din støtte hjelper med å holde nettstedet i gang! Vi tjener et henvisningsgebyr for noen av tjenestene vi anbefaler på denne siden.


Har du noen gang lurt på hvordan en datamaskin ordner ting? Når du klikker på A-Z-knappen i Excel, hva skjer egentlig?

Datamaskiner sorterer lister ved å følge prosedyrer som kalles “sorteringsalgoritmer.” En algoritme er et sett med instruksjoner som kan følges om og om igjen, mekanistisk. Det er flere forskjellige sorteringsalgoritmer – forskjellige prosedyrer for å sette lister i riktig rekkefølge. Hver og en har sine styrker og svakheter.

Her er de mest populære sorteringsalgoritmene.

Bubble Sort

Boblensortering er en ineffektiv, men enkel algoritme. Det brukes sjelden i praksis, men det er lett å forstå.

Boblensortering fungerer ved å sammenligne suksessive par elementer i en liste. Det første og det andre elementet sammenlignes, deretter det andre og det tredje, deretter det tredje og fjerde, og så videre gjennom listen. Etter hver sammenligning byttes de to elementene ut hvis de ikke er i orden. Etter en enkelt iterasjon vil det største elementet ha “boblet opp” til slutten av listen. Denne prosedyren gjentas om og om igjen til listen er sortert.

I den toveisvarianten gjøres sammenligninger vekselvis fremover gjennom listen og deretter bakover gjennom listen. Dette utvider en sortert seksjon i hver ende av listen. Dette kalles også “cocktail shaker sort.”

Når du skal bruke Bubble Sort

Aldri annet enn for demonstrasjon.

Mer informasjon om Bubble Sort

  • Bubble Sort forklaring fra algoritmen, med eksempelkode;
  • Bubble Sort Algorithm kodet på over 100 forskjellige programmeringsspråk;
  • Bubble Sort illustrert med Legos;
  • Bubble Sort illustrert med ungarsk folkedans.

Innleggssortering

Innleggssorteringen er hvordan de fleste intuitivt sorterer ting manuelt – for eksempel når de alfabetiserer papirer. Det innebærer å flytte hvert element på sin side til sin rette plass i en allerede sortert del.

Det første elementet i listen regnes som “sortert.” Da blir det andre elementet vurdert. Hvis det er større enn elementet før det, er det på riktig sted og utgjør en del av delen “sortert”. Ellers blir den flyttet bakover ett spor og sammenlignet med elementet bak. Elementet fortsetter å bevege seg bakover til det er i riktig posisjon innenfor den sorterte delen av listen. Denne prosedyren blir deretter gjentatt med det tredje, fjerde, femte elementet, og så videre.

Når skal du bruke Innleggssortering

Innføringssortering er vanligvis den raskeste løsningen for å sortere små lister (10 eller færre elementer), og utfører minst tilstrekkelig i mellomstore lister. Imidlertid kan det bli uoverkommelig tregt i større sett.

Innføringssortering fungerer også bra, selv i store sett, hvis listen allerede stort sett er sortert. Dette gjør det ideelt for å rydde opp i gamle menneskesorterte data, eller for å bruke i forbindelse med andre sorteringsalgoritmer. For eksempel er det vanlig å begynne med en rask sortering og deretter bytte til innsetting etter noen iterasjoner.

Mer informasjon om innsetting

  • Insertion Sorter forklaring og kodingsøvelse, ved Khan Academy;
  • Insertion Sort Algorithm kodet i nesten 100 forskjellige programmeringsspråk;
  • Insertion Sort illustrert med styrofoam kopper og fortalt av en Harvard CS-student;
  • Insertion Sort illustrert med ungarsk folkedans.

Heap Sort

Heapsorteringen er en todelt sortering som bruker en binær heapdatastruktur som en mellomliggende holder for elementene i listen.

En binær haug er en trestruktur der hver node har opptil to underordnede noder. Det største elementet er på toppen av treet. Hver underordnede node er mindre enn sin overordnede node. Dette betyr at prosessen med å bygge en haug delvis sorterer listen. Når dyngen er bygget, fjernes det største elementet og plasseres i den sorterte matrisen – deretter den største av den gjenværende dyngen, og så videre.

Når skal du bruke Heap Sort

I gjennomsnitt gir sorteringsgraden god ytelse. I tillegg er det verste fallet mye bedre enn det verste scenarioet for nesten hvilken som helst annen algoritme. Det blir derfor ofte brukt med store og distribuerte datasett.

Mer informasjon om Heap Sort

  • Detaljert forklaring av Heap Sort fra en CS-professor ved Kent State;
  • Heaps and Heap Sort Video-forelesning fra MIT;
  • Hvis du vil ha en dyptgående forståelse av hauger og haugesortering, kan du se denne femdelte videoserien.

Slå sammen sortering

Å slå sammen to allerede sorterte lister til en ny allerede sortert liste er relativt enkelt: sammenlign det første elementet i hver og legg de mindre inn i den nye listen, gjenta. Dette er grunnlaget for sammenslåingen.

For å starte en sammenslåingssortering blir en liste delt inn i et sett med 1-element “lister.” Deretter blir par av disse listene slått sammen til 2-elementslister, som deretter slås sammen til 4-elementslister, og så videre til hele listen er slått sammen igjen..

Når skal du bruke Merge Sort

Slå sammen sortering er veldig effektiv. Det eneste problemet er at flettesortering vanligvis krever nok aktivt minne (RAM) til å holde listen to ganger. Det kan derfor bli umulig under visse omstendigheter.

Mer informasjon om Merge Sort

  • Merge Sort fra Khan Academy er en utmerket seksdelt leksjon med programmeringsøvelser inkludert;
  • Merge Sort kodet på over 80 forskjellige programmeringsspråk;
  • Merge Sort with German Folk Dance gir en danserutine som demonstrerer sorteringsalgoritmen.

Rask sortering

Rask sortering er ikke veldig intuitiv. Det er imidlertid veldig effektivt.

Det første trinnet i en rask sortering er å velge et pivotelement. Dette kan være et hvilket som helst element i listen. Dernest blir alle verdier større enn pivoten plassert etter den, mens alle verdier mindre enn er plassert før den. Dette skaper to partisjoner som ikke er sortert, men som er i riktig forhold til hverandre. Den samme prosedyren gjøres på hver partisjon, deretter på hver underpartisjon, og så videre. Når partisjonene når en størrelse på ett element hver, blir listen sortert.

Når skal du bruke hurtig sortering

Rask sortering er en av de mest populære sorteringsalgoritmer for praktisk bruk. Gjennomsnittlig hastighet er veldig rask. Imidlertid blir det verste tilfellet (som sjelden skjer i naturlige datasett) problematisk med veldig store sett.

Mer informasjon om rask sortering

  • Rask sortering kodet på over 100 programmeringsspråk;
  • Rask sortering forklart med blokker fra Harvards CS-50-klasse;
  • Veiledning for hurtig sortering fra Tutorials Point har mange detaljer, prøvekoder og animerte bilder.

Generelle ressurser for sorteringsalgoritme

  • Datastruktur – sorteringsteknikker er en veldig detaljert serie fra Tutorials Point;
  • Sorteringsalgoritmer har visualiseringer av alle slag, under forskjellige forhold – du kan til og med se forskjellige algoritmer kappløpe hverandre;
  • 15 Sortering av algoritmer på 6 minutter er en fascinerende videovisualisering;
  • Å bli sortert er video som utforsker problemet med datastyrt sortering;
  • Hva forskjellige sorteringsalgoritmer høres ut er en utrolig “audibilization” -video som oversetter flere sorteringsalgoritmer til lyd.

Sammendrag

Det meste av tiden, når du programmerer, hvis du trenger noe trivielt sortert – et kort utvalg av verdier, en kolonne med data – vil du bare bruke hvilken metode eller funksjon som er innebygd i programmeringsspråket eller favorittbiblioteket ditt.

Men når du jobber med store dataprogrammer, er det viktig å tenke på hvordan valget av algoritme vil påvirke ytelsen til systemet ditt. Utover det er sorteringsalgoritmer et grunnleggende aspekt av informatikk, og bør forstås godt av alle som jobber med utvikling eller programmering.

Videre lesing og ressurser

Vi har flere guider, veiledninger og infografikk relatert til koding og utvikling:

  • C ++ Utviklerressurser: et av de mest populære programmeringsspråk, bra for de fleste applikasjoner.
  • Unicode Introduksjon og ressurser: lære alt om karakterkoding.
  • MantisBT Introduksjon og ressurser: MantisBT er et av de mest populære bug tracking programmene.

Hvilken kode skal du lære?

Forvirret om hvilket programmeringsspråk du bør lære å kode på? Ta en titt på infografien vår, hvilken kode skal du lære? Den diskuterer ikke bare forskjellige sider av språkene, den svarer på viktige spørsmål som “Hvor mye penger vil jeg tjene på å programmere Java for å leve?”

Hvilken kode skal du lære?
Hvilken kode skal du lære?

Jeffrey Wilson Administrator
Sorry! The Author has not filled his profile.
follow me
    Like this post? Please share to your friends:
    Adblock
    detector
    map