Læreplankoblet

LAST NED kopioriginaler

Sortert

Stikkord: Algoritmer Sortering Programmering

Aktivitet

Spillekort som er lagt usortert utover et bord.

Finn fram eller lag noen nummererte kort, mellom 10 og 20 er nok. Du kan for eksempel bruke alle kortene av én sort i en kortstokk (hjerter, ruter, kløver, spar).

Bland kortene og legg dem på bordet, sortert i stigende rekkefølge.

Hvilken metode brukte du for å legge dem i stigende rekkefølge?

Kan du komme på en annen metode å sortere kortene på?

Nedenfor er det beskrevet noen sorteringsalgoritmer som du kan prøve. Det kan være lurt å legge alle kortene i en rad på bordet, for at det skal være enkelt å holde oversikt over det som skjer.

Bubble sort

  • Sammenlign de to første kortene. Bytt om plasseringen deres hvis de ligger i feil rekkefølge.
  • Deretter sammenligner du det andre og det tredje kortet. Bytt om plasseringen deres hvis de ligger i feil rekkefølge.
  • Fortsett slik gjennom hele raden med kort.
  • Når du har gått gjennom alle kortene, lar du den nye rekkefølgen ligge og begynner forfra igjen.
  • Gjenta dette helt til du kan gå gjennom hele raden uten at noen kort må bytte plass.

Shuttle sort

  • Første gjennomgang: Sammenlign de to første kortene, og bytt om plasseringen deres om nødvendig.
  • Andre gjennomgang: Sammenlign det andre og det tredje kortet, og bytt om plasseringen deres om nødvendig. Sammenlign og bytt deretter om de to første kortene om nødvendig.
  • Tredje gjennomgang: Sammenlign det tredje og det fjerde kortet, og bytt om plasseringen deres om nødvendig. Sammenlign og bytt deretter om det andre og det tredje kortet om nødvendig. Sammenlign og bytt deretter om det første og det andre kortet om nødvendig.
  • Fortsett på samme måte gjennom hele raden.

Selection sort

  • Gå gjennom raden med kort helt til du finner eneren (ess om du bruker kortstokk). Bytt dette kortet med det første kortet i raden.
  • Deretter går du gjennom raden med kort til du finner toeren. Bytt dette kortet med det andre kortet i raden.
  • Gå gjennom raden med kort til du finner treeren. Bytt dette kortet med det tredje kortet i raden.
  • Fortsett slik med resten av kortene.

Insertion sort

  • Legg ned det første kortet.
  • Legg det andre kortet til høyre eller til venstre for det første kortet, avhengig av om tallverdien er høyere eller lavere.
  • Legg det tredje kortet på riktig plass i forhold til de to første kortene. Lag plass mellom de to første kortene om nødvendig.
  • Plasser det fjerde kortet korrekt i forhold til de tre første kortene. Lag plass mellom noen av kortene om nødvendig.
  • Fortsett slik til alle kortene er sortert i rekkefølge.

Quick sort

  • Legg ned det første kortet.
  • Sorter resten av kortene i en bunke som inneholder alle kortene med lavere tallverdi enn det første, og en bunke som inneholder alle kortene med høyere tallverdi enn det første.
  • Legg det første kortet mellom de to mindre bunkene med kort.
  • Sorter de mindre bunkene på samme måte.
  • Fortsett til det ikke er igjen flere bunker med kort.


Prøv hver algoritme noen ganger, og hold oversikt over hvor mange «trekk» eller «bytter» du utfører. Du kan også samarbeide med en annen og konkurrere om å sortere raskest.

Hvis du ikke helt skjønner noen av de skriftlige algoritmene, kan du se på filmene under Starthjelp, som viser algoritmene i praksis.

Her er noen spørsmål du kan arbeide med:

  • Hvilken algoritme er gjennomsnittlig raskest?
  • Hva er verst tenkelig utfall for hver algoritme? Hvilket utgangspunkt vil gi flest «trekk» eller «bytter»?
  • Hvor lang tid vil det ta å sortere ved verst tenkelige utgangspunkt?
  • Dersom du kan programmere litt, kan du lage et program som utfører disse algoritmene. Hvilken algoritme ville du valgt å programmere for å lage det mest mulig effektive programmet? Kan du få programmet til å holde oversikt over hvor mange «trekk» eller «bytter» det gjør i de forskjellige algoritmene?

Starthjelp

Bubble sort

Shuttle sort

Selection sort

Insertion sort

Quick sort

Lærerveiledning

Mulig tilnærming

Hver elev trenger alle kortene fra ess til konge av én sort i en kortstokk. Alternativt kan de bruke andre nummererte kort. «Bland kortene deres og legg dem i rekkefølge fra ess til konge. Se på hvordan andre sorterer kortene sine. Gjør dere det på samme måte? Hvor effektiv er måten din?»

Deretter kan du vise filmene under Starthjelp, eller dele ut kopioriginalen. Elevene bør forsøke å forstå algoritmene før de prøver dem selv.

«Gjennomfør hver algoritme noen ganger for å bli bedre kjent med den. Deretter velger du to algoritmer som du vil sammenligne. Hvilken er raskest? Hvorfor? Kan du plassere kortene dine i det verst tenkelige utgangspunktet for hver av de to algoritmene, for å få det til å ta så lang tid som mulig?»

Gi elevene tid til å utforske både spørsmålene nedenfor og spørsmålene i oppgaven eller kopioriginalen:

  • Hvilken algoritme synes du er gjennomsnittlig raskest?
  • Hva er verst tenkelige utfall for hver algoritme? Hvilket utgangspunkt vil gi flest «trekk» eller «bytter»?
  • Hvor lang tid vil det ta å sortere ved verst tenkelige utgangspunkt?

Diskuter funn og oppdagelser sammen med hele klassen.

Mulig utvidelse

Utfordre elevene til å skrive pseudokode eller programmere algoritmene med et programmeringsspråk de kjenner.

Mulig støtte

Introduser én algoritme om gangen. Nettsiden toptal.com (ekstern side) kan visualisere algoritmene, og kan hjelpe elevene med å forstå de forskjellige metodene.

Ressursen er utviklet av NRICH

9,10