(Finns – eventuellt – en poäng i slutet även för den som inte är så värst intresserad av hur man kan sortera grejer…)
Häromveckan fick jag för mig att implementera en sorteringsalgoritm från scratch, lite som en övning, dvs en liten kodsnutt som ordnar en sekvens av saker så de hamnar minst till störst.
Att göra någonting sånt är egentligen meningslöst. Det finns super-optimerade sorteringsfunktioner redo att använda i vartenda programspråk. Att implementera själv är oftast, om man inte har något speciellt problem, bara slöseri med tid.
Jag testade iaf att slänga ihop en s k quicksort. Och det gick ju alldeles utmärkt. Ett par, tre minuter och det funkade på första försöket. Oj. Att jag minns vad quicksort var ens, utan att kolla upp den eller någonting.
(Quicksort: välj ett element – ett pivotelement – från sekvensen, lägg allt som är mindre i en hög och sortera den enligt quicksort, lägg allt som är större i en hög och sortera den enligt quicksort. Resultatet är den mindre högen följt av allt som är pivotelementet eller lika följt av den större högen.)
Så jag testade att göra om det, men öh… mergesort. Jamen det minns jag ju också. Och det var också lätt. Två, tre minuter, funkade på första. Oj. Jaha. Lite förvånad.
(Mergesort: dela upp sekvensen i två högar, spelar inte så stor roll hur. Högarna kör du mergesort på. Sen tittar du om och om igen på det minsta elementet i båda högarna och plockar det minsta av de två till din resultatsekvens. Tar en hög slut innan den andra, lägg på det som är kvar till resultatet. Klart!)
Quicksort och mergesort är två väldigt bra – effektiva – sätt att sortera på (och sortera är ju någonting fundamentalt för datorer). Industristandard sen datorernas barndom. Men kanske inte den första sorteringsalgoritm man brukar få implementera som student, även om man inte ska överdriva svårighetsgraden. Förmodligen har det att göra med att de är rekursiva – dvs använder anrop till sig själva i sin definition.
Men lite nyfiken blev jag. Så jag gav mig på nybörjarnas sorteringsalgoritm. Den som alla får testa att implementera det första de gör, för att den är så enkel. Bubblesort. Den är dock väldigt ineffektiv och duger egentligen inte till så mycket annat än just nybörjarövning.
Bubblesort var… kanske inte svår, men tog ett tag att få rätt. Märkligt. Varför är quicksort och mergesort pissenkla att implemtera om bubblesort, som ska vara pissenkel, ger mig bryderier?
(Bubblesort: gå igenom sekvensen element för element, jämför med grannen och byt plats vid behov. Upprepa tills du gått igenom hela sekvensen utan att göra något byte.)
Jaha. Fått blodad tand – och bryderier – så jag implementerade en selection sort (egentligen värdelös i praktiken) och insertion sort (som är effektiv för kortare sekvenser). Också knepigare att få till än quicksort och mergesort.
(Selectionsort: leta upp minsta elementet i sekvensen, lägg till som största elementet i din resultatsekvens. Upprepa tills du inte har något kvar att sortera.)
(Insertionsort: plocka ut nästa element i din insekvens och stoppa in det på rätt plats i en resultatsekvens som till slut innehåller alla element.)
Funderade mer varför jag upplevde de icke-rekursiva bubblesort, selectionsort och insertionsort som knepigare. Skrev ett par nya varianter där jag gjorde insertionsort eller om det var selectionsort rekursiv, dvs använde anrop till sig själv i definitionen. Gjorde om de versionerna till iterativa igen, på andra sätt.
Skrev väl 10 olika sorteringsalgoritmer på en timme. Funderade en hel del. Lärde mig en del, trots att ingenting egentligen var någonting nytt.
Jaha.
Programmerare gör såhär ibland. Tränar ibland på egentligen simpla saker. Går tillbaka till början. Varför – på riktigt! – blir det si om man gör så? Utmanar sig själv att lösa ett problem på ett annat sätt. Och ett till. Ett till. Ett till. Ett till. Ett till. Tills man inte kan lösa det på något nytt sätt. osv osv
Det kallas för kodkatas.
Kommer från det japanska ordet för form: “kata”. Norm. Sätt att göra saker.
Inom olika kampsporter har man ju ofta en massa kända katas – sekvenser av slag och sparkar, blockeringar, kast av tänkta motståndare. För att gradera till olika bälten krävs det ofta att man kan utföra vissa förutbestämda katas på ett tillfredsställande sätt.
Programmeringen har hämtat ordet från kampsporten.
Undrar om man håller på såhär inom andra konstformer, hantverk?
En författare eller journalist, som skriver människospråk exempelvis… utmanar de sig någonsin att skriva en kort nyhetsnotis om någonting? För att sedan skriva om samma sak som en krönika? Ett rent referat? Som om Björn Ranelid hade skrivit det? Som en tweet? Utan bokstaven e? Som en haiku eller fri vers? Som någonting som skulle funka i tv?