Progblemet #7 - sortering
EDIT: och glömmer alltid skriva detta...
Progblemet är ingen fråga från min sida, det är en helt öppen diskussion kring någon ämne där alla är välkomna att ge sina egna bidrag eller ställa frågor. Tanken är att man ska kunna se hur lösningar på ett problem eller problemområde ser ut i en rad olika programmeringsspråk. Så visa gärna hur man skriver quick sort, shell sort, insert sort eller liknande i Python, C# eller något annat språk du råkar gilla!
Har varit väldigt mycket på jobbet och är fortfarande, så inte riktigt haft tid med något progblemet. Men har tittat in in denna del av forumet till och från och föga oväntat kommer det frågor kring sortering. Så varför inte köra ett progblemet på detta tema.
Det finns väldigt många olika sortering-algoritmer med väldigt olika egenskaper. Noterat att väldigt många frågar om bubble sort, en algoritm som förhoppningsvis aldrig förekommer i produktionskod men den är ändå intressant då implementationen av denna algoritm är typiskt väldigt enkel i språk som är besläktade med C.
Man brukar karakterisera sorteringsalgoritmer enligt följande egenskaper
Genomsnittlig tidskomplexitet, d.v.s. om det tar X s att sortera N element, hur lång tid borde det då ta att sortera 10*N element
Värsta möjligt tidskomplexitet, samma som ovan om man stoppar in den värsta tänkbara input
Utrymmeskomplexitet, hur mycket extra minne behövs för att utföra sorteringen
Lite ovanligare, men ibland specificerar man även hur många jämförelser och hur många gånger man måste flytta element som utförs i genomsnitt
Genomsnittlig tidskomplexitet är något man visar med "big-O notation". O(N^2) betyder då att tiden det tar att sortera växer kvadratiskt med storleken på indata medan O(N*log(N)) betyder att tiden växer lite snabbare än storleken på indata (lite förenklat).
Låt oss använda [4,3,1,2] som indata
Bubble-sort är en algoritm som garanterat sorterar in minst ett element på rätt plats varje gång man går igenom data. Det gör det till en O(N^2) algoritm, vilket i sin tur gör den olämplig att sortera något annat än väldigt små data-mängder. Processen är att jämföra två element, om det första elementet ska ligga längre bak så byter man plats på elementen. Om elementen är i rätt ordning jämför man nästföljande par o.s.v. till man når slutet. I det läget vet man att sista elementet ligger på rätt plats och man kan börja om från början.
[4,3,1,2] -> 4 > 3 så byt plats på elementen -> [3,4,1,2] -> [3,1,4,2] -> [3,1,2,4] nummer 4 är nu garanterat på rätt plats
[3,1,2,4] -> [1,3,2,4] -> [1,2,3,4] de två sista elementen är nu garanterat rätt
[1,2,3,4] -> elementen redan på rätt plats, så gå vidare men i detta fall är vi klara
En lite mer praktisk användbar algoritm är quick sort. Det är en algoritm som är O(N*log(N) i genomsnitt, men tyvärr O(N^2) om det vill sig illa. I praktiken går det nästan alltid att undvika det dåliga fallet om man tänker till lite. Denna fungerar så att man väljer ett avgränsnings element, sedan delar man upp indata i två delar
* mindre eller lika med avgränsningselementet
* större än avgränsningselementet
sedan sorterar man varje del för sig. Processen avbryts när indata är ett eller noll element, för i det läget är ju indata redan sorterat
[4,3,1,2] -> i detta fall väljs sista elementet som avskiljare -> [1] [4,3]
[1] är redan sorterad
[4,3] -> [] [4]
Vi har nu [1] 2 [] 3 [4] där de fristående avskiljarna nu ligger i variabler, detta slås ihop till [1,2,3,4]
Ett sista exempel här är merge sort som har den trevliga egenskapen att alltid vara O(N*log(N)). Så varför skulle man då någonsin välja quick sort? Problemet med merge sort är att den fungerar jättebra till länkade listor, men om man vill sortera arrayer så kräver merge sort extra utrymma motsvarande storleken på input, något quick sort inte kräver (bubble sort kräver inte heller det). Processen är att dela indata i två lika stora delar, något som repeteras till dess att indata är ett eller noll element stort
[4,3,1,2] -> [4,3] [1,2] -> [4] [3] [1] [2]
i detta läge kommer det som gett denna algoritm sitt namn, man måste nu sätta ihop alla delar (merge) i rätt ordning.
[] [4] [3] -> [3] [4] [] -> [3,4] [] []
[] [1] [2] -> [1] [] [2] -> [1,2] [] []
[] [3,4] [1,2] -> [1] [3,4] [2] -> [1,2] [3,4] [] -> [1,2,3] [4] [] -> [1,2,3,4] [] []
Om någon vill visa upp någon annan algoritm kan de ju skriva en kort förklaring om hur den fungerar!
Care About Your Craft: Why spend your life developing software unless you care about doing it well? - The Pragmatic Programmer