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 i
and j
are chosen carefully, based on the state of the list l
.
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.