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!

.