Selection Sort Animated
Join the DZone community and get the full member experience.
Join For FreeLately I bumped in the Wikipedia page dedicated to the Selection Sort
algorithm and I found an interesting animation that shows its behavior.
So I decided to write this post which shows how to recreate that
animation using Python.
The idea behind the selection sort is straightforward: at each iteration
the unsorted element with the smallest (or largest) value is moved to
its proper position in the array.
Assume that we wish to sort an array in increasing order. We begin by
selecting the lowest element and moving it to the lowest index position.
We can do this by swapping the element at the lowest index and the
lowest element. We then reduce the effective size of the unsorted items
by one element and repeat the process on the smaller unsorted
(sub)array. The process stops when the effective number of the unsorted
items becomes 1.
Let's see a Python implementation of the selection sort which is able to
visualize with a graph the status of the sorting at each iteration:
import pylab def selectionsort_anim(a): x = range(len(a)) for j in range(len(a)-1): iMin = j for i in range(j+1,len(a)): if a[i] < a[iMin]: # find the smallest value iMin = i if iMin != j: # place the value into its proper location a[iMin], a[j] = a[j], a[iMin] # plotting pylab.plot(x,a,'k.',markersize=6) pylab.savefig("selectionsort/img" + '%04d' % j + ".png") pylab.clf() # figure clear # running the algorithm a = range(300) # initialization of the array shuffle(a) # shuffle! selectionsort_anim(a) # sorting
At each iteration the status of the algorithm is visualized plotting the
indexes of the array versus its values. Every plot is saved as an image
and we can easily join them as a video using ffmpeg:
$ cd selectionsort # the directory where the images are $ ffmpeg -qscale 5 -r 20 -b 9600 -i img%04d.png movie.mp4
The result should be as follows
<object width="640" height="480"><param name="movie" value="http://www.youtube.com/v/R-vLQaPSjmU?version=3&hl=en_US"></param><param name="allowFullScreen" value="true"></param><param name="allowscriptaccess" value="always"></param><embed src="http://www.youtube.com/v/R-vLQaPSjmU?version=3&hl=en_US" type="application/x-shockwave-flash" width="640" height="480" allowscriptaccess="always" allowfullscreen="true"></embed></object>
At each frame of the video we can see that the elements on the left form
a subset of items already sorted and the rest of the items remain to be
sorted. It's nice to see that the number unsorted elements decrease at
each iterations while the subset of sorted items grows forming a
straight line.
This is just the first of a series of posts
about the visualization of sorting algorithms. Stay tuned for the
animations of other sorting algorithms!
Published at DZone with permission of Giuseppe Vettigli, DZone MVB. See the original article here.
Opinions expressed by DZone contributors are their own.
Trending
-
How To Use Geo-Partitioning to Comply With Data Regulations and Deliver Low Latency Globally
-
Never Use Credentials in a CI/CD Pipeline Again
-
Tech Hiring: Trends, Predictions, and Strategies for Success
-
Mastering Time Series Analysis: Techniques, Models, and Strategies
Comments