headerimage

SneManden.com

Sorteringsalgoritmer visualiseret

02. March 2013

Jeg faldt for nylig over denne fine blogpost http://glowingpython.blogspot.dk... Det er et lille python script, som løbende plotter den fantastiske sorteringsalgoritme BubbleSort i aktion.

Men desværre var der ikke umiddelbart nogen gif at hente, så jeg gik straks ikast med at generere en sådan en. Jeg compilede og installerede ImageMagick og kørte følgende kommando:

convert -delay 2 bubblesort/*.png bubbleSortAnimation.gif

Den konverterer simpelthen alle de genererede PNG-filer til én smuk gif. I ovenstående kommando, er det eksemplet på generering af bubble-sort animationen. Og nu da jeg var ved det, implementerede jeg også hurtigt to andre sorteringsalgoritmer: SelectionSort og InsertionSort.

Min egen, slightly modificerede version fra førnævnte blogpost og de to lignende scripts til de andre algoritmer kan du finde her: bubbleSort.py, selectionSort.py, insertionSort.py. Til at plotte er der anvendt pylab, som er indeholdt i numPy. Det er ikke et library jeg har stiftet megen bekendsskab med, men måske dette vil ændres i fremtiden.

BubbleSort

Bubble-sort animated

SelectionSort

Selection-sort animated

InsertionSort

Insertion-sort animated

I forbindelse med dette mikro-projekt, faldt jeg over en aldeles fin side med flotte visualiseringer af forskellige sorteringsalgoritmer - heriblandt quickSort, mergeSort og heapSort: http://www.sorting-algorithms.com/. Interessen for sorteringsalgoritmer kommer fra mit Datalogi-studie på SDU i Odense, hvor jeg i øjeblikket deltager i kurset "Algoritmer og datastrukturer", som beskæftiger sig meget med diverse sorteringsalgoritmer, med analyse af korrekthed og køretid.