A Python Sorting Manager With A Human Comparison Operator

Nothing too exciting in today's post.  I've created a SortingManager class to implement the sorting algorithm that I mentioned in a previous article.  Unlike most sorting algorithms it doesn't have a way to compare things.  When the manager gets to a point in the sort that require two items to be compared, it'll wait for user input.  This means any object can be sorted, and things that can't usually be compared by a computer can be sorted.  For instance you could supply a list of baby names and use the sorting manager to order them.  To illustrate this I've used a random arrangement of the numbers 1-10.

The first step is to create a deque containing each item and then place all of these deques in another deque.  There also needs to be an empty deque at the start.  This is demonstrated in the example below.  The word deque has been replaced by the letter d to make things more readable.

d([d([]), d([4]), d([10]), d([1]), d([8]), d([5]), d([2]), d([9]), d([3]), d([6]), d([7])])

A sorting manager object is then initialised with this deque.  In this case the deque to sort is called toSort.

sm = SortingManager(toSort)

At this point calling sm.options will return 2 elements in a list to choose from.  Based on your sorting metric you then select one of these by calling sm.select(n), where n is either 0 or 1.  This means you can sort based on obscure things like the best baby name, the nicest font, or the most beautiful flower for a garden.  You can also sort based on conventional things like smallest number.  For most sorting algorithms you have to supply a comparison operator for the objects you're sorting.  In this case YOU are the comparison operator.

This process is repeated until the list is sorted.  If you happen to make a mistake call sm.undo() and this will take you back a step in the sort.  There is also sm.redo() in case it's needed as well.  sm.sorting_state will let you see the the internal state of the object.  This can be saved to file and reloaded later if needed.  sm.progress allows you to know how much of the sort is completed. it return a list of 2 numbers.  The first is the maximum number of comparisons yet to complete, the second is the maximum number of comparisons is the list was completely unsorted.

I get that this may be little hard to understand.  To help you out I've written a test program that sorts the numbers in the deque above.

The output of test.py is listed below.  The internal state deque is displayed, the amount of the sort remaining is shown as a decimal, and then the options to choose from are shown in square bracekts.  My choice of the 1st or 2nd option is shown after the > character.  There is purposeful mistake near the end to demonstrate the undo command.

enter
1 for option 1
2 for option 2
8 for undo
9 for redo

d([d([]), d([4]), d([10]), d([1]), d([8]), d([5]), d([2]), d([9]), d([3]), d([6]), d([7])])
100.0
[4, 10]
>1

d([d([]), d([1]), d([8]), d([5]), d([2]), d([9]), d([3]), d([6]), d([7]), d([4, 10])])
96.0
[1, 8]
>1

d([d([]), d([5]), d([2]), d([9]), d([3]), d([6]), d([7]), d([4, 10]), d([1, 8])])
92.0
[5, 2]
>2

d([d([]), d([9]), d([3]), d([6]), d([7]), d([4, 10]), d([1, 8]), d([2, 5])])
88.0
[9, 3]
>2

d([d([]), d([6]), d([7]), d([4, 10]), d([1, 8]), d([2, 5]), d([3, 9])])
84.0
[6, 7]
>1

d([d([]), d([4, 10]), d([1, 8]), d([2, 5]), d([3, 9]), d([6, 7])])
80.0
[4, 1]
>2

d([d([1]), d([4, 10]), d([8]), d([2, 5]), d([3, 9]), d([6, 7])])
76.0
[4, 8]
>1

d([d([1, 4]), d([10]), d([8]), d([2, 5]), d([3, 9]), d([6, 7])])
72.0
[10, 8]
>2

d([d([]), d([2, 5]), d([3, 9]), d([6, 7]), d([1, 4, 8, 10])])
68.0
[2, 3]
>1

d([d([2]), d([5]), d([3, 9]), d([6, 7]), d([1, 4, 8, 10])])
64.0
[5, 3]
>2

d([d([2, 3]), d([5]), d([9]), d([6, 7]), d([1, 4, 8, 10])])
60.0
[5, 9]
>1

d([d([]), d([6, 7]), d([1, 4, 8, 10]), d([2, 3, 5, 9])])
56.0
[6, 1]
>2

d([d([1]), d([6, 7]), d([4, 8, 10]), d([2, 3, 5, 9])])
52.0
[6, 4]
>2

d([d([1, 4]), d([6, 7]), d([8, 10]), d([2, 3, 5, 9])])
48.0
[6, 8]
>1

d([d([1, 4, 6]), d([7]), d([8, 10]), d([2, 3, 5, 9])])
44.0
[7, 8]
>1

d([d([]), d([2, 3, 5, 9]), d([1, 4, 6, 7, 8, 10])])
36.0
[2, 1]
>2

d([d([1]), d([2, 3, 5, 9]), d([4, 6, 7, 8, 10])])
32.0
[2, 4]
>1

d([d([1, 2]), d([3, 5, 9]), d([4, 6, 7, 8, 10])])
28.0
[3, 4]
>1

d([d([1, 2, 3]), d([5, 9]), d([4, 6, 7, 8, 10])])
24.0
[5, 4]
>1

d([d([1, 2, 3, 5]), d([9]), d([4, 6, 7, 8, 10])])
20.0
[9, 4]
>8

d([d([1, 2, 3]), d([5, 9]), d([4, 6, 7, 8, 10])])
24.0
[5, 4]
>2

d([d([1, 2, 3, 4]), d([5, 9]), d([6, 7, 8, 10])])
20.0
[5, 6]
>1

d([d([1, 2, 3, 4, 5]), d([9]), d([6, 7, 8, 10])])
16.0
[9, 6]
>2

d([d([1, 2, 3, 4, 5, 6]), d([9]), d([7, 8, 10])])
12.0
[9, 7]
>2

d([d([1, 2, 3, 4, 5, 6, 7]), d([9]), d([8, 10])])
8.0
[9, 8]
>2

d([d([1, 2, 3, 4, 5, 6, 7, 8]), d([9]), d([10])])
4.0
[9, 10]
>1
-sorted
0.0
d([d([]), d([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])])

You're going to have to trust me that I'm heading somewhere with this.  As of the time of writing I still need to comment the code and tweak a few things, but stick with me, it's all part of a larger project.

Get The Code!

.

Merge Sort... Sort Of

I have a project in mind that requires a sorting algorithm.  That's easy enough, there are plenty of them out there, the problem I have is that I want to be able to save the state of the sort part way through and resume it later.  The easiest way to explain the solution I devised is to show an example sort in the animation below and then explain it.  First understanding Merge Sort will help as well.

Custom Merge Sort

I haven't really changed much.  I've just implemented Merge Sort in a simple way.  More specifically in a list of lists.  The basic principles of a Merge Sort are still there.  At every stage all sub lists remain sorted and merging two lists is done by comparing the smallest elements of the two lists.

In the animation above, 11 numbers are sorted.  To start, 11 lists that contain only one number each are created to store the numbers to sort.  These are contained within another list that has another empty list placed at the start.  This empty list is called the auxiliary list or List 1.  From this point on the process is simple, merge List 2 and 3 into List 1.  Once this has been done, move the new large list to the end of the outer list. Each time this process is repeated, the number of lists is reduced by one until only one sorted list remains.  It also ensures the the lists are always ordered by the number of elements they contain.  Large ones at the end, smaller ones near the start.

The reason I like this method of sorting is that it's easy to pause the sort, save the state, and resume it later.  All you need to do is save a lists of lists.  You don't need anything else.  When resuming, the next move to make can be determined by looking at the first three lists and seeing if they contain any elements.

Sorting State

It's not ground breaking, and merge sort has probably been implemented like this before, but I found it to be a simple way to go about doing things.  I've mentioned lists throughout this post, but as the program I want to write is likely to be in python, I'll probably use a deque of deques to hold the data.

On another topic, my original plan way to make a nice fancy animation to explain things that had nice transitions, but I just couldn't pull it together in time.  I thought I could find a software package to do it and ended up with Synfig, but that went nowhere.  What kind of program freezes because you have a font installed it can't read.  Some error handling would be nice.

I eventually started hand coding an animated SVG and that showed promise, but it was a bit clumsy and I didn't really have a work flow established as you can see in the image below.  I think I've finally come to a solution that involves d3.js and all that's associated with it.  Fingers crossed.

Makeshift animated SVG IDE

Just for fun, let's speed things up. :-)

Fast Custom Merge Sort

.