Suppose you have a list of about 50 items that are already sorted and you add three items either to the end of the list or somewhere unsorted into the middle. Now you want to re-sort the list with the fewest possible comparisons. Which sorting algorithm or data structure would you use?
I'm writing an online sorter app where the comparisons are subjective. Consider the case where you want to figure out who to invite to your wedding given
n (e.g. 200) people and
n (e.g. 100) seats. You want a way to find the top
m most important people to invite.
After entering their data into a
<textarea>, I generate a "quiz" that prompts them with two item buttons, asking which is more important. The sorting algorithm uses that input as the comparison. I want to minimize the length of the quiz.
In this use case, the comparisons are the only amount of processing time that matters since it requires user input. The actual sorting of such a small number of items happens behind the scenes in a fraction of a second, so no matter how inefficient it is, it won't compare to the time spent comparing two people/families.
I've discovered for thoroughly shuffled lists, an AVL-tree (with memoized comparisons) is actually the most efficient, despite being one of the least efficient self-balancing trees in the real world. For 58 items, it beats Quicksort by an average of 17 comparisons and merge sort by 73.
Suppose the user sorts their list and then remembers three people they forgot to add. Their input is now sorted, but rather than doing what they probably don't know is an insertion sort, they just add the items to end of their list and click the sort button again. At this point, we don't know that their list is mostly sorted, nor that only the last three items are new, so we can't do an insertion sort ourselves. I give options and descriptions for various sorting algorithms so they can choose which algorithm will be most efficient for them. For unsorted lists, the AVL tree algorithm is best. For "mostly sorted" lists, I'll present another algorithm option.
Ideally, if the list is already sorted, it will require exactly
n-1 comparisons. If there are 3 unsorted items, it will require
3n comparisons in the worst case, and
~3n/2 on average, assuming the items belong in the middle of the list.
My instinct says bubble sort--another unlikely algorithm--would be best for my scenario, but I don't know enough about the numerous sorting algorithms to be sure. (I could also be wrong about insertion sort being impossible/inefficient.)
This project is largely done now. I might go back and implement Timsort to see how it compares, but for now, I've just used Insertion Sort. When I said we couldn't use Insertion Sort above, I was thinking of Selection Sort.
The project can be found at https://dfdx.us/subjective-sorter.