Posted on Wed 14 March 2012

Visualizing sorting Algorithms with D3

In my Algorithm class, we had to implement our own sorting algorithm as an exercise in pseudo-code. It was very simple: Alternatingly iterate over an array from beginning to end and from end to beginning, always swapping pairs over numbers which are not correctly sorted. Repeat until finished.

In Python (you can also download a runnable versioncachespan)

def sort(a):
  lower_limit = 0
  upper_limit = len(a) - 1

  while(lower_limit != upper_limit ):
    i = lower_limit
    while i < upper_limit - 1:
      if a[i] > a[i+1]:
        a[i], a[i + 1] = a[i + 1], a[i]
        if upper_limit == i+1 and upper_limit < len(a) - 1:
          upper_limit += 1
        if lower_limit == i and lower_limit > 0:
          lower_limit -= 1
      elif lower_limit + 1 == i:
        lower_limit += 1
      i += 1

    i = upper_limit - 1
    while i >= lower_limit:
      if a[i] > a[i+1]:
        a[i], a[i + 1] = a[i + 1], a[i]
        if upper_limit == i+1 and upper_limit < len(a) - 1:
          upper_limit += 1
        if lower_limit == i and lower_limit > 0:
          lower_limit -= 1
      elif upper_limit - 1 == i:
        upper_limit -= 1
      i -= 1

Of course, I wasn't content with just a pseudo code implementation, so I set out to write something more tangible. Here's the result - a sort visualization using D3cache, an awesome JavaScript library for data-driven manipulation. "Selection Sort" is what you'd expect, and "AlgoDat Sort" is the algorithm described above.

ms step duration      elements
Selection Sort
AlgoDat Sort

Steps so far: 0

Category: misc

Tags: programming, university

© Julian Schrittwieser. Built using Pelican. Theme by Giulio Fidente on github. .