Blind Random Sort

Question

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.

Answer 1

Python, score = 4508

def half_life_3(length):
    h = int(random.uniform(1, (length / 2) ** -3 ** -0.5) ** -3 ** 0.5)
    i = random.randrange(length - h)
    return i, i + h

Half-Life 3 confirmed.

Python, score = 11009

def bubble(length):
    i = random.randrange(length - 1)
    return i, i + 1

Apparently a randomized bubble sort doesn’t do all that much worse than a normal bubble sort.

Optimal distributions for small length

There’s no way this could be extended to length 100, but it’s interesting to look at anyway. I computed optimal distributions for small cases (length ≤ 7) using gradient descent and lots of matrix algebra. The kth column shows the probability of each swap at distance k.

length=1
score=0.0000

length=2
1.0000
score=0.5000

length=3
0.5000 0.0000
0.5000
score=2.8333

length=4
0.2957 0.0368 0.0000 
0.3351 0.0368 
0.2957 
score=7.5106

length=5
0.2019 0.0396 0.0000 0.0000 
0.2279 0.0613 0.0000 
0.2279 0.0396 
0.2019 
score=14.4544

length=6
0.1499 0.0362 0.0000 0.0000 0.0000 
0.1679 0.0558 0.0082 0.0000 
0.1721 0.0558 0.0000 
0.1679 0.0362 
0.1499 
score=23.4838

length=7
0.1168 0.0300 0.0041 0.0000 0.0000 0.0000 
0.1313 0.0443 0.0156 0.0000 0.0000 
0.1355 0.0450 0.0155 0.0000 
0.1355 0.0443 0.0041 
0.1313 0.0300 
0.1168 
score=34.4257

Answer 2

Score: 4627

def rand_step(n):
	step_size = random.choice([1, 1, 4, 16])
	
	if step_size > n - 1:
		step_size = 1 
	
	start = random.randint(0, n - step_size - 1)
	return (start, start + step_size)

Try it online!

Outputs random indices whose distance apart is chosen uniformly from [1,1,4,16]. The idea is to have a mix of 1-step swaps with swaps at larger scales.

I hand-tweaked these values for lists of length 100, and they are likely far from optimal. Some machine search could probably optimize the distribution over distances for the random-pair-with-chosen-distance strategy.

Answer 3

Score: 28493

def x_and_y(l):
    x = random.choice(range(l))
    y = random.choice(range(l))
    while y == x and l != 1: y = random.choice(range(l))
    return sorted([x,y])

Try it online!

This solution just selects distinct values for x and y randomly from the range and returns them in sorted order. As far as I can tell, this performs better than choosing x then choosing y from the remaining values.

Answer 4

Python, score: 39525

def get_indices(l):
    x = random.choice(range(l-1))
    y = random.choice(range(x+1,l))
    return [x,y]

First it chooses a random value in the range \$[0, l-1)\$ for the \$x\$-index.
After that it will choose another random value larger than \$x\$ in the range \$[x+1, l)\$ for the \$y\$-index.

Try it online.

Answer 5

Python, score ≈ 5000

def exponentialDistance(n):
    epsilon = 0.25
    for dist in range(1, n):
        if random.random() < epsilon:
            break
    else:
        dist = 1
    low = random.randrange(0, n - dist)
    high = low + dist
    return low, high

Tried with a bunch of epsilon values, 0.25 seems to be the best.

Score ≈ 8881

def segmentedShuffle(n):
    segments = 20
    segmentLength = (n - 1) // segments + 1

    if random.random() < 0.75:
        a = b = 0
        while a == b or a >= n or b >= n:
            segment = random.randrange(segments)
            a = random.randrange(segmentLength) + segment * segmentLength
            b = random.randrange(segmentLength) + segment * segmentLength
        return sorted([a, b])

    highSegment = random.randrange(1, segments)
    return highSegment * segmentLength - 1, highSegment * segmentLength

A different approach. Not as good, and it dies horribly with length not divisible by the number of segments, but still fun to build.

Answer 6

Score: 4583

def rand_shell(l):
    steps = [1, 3, 5, 9, 17, 33, 65, 129]
    candidates = [(left, left + step)
            for (step, nstep) in zip(steps, steps[1:])
            for left in range(0, l - step)
            for i in range(nstep // step)
    ]
    return random.choice(candidates)

Try it online!

I've no idea why. I just tried sequences listed on wikipedia artical for shellsort. And this one seem works best. It get similar score with the one xnor posted.

Answer 7

Python 2, 4871

import random
def index_chooser(length):
    e= random.choice([int(length/i) for i in range(4,length*3/4)])
    s =random.choice(range(length-e))
    return [s,s+e]
def score(length, index_chooser):
    steps = 0
    l = list(range(length))
    random.shuffle(l)
    while True:
        for x in range(length-1):
            if l[x] > l[x+1]:
                break
        else:
            return steps
        i, j = index_chooser(length)
        assert(i < j)
        if l[i] > l[j]:
            l[i], l[j] = l[j], l[i]
        steps += 1

print sum([score(100, index_chooser) for t in range(100)])

Try it online!