I’m currently working on a little web app that allows the user to sort a list of elements (like a tier-list maker).
Instead of just asking the user to sort the list through drag’n drop, I thought I could run a sorting algorithm that would ask the user every time it needs to make a comparison.
The whole thing would feel a bit magic, since you would have several questions like “Which one do you prefer, A or B?” and get your sorted list.
The question is: which algorithm should I use to keep the user entertained? I don’t want to compare A with everything, then B with everything and so on with something like a Bubble Sort, that would be boring.
What do you think about it? Please be aware this is not a big project, just something I make out of curiosity. Thanks in advance!
Edit:
As an example, let’s say I want to sort fruits by personal preference.
I have a list [Apple, Banana, Coconut, Durian, Eggplant, Fig, Grape] but no algorithm can tell if I prefer an apple or a banana so it needs to ask me.
What would be the questions an algorithm needs to ask me in order to sort the list of fruits for me?
The idea behind it is not to sort stuff but to spark discussion during the “comparison” step (“Ok, why do you prefer bananas to apples?”), that’s why I need successive comparisons to be different, so it keeps the users’ interest.
It might be something that is pretty different than what you are looking for, but for interactivity it might be funnier and less repetitive if you demonstrate some sort of bucket/radix sort to not have comparisons at all “choose which buket this number should go into”
Maybe also mergesort would be fun to simulate. You can split the array as usual and then ask the user to pick which number should go next from the two lists.
Merge sort is really promising since I can first break my list into pairs, sort every pair (if my list is randomized, those pairs are random, which is good for entertainment) and then alternate between the different merges so we don’t focus on one half of the list
And add some random caracters in the comparaison like emojis nulber, or one number is written in letter, or which side have more cat and you show emoji cat or picture with cats. Be creative on the number presentation to add some sillyness and fun
I would break it into an interface that abstracts the sorting algorithm so that the sorting logic is decoupled from comparison logic or from the visuals. This would make it so that you can use different sorting algorithms and compare between them to see which one seems the most magical.
Magical might mean something different between us, so I don’t want to assume and just give you an algo.
I already managed to break the code for my sorting algorithm to take an async lambda as a comparison function. Therefor I can choose my sorting algorithm on the fly.
As for magic, I thought the interface would show you pairs of elements that look randomly picked and after a while it gives you your sorted list. So, the “magical” thing would be that not-so-random selection of pairs
Among the classics, perhaps quick sort? Since it is unstable.
QuickSort sounds good since it’s, well… quick, but the whole pivot thing would compare the pivot to everything as a first step which would not be very entertaining if done manually.
n*log(n) algorithms are the way to go, thoughYou can take the median of three random elements as your pivot, to get a good chance of it being near the middle without a lot of comparisons.
the problems are: my elements are not comparable without a user input (I added an example with fruits in an edit in my post), and even if I chose a good pivot, most of the first questions would be “Do you prefer Coconut or Apple? Do you prefer Coconut or Banana? Do you prefer Coconut or Durian?” (supposing Coconut is the pivot) which would be a bit boring
A sorting algorithms is the wrong choice here. Use iterative Bradley-Terry and always choose the closest comparison (i.e. the two things that are ranked closest) that you haven’t compared before.
This will give you good results fastest and it will robustly handle conflicting results (A beats B beats C beats A) that sorting algorithms wouldn’t.
Maybe merge sort. Its O(nlogn) and fun, or at least less boring than manually bubble sorting.
Merge sort is easy to implement and looks cool when animated.
I think you may be wanting something like probabilistic programming. You aren’t sorting. You are getting facts to infer something else with a high probability.
This is not unlike what LLMs/GPTs are doing. Inferring the next best word after asking billions of questions.
