Blind Random Sort
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
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.
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.