Here's a pretty common pattern for sorting algorithms:
def sort(l): while not is_sorted(l): choose indices i, j assert i < j if l[i] > l[j]: l[i], l[j] = l[j], l[i]
These algorithms work well because the indices
j are chosen carefully, based on the state of the list
However, what if we couldn't see
l, and just had to choose blindly? How fast could we sort the list then?
Your challenge is to write a function that outputs a random pair of indices, given only the length of
l. Specifically, you must output two indices,
i, j, with
0 <= i < j < len(l). Your function should work on any length of list, but it will be scored on a list of length 100.
Your score is the mean number of index choices necessary to sort a uniformly randomly shuffled list according to the above pattern, where the indices are chosen according to your function.
I will score submissions, taking the mean number of index choices over 1000 trials on a uniformly randomly shuffled list of length 100 with no repeated entries.
I reserve the right to run less trials if the submission is clearly non-competitive or does not terminate, and I will run more trials to differentiate the top competitors to find a single winner. If multiple top submissions remain within the margin of error at the limit of my computational resources, I will declare the earlier submission the winner, until further computational resources can be brought to bear.
Here's an example scoring program, in Python:
import random def is_sorted(l): for x in range(len(l)-1): if l[x] > l[x+1]: return False return True def score(length, index_chooser): steps = 0 l = list(range(length)) random.shuffle(l) while not is_sorted(l): i, j = index_chooser(length) assert (i < j) if l[i] > l[j]: l[i], l[j] = l[j], l[i] steps += 1 return steps
Your function may not maintain any mutable state, interact with global variables, affect the list
l, etc. Your function's only input must be the length of the list
l, and it must output a ordered pair of integers in the range
[0, len(l)-1] (or appropriate for your language's list indexing). Feel free to ask whether something's allowed in the comments.
Submissions may be in any free-to-use language. Please include a scoring harness if one has not already been posted for your language. You may post a provisional score, but I will leave a comment with the official score.
Scoring is the mean number of steps to a sorted list on a uniformly randomly shuffled list of length 100. Good luck.