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 versionspan)
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 D3, an awesome JavaScript library for data-driven manipulation. "Selection Sort" is what you'd expect, and "AlgoDat Sort" is the algorithm described above.
Steps so far: 0Tags: programming, university