Voici un modèle assez courant pour les algorithmes de tri:

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]

Ces algorithmes fonctionnent bien car les indices iet jsont choisis avec soin, en fonction de l'état de la liste l.

Cependant, que se passerait-il si nous ne pouvions pas voir let si nous devions simplement choisir aveuglément? À quelle vitesse pourrions-nous alors trier la liste?

Votre défi consiste à écrire une fonction qui génère une paire aléatoire d'indices, étant donné uniquement la longueur de l. Plus précisément, vous devez générer deux index,, i, javec 0 <= i < j < len(l). Votre fonction devrait fonctionner sur n'importe quelle longueur de liste, mais elle sera notée sur une liste de longueur 100.

Votre score est le nombre moyen de choix d'index nécessaires pour trier une liste uniformément aléatoire au hasard selon le modèle ci-dessus, où les indices sont choisis en fonction de votre fonction.

Je noterai les soumissions, en prenant le nombre moyen de choix d'index sur 1000 essais sur une liste uniformément aléatoire de 100 de longueur sans entrées répétées.

Je me réserve le droit d'exécuter moins d'essais si la soumission est clairement non compétitive ou ne se termine pas, et j'exécuterai plus d'essais pour différencier les meilleurs concurrents afin de trouver un seul gagnant. Si plusieurs soumissions principales restent dans la marge d'erreur à la limite de mes ressources de calcul, je déclarerai la soumission antérieure gagnante, jusqu'à ce que d'autres ressources de calcul puissent être utilisées.

Voici un exemple de programme de notation, en 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

Votre fonction ne peut pas conserver tout état mutable, interagissent avec les variables globales, affectent la liste l, etc. entrée uniquement de votre fonction doit être la longueur de la liste l, et il doit sortir une paire ordonnée d'entiers dans la plage [0, len(l)-1](ou approprié pour votre de la langue indexation des listes). N'hésitez pas à demander si quelque chose est autorisé dans les commentaires.

Les soumissions peuvent être dans n'importe quelle langue gratuite. Veuillez inclure un harnais de notation si celui-ci n'a pas encore été publié pour votre langue. Vous pouvez poster un score provisoire, mais je laisserai un commentaire avec le score officiel.

La notation est le nombre moyen d'étapes vers une liste triée sur une liste uniformément aléatoire de longueur 100. Bonne chance.

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

Confirmation de Half-Life 3.

Python, score = 11009

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

Apparemment, un tri à bulles aléatoire ne fait pas bien pire qu'un tri à bulles normal.

Distributions optimales pour petite longueur

Il n'y a aucun moyen que cela puisse être étendu à 100, mais c'est intéressant à regarder de toute façon. J'ai calculé les distributions optimales pour les petits cas (longueur ≤ 7) en utilisant la descente de gradient et beaucoup d'algèbre matricielle. La k ème colonne montre la probabilité de chaque swap à la 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

Résultat: 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)

Essayez-le en ligne!

Génère des indices aléatoires dont la distance est choisie uniformément [1,1,4,16]. L'idée est d'avoir un mélange de swaps en une étape avec des swaps à plus grande échelle.

J'ai modifié à la main ces valeurs pour des listes de longueur 100, et elles sont probablement loin d'être optimales. Une recherche automatique pourrait probablement optimiser la distribution sur les distances pour la stratégie de paire aléatoire avec la distance choisie.

Résultat: 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])

Essayez-le en ligne!

Cette solution sélectionne simplement des valeurs distinctes pour xet de ymanière aléatoire dans la plage et les renvoie dans l'ordre trié. Pour autant que je sache, cela fonctionne mieux que de choisir xpuis de choisir yparmi les valeurs restantes.

Python, score: 39525

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

$[0, l-1)$$x$
$x$$[x+1, l)$$y$

Essayez-le en ligne.

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

Essayé avec un tas de valeurs epsilon, 0,25 semble être le meilleur.

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

Une approche différente. Pas aussi bon, et il meurt horriblement avec une longueur non divisible par le nombre de segments, mais toujours amusante à construire.

Résultat: 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)

Essayez-le en ligne!

Je ne sais pas pourquoi. Je viens d'essayer des séquences répertoriées sur wikipedia artical pour shellsort . Et celui-ci semble fonctionner le mieux. Il obtient un score similaire avec celui xnor publié .

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)])

Essayez-le en ligne!