Algoritme

Sammenligning af algoritmer

Der er som regel mere end én måde at løse et problem på. Der kan være mange forskellige opskrifter på en bestemt ret, som ser forskellig ud, men som i sidste ende smager ens. Det samme gælder for algoritmer. Nogle af disse måder vil dog være bedre end andre. Hvis en opskrift kræver en masse komplicerede ingredienser, som du ikke har, er den ikke så god som en simpel opskrift. Når vi ser på algoritmer som en måde at løse problemer på, ønsker vi ofte at vide, hvor lang tid det ville tage en computer at løse problemet ved hjælp af en bestemt algoritme. Når vi skriver algoritmer, vil vi gerne have, at vores algoritme tager mindst mulig tid, så vi kan løse vores problem så hurtigt som muligt.

I madlavning er nogle opskrifter sværere at lave end andre, fordi det tager længere tid at lave dem eller fordi der er flere ting at holde styr på. Det er det samme med algoritmer, og algoritmer er bedre, når de er lettere for computeren at udføre. Det, der måler en algoritmes sværhedsgrad, kaldes kompleksitet. Når vi spørger, hvor kompleks en algoritme er, ønsker vi ofte at vide, hvor lang tid det vil tage en computer at løse det problem, vi ønsker, at den skal løse.

Sortering

Dette er et eksempel på en algoritme til at sortere kort med farver i bunker af samme farve:

1. Saml alle kortene op.
2. Vælg et kort fra din hånd, og se på kortets farve.
3. Hvis der allerede er en bunke med kort i den farve, skal du lægge dette kort på bunken.
4. Hvis der ikke er nogen bunke kort af den pågældende farve, skal du lave en ny bunke med netop denne kortfarve.
5. Hvis der stadig er et kort på hånden, skal du gå tilbage til andet trin.
6. Hvis der ikke stadig er et kort på din hånd, sorteres kortene. Du er færdig.

Sortering efter numre

Dette er eksempler på algoritmer til at sortere en stak kort med mange forskellige numre, så numrene er i rækkefølge.

Spillerne starter med en stak kort, som ikke er blevet sorteret.

Første algoritme

Denne algoritme gennemgår stakken af kort, ét kort ad gangen. Dette kort sammenlignes med det næste kort i stakken. Bemærk venligst, at denne position kun ændres i trin 6. Denne algoritme kaldes bubblesort. Den er langsom.

1. Hvis stakken af kort er tom, eller hvis den kun indeholder ét kort, er den sorteret, og du er færdig.
2. Tag stakken af kort. Kig på det første kort (det øverste) i stakken.
3. Det kort, du ser på, er kort A. Den position, hvor kort A befinder sig i øjeblikket, er i stak P.
4. Hvis der ikke er flere kort i stakken efter kort A, skal du gå til trin 8.
5. Det næste kort i stakken er kort B.
6. Hvis kort B har et lavere tal end kort A, skal du bytte om på kortene A og B. Husk, at du har gjort det. Når du bytter kort, må du ikke ændre positionen P.
7. Hvis der er et andet kort i stakken efter position P, skal du se på det; gå tilbage til trin 3.
8. Hvis du ikke har byttet om på nogen kort i den sidste runde, er du færdig; stakken af kort er sorteret.
9. Ellers skal du gå tilbage til trin 2.

Trin-for-trin eksempel

Lad os tage en stak kort med tallene "5 1 4 2 2 8" og sortere dem fra det mindste tal til det største ved hjælp af denne algoritme. I hvert trin sammenligner algoritmen de elementer, der er skrevet med fed skrift, med hinanden. Den øverste del af stakken af kort er i venstre side.

Første gennemløb:
( 5 1 4 2 8 ) → {\displaystyle \to } ( 1 5 4 4 2 8 ) Her sammenligner algoritmen de to første elementer og bytter dem.
( 1 5 4 2 8 ) → {\displaystyle \to } ( 1 4 5 5 2 8 )
( 1 4 5 2 8 ) → {\displaystyle \to } ( 1 4 2 5 5 8 )
( 1 4 2 5 5 8 ) → {\displaystyle \to } ( 1 4 2 5 5 8 ) Disse elementer er allerede i rækkefølge, så algoritmen bytter dem ikke.
Anden gennemløb:
( 1 4 2 5 8 ) → {\displaystyle \to } ( 1 4 2 5 8 )
( 1 4 2 5 8 ) → {\displaystyle \to } ( 1 2 4 5 5 8 )
( 1 2 4 5 5 8 ) → {\displaystyle \to } ( 1 2 4 5 5 8 )
( 1 2 4 5 5 8 ) → { {\displaystyle \to } ( 1 2 4 5 5 8 )
Nu er stakken af kort allerede sorteret, men det ved vores algoritme ikke. Algoritmen har brug for en hel omgang uden bytte for at vide, at den er sorteret.
Tredje gennemløb:
( 1 2 4 5 5 8 ) → {\displaystyle \to } ( 1 2 4 5 5 8 )
( 1 2 4 5 5 8 ) → {\displaystyle \to } ( 1 2 4 5 5 8 )
( 1 2 4 5 5 8 ) → {\displaystyle \to } ( 1 2 4 5 5 8 )
( 1 2 4 5 5 8 ) → { {\displaystyle \to } ( 1 2 4 5 5 8 )
Endelig er arrayet sorteret, og algoritmen kan stoppe.

Historie

Dette er en letforståelig algoritme til sortering. Computerforskere kaldte den Bubble sort, fordi mindre elementer vil stige til tops og ændre deres position ved hver kørsel. Desværre er algoritmen ikke særlig god, fordi det tager lang tid (mange gennemgange af kortbunken) at sortere den.

Anden algoritme

Denne algoritme anvender en anden idé. Nogle gange er det svært at løse et problem, men problemet kan ændres, så det består af enklere problemer, der er nemmere at løse. Dette kaldes rekursion. Det er vanskeligere at forstå end det første eksempel, men det giver en bedre algoritme.

Grundlæggende idé

1. Hvis der ikke er nogen kort i stakken, eller hvis der kun er ét kort i den, er den sorteret, og du er færdig.
2. Del stakken af kort i to halvdele af nogenlunde samme størrelse. Hvis der er et ulige antal kort, vil den ene af de to stakke have et kort mere end den anden.
3. Sorter hver af de to stakke ved hjælp af denne algoritme (start ved punkt 1 i listen for hver stak).
4. De to sorterede stakke slås sammen som beskrevet nedenfor.
5. Resultatet er en sorteret stak kort. Du er færdig.

Sammenlægning af to stakke

Dette fungerer med to stakke kort. Den ene stak hedder A, den anden hedder B. Der er en tredje stak, som er tom i starten og hedder C. Til sidst vil den indeholde resultatet.

1. Hvis enten stak A eller stak B er tom, skal du lægge alle kortene fra den stak, der ikke er tom, oven på stak C. Du er færdig, og stak C er resultatet af sammenlægningen. (Bemærk: tag hele stakken og læg den på stak C; hvis du gør det kort for kort, vil rækkefølgen blive ændret, og det vil ikke fungere som det skal).
2. Se på de øverste kort i stak A og stak B. Læg det kort med det laveste tal oven på stak C. Hvis stak C ikke havde nogen kort, har den nu et kort.
3. Hvis der er kort tilbage i enten stak A eller stak B, skal du gå tilbage til trin 1 for at sortere dem.

Historie

John von Neumann udviklede denne algoritme i 1945. Han kaldte den ikke for sortering efter tal, men for Mergesort. Det er en meget god algoritme til sortering sammenlignet med andre algoritmer.

Tredje algoritme

Den første algoritme tager meget længere tid at sortere kortene end den anden, men den kan forbedres (gøres bedre). Når man ser på bobelsortering, kan det bemærkes, at kort med høje numre bevæger sig ret hurtigt fra toppen af stakken, men kort med lave numre nederst i stakken tager lang tid om at komme op (bevæge sig til toppen). For at forbedre den første algoritme er følgende ideen:

I stedet for at sammenligne to kort, der ligger ved siden af hinanden, vælges der i starten et "særligt" kort. Alle de andre kort sammenlignes derefter med dette kort.

1. Vi starter med en stak A. Der vil være to andre stakke B og C, som vil blive oprettet senere.
2. Hvis stak A ikke har nogen kort, eller hvis den kun har ét kort, er vi færdige med at sortere.
3. Der tages et kort fra stak A, om muligt tilfældigt. Dette kaldes en pivot.
4. Alle de resterende kort i stak A sammenlignes med dette omdrejningspunkt. Kort med et mindre tal går til bunke B, og kort med et lige stort eller større tal går til bunke C.
5. Hvis der er kort i stak B eller C, skal disse stakke sorteres med samme algoritme (start ved pos. 1 på denne liste for både stak B og C).
6. Færdig. Den sorterede stak kort har først den sorterede stak B, derefter omdrejningspunktet og derefter den sorterede stak C.

Historie

Denne algoritme blev udviklet af C.A.R. Hoare i 1960. Det er en af de mest udbredte algoritmer til sortering i dag. Den kaldes Quicksort.

Den tredje algoritme til sortering af kort. Det element med den røde streg vælges som omdrejningspunkt. I starten er det elementet helt til højre. Denne algoritme kaldes Quicksort.


Animation, der viser, hvordan en bobelsortering fungerer


Sortering af 7 tal ved hjælp af den anden algoritme til sortering efter tal (Mergesort)

Sammensætning af algoritmer

Hvis spillerne har kort med farver og tal på, kan de sortere dem efter farve og tal, hvis de udfører algoritmen "sortering efter farver", derefter udfører algoritmen "sortering efter tal" på hver farvet stak og derefter lægger stakkene sammen.

Algoritmerne til sortering efter tal er vanskeligere at udføre end algoritmerne til sortering efter farver, fordi de måske skal udføre trinene igen mange gange. Man kan sige, at sortering efter tal er mere kompleks.

Relaterede sider

• Den euklidiske algoritme blev fundet for over 2000 år siden. Den er i stand til at finde den største fælles divisor af to tal.