Incomparable Sort 2: Meme Sort
Desktop Applications
Meme Sort is a sorting program that lets you sort your pictures. All you do is select a source and destination folder, click start, then click on which image you think is better. When all the comparisons are made, the pictures from the source folder will be copied to the destination folder and will be ordered by your judgment.
You can download this for Windows from my Github below:
This application is a continuation of my Incomparable Sort idea that I wrote about and developed before. Meme Sort is what I actually had in mind when I developed the first Incomparable Sort, but I didn’t have the time to implement my idea with images.
Development
I decided to use Qt because I wanted to develop my application in C++ and it’s a popular toolkit.
Sorting Algorithm
From my previous article I determined that Merge Sort was the most optimal algorithm for this purpose as it has the fewest comparisons on average. Where I differ though is my Merge Sort implementation. In my previous Javascript implementation I used Merge Sort with recursion. Using Merge Sort with recursion in my desktop application would lead to several problems such as having to halt execution of the program while waiting for the user to make a comparison. I decided instead to implement Merge Sort iteratively with a bottom up approach. The list of images would be split into a list of lists containing one image each. Then each list would be merged back together by the user’s comparisons until one fully sorted list is left.
Undo & Redo
When using my previous Incomparable Sort implementation I would often find myself accidentally clicking on the wrong item when performing comparisons, so I knew I definitely wanted an undo button. Since I implemented the sorting algorithm with two alternating lists of sorted lists instead of with recursion, it made it much easier to change the state of the application. All I needed to do was just use a QUndoStack (It’s just a stack in Qt that contains the changes that have been made, and how to undo and redo those changes) and push the state of the sorting algorithm onto it before each comparison. When I want to undo or redo a comparison, all I need to do is pop the state of the sort from the stack, reassign the current state of the sorting algorithm, and reload the necessary images.
Analysis
When performing the comparisons in my last article, I would always wonder how many more I had left. After all the best we can really do in sorting is nLog(n) complexity. I wanted to be more specific though, so I found two scholarly articles with formulas to calculate number of comparisons from Marek A. Suchenek, Ph.D.
Lower bound (Fewest comparisons needed):
Upper bound (Most comparisons needed):
https://arxiv.org/abs/1607.04604
https://arxiv.org/abs/1702.08443
Conclusion
I had a lot of fun developing this application. I started developing it a year ago after I wrote the previous article and now I’ve finally gotten around to finishing it. I’d definitely arrange the code differently given the knowledge I've gained along the way, but I’m just happy to have the application that I’ve wanted all along. Now I can sort my memes, vacation photos, selfies, and much more!