Odd-Even sort visualized

The Odd/Even sort is a sorting algorithm which uses the concept of the Bubble Sort to move elements around. Unlike Bubble sort, the Odd/Even sort compares disjointed pairs by using alternating odd and even index values splitting the sorting in different phases. We have that in the odd phase all the element with an odd index i are compared with the adjacent even index i+1 and in the even phase all the element with an even index i are compared with the adjacent odd index i+1. These two phases are repeated until no exchanges are required. This is a Python snippet that make us able to visualize the behavior of the algorithm:

def oddeven_anim(a):
 imgidx = 0
 x = range(len(a))
 sort = False; 
 while not sort:
  sort = True;
  for i in range(1,len(a)-1,2): # odd phase
   if a[i] > a[i+1]:
    a[i+1], a[i] = a[i], a[i+1]
    sort = False;
  for i in range(0,len(a)-1,2): # even phase
   if a[i] > a[i+1]:
    a[i+1], a[i] = a[i], a[i+1]
    sort = False;
  pylab.plot(x,a,'k.',markersize=6)
  pylab.savefig("oddevensort/img" + '%04d' % imgidx + ".png")
  pylab.clf()
  imgidx =  imgidx + 1

# run the algorithm
a = range(300)
shuffle(a)
oddeven_anim(a)

As in the other examples of sorting visualization in this blog, we have an image for each step of the algorithm. The following video have been produced joining all the images (here is explained how):

Insertion Sort animation

To continue the series of animated sorting algorithm this time we will deal with the Insertion Sort. We are still in the basic algorithms and the way it works is pretty simple. It inserts each element of the array into its proper position, leaving progressively larger stretches of the array sorted. What this means in practice is that the sort iterates down an array, and the part of the array already covered is in order; then, the current element of the array is inserted into the proper position at the head of the array while the rest of the elements are moved using the space just vacated by the element inserted. The Python snippet for creating the animation is the following:

def insertionsort_anim(a):
 x = range(len(a))
 for i in range(1,len(a)):
  val = a[i]
  j = i-1
  while j >= 0 and a[j] > val:
   a[j+1] = a[j] # creating the space for the insertion
   j = j-1
  a[j+1] = val # insertion
  pylab.plot(x,a,'k.',markersize=6)
  pylab.savefig("insertionsort/img" + '%04d' % i + ".png")
  pylab.clf()

# running the algorithm
a = range(300)
shuffle(a)
insertionsort_anim(a)

The strategy used to create the video is the usual and we can see the result in the following video:

It's interesting to see that the algorithm forms small subsets of sorted items that tend to join when the number of iteration grows and the holes between the them are filled by the insertion process.

Bubble Sort visualized

The bubble sort algorithm is one of the simplest sorting methods to implement and in this post we will see that it is also one of the best to visualize. It works by repeatedly exchanging adjacent elements when necessary and stops when no exchanges are required. Thus, smaller elements will "bubble" to the front, (or bigger elements will be "bubbled" to the back). The following snippet is able to visualize the behavior of the bubble sort:

import pylab
from random import shuffle

def bubblesort_anim(a):
 x = range(len(a))
 imgidx = 0
 # bubble sort algorithm
 swapped = True
 while swapped: # until there's no swapping
  swapped = False
  for i in range(len(a)-1):
   if a[i] > a[i+1]:
    a[i+1], a[i] = a[i], a[i+1] # swap
    swapped = True
  pylab.plot(x,a,'k.',markersize=6)
  pylab.savefig("bubblesort/img" + '%04d' % imgidx + ".png")
  pylab.clf() # figure clear
  imgidx = imgidx + 1

# running the algorithm
a = range(300)
shuffle(a)
bubblesort_anim(a)

The snipped is based same technique we have seen to visualize the insertion sort algorithm and to build the animation. At each iteration an image that represents the status of the array is saved to the disk and ffmpeg is used to build a video as showed in the last post. This time the result should be as follows:

The animation is easy on the eyes and we can observe that during the sorting process the smallest elements approach to their correct positions as the bubbles go up in a glass of soda.

Stay tuned to see the animation of the insertion sort algorithm!

Selection Sort animated

Lately 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

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!