In
English
In
EnglishHemsida: http://fy.chalmers.se/~f96hajo/old
E-post: f96hajo@chalmers.se Eller använd ett formulärProgrammet visar hur en lista med olika element (representerade med olika höjd och färg) sorteras med olika sorteringsalgoritmer, d.v.s. demonstrerar sorteringsalgoritmerna i aktion. Då en sorteringsalgoritm arbetar räknas antalet jämförelser mellan element och antalet byten av element som sker.
Anger pausen efter varje byte/kopiering av element. Snabbare åt höger.
Anger hur många element som listan skall innehålla. Värden 1 - 10 000 är giltiga. Tryck på Enter/Retur för att genomföra en förändring.
Slumpar om värdena (höjd och färg) på elementen.
Slumpar om värdena (höjd och färg) på elementen. Gör så att fler element än vanligt i samma färg får samma höjd.
Vänder listan bak-och-fram.
Sparar den aktuella listan. Informationen går förlorad om antalet element ändras.
Använder den sparade listan som aktuell lista. Detta är användbart då man vill jämföra olika sorteringsalgoritmer, eftersom en omslumpning av listan ger annorlunda förutsättningar.
Sorterar elementen efter värde (höjd).
Sorterar elementen efter färg. Om man först sorterar elementen efter värde (höjd) och sedan efter färg kan man ta reda på om en sorteringsalgoritm är stabil.
Används då man inte orkar vänta på att en sorteringsalgoritm skall terminera.
Starta sorteringen genom att välja en sorteringsmetod.
comp anger antalet utförda jämförelser och swap antalet utförda byten av element. Ju färre, dess bättre.
Sorteringsmetodernas
tidsåtgång anges med ordo-notation, O(n), dvs storleksordning.
Måttet kan inte användas för att jämföra tider
som olika algoritmer använder, men däremot kan notationen ange
hur intelligent eller slug en algoritm är. Om man känner till
tids-komplexiteten för en algoritm (t.ex. att BubbleSort harO(n2)),
och tiden för att genomföra algoritmen för ett problem av
storleken n (t.ex. liststorleken = n), kan man gissa sig till vilken tid
det tar för en annan problemstorlek.
Man brukar kalla sorteringsalgoritmer med en tidskomplexitet på O(n2) för enkla och de med en tidskomplexitet på O(n log n) för avancerade. För större problem kan man även använda beskrivningen: O(n2) - synnerligen meningslös, O(n log n) - användbar och O(n!) - bara dum :-).
En
sorteringsalgoritm sägs vara stabil om den inte byter inbördes
ordning på element med samma sorteringsnyckel vid sortering. T.ex.
om elementen först sorterats efter höjd och sedan sorteras efter
färg, är metoden stabil om elementen efteråt inom varje
färg fortfarande är sorterade m.a.p. höjd.
| Algoritm | Metod | Tidsåtgång | Stabil |
| BubbleSort | Itererar genom listan upprepade gånger och jämför vid varje steg två grannar. Om de är i fel ordning byter de plats. Ovan har metoden implementerats så att det minsta elementet bubblar ner vid varje iteration. |
O(n2) |
Ja |
| Alternating BubbleSort | Itererar genom listan upprepade gånger och jämför vid varje steg två grannar. Om de är i fel ordning byter de plats. Varannan gång genomlöps listan framlänges, varannan gång baklänges. |
O(n2) |
Ja |
| InsertationSort | Betraktar en del av listan till vänster som sorterad. Vid varje iteration sätts nästa element in på rätt plats i den sorterade delen genom bubbling neråt. |
O(n2) |
Ja |
| SelectionSort | Betraktar en del av listan till vänster som sorterad. Vid varje iteration letas det minsta av de återstående elementen upp och placeras in på nästa plats. |
O(n2) |
Nej |
| ShellSort | Fungerar huvudsakligen som den ökända BubbleSort, men börjar med att jämföra element på stora avstånd (t.ex. halva listans längd) och går ned i avstånd mellan elementen som jämförs tills avståndet är 0 och därmed hela listan är sorterad. På detta sätt genomförs först en grovsortering av listan. |
O(n log n) |
Nej |
| HeapSort |  Använder
en analogi mellan kompletta binära träd och hur de lagras i en
lista. I detta fallet har trädet egenskapen att värdet i en nod
är större eller lika med värdet i barnnoderna. I varje iteration
är det första elementet i det binära trädet
således det största och byts ut mot det sista,
så hamnar det på rätt plats i listan. Så behöver
man bara återställa trädet (varje nod större eller
lika med varje barnnod), och det är dags för nästa iteration. |
O(n log n) |
Nej |
| MergeSort |  Varje steg i algoritmen
sorterar ihop två delar av listan. Delarnas storlek börjar med
att vara ett och dubblas tills längden är hela listan och den därmed är sorterad. Problemet
med algoritmen är att den under sorteringen behöver extra minne
proportionellt mot antalet element i listan. |
O(n log n) |
Ja |
| QuickSort | Väljer ut ett strategiskt pivotelement och placerar alla element mindre än pivotelementet i början av listan och alla element större än pivotelementet i slutet på listan. Sedan anropas QuickSort rekursivt för början av listan och för slutet av listan. |
O(n log n) |
Nej |
| BogoSort | BogoSort är ekvivalent med att upprepade gånger kasta upp en kortlek i luften, plocka upp korten slumpvis, och sedan testa om de är i ordning. Den tjänar som det klassiska exemplet på fulhet. Mer information finns på http://www.science.uva.nl/~mes/jargon/b/bogosort.html. Min implementering skiljer sig lite från den ovan beskrivna, men resultatet är ungefär detsamma. |
O(n!) |
Nej |