Hier ist ein ziemlich verbreitetes Muster für Sortieralgorithmen:

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]

Diese Algorithmen funktionieren gut, da die Indizes iund janhand des Status der Liste sorgfältig ausgewählt werden l.

Was aber, wenn wir nicht sehen lkonnten und einfach blind wählen mussten? Wie schnell könnten wir dann die Liste sortieren?

Ihre Herausforderung besteht darin, eine Funktion zu schreiben, die ein zufälliges Indexpaar mit der angegebenen Länge von ausgibt l. Insbesondere müssen Sie zwei Indizes ausgeben i, j, mit 0 <= i < j < len(l). Ihre Funktion sollte auf jeder Länge der Liste funktionieren, sie wird jedoch auf einer Liste mit einer Länge von 100 bewertet.

Ihre Punktzahl ist die mittlere Anzahl von Indexauswahlmöglichkeiten, die erforderlich sind, um eine gleichmäßig zufällig gemischte Liste nach dem oben genannten Muster zu sortieren, wobei die Indizes gemäß Ihrer Funktion ausgewählt werden.

Ich werde Einsendungen bewerten und dabei die mittlere Anzahl der Indexauswahl über 1000 Versuche auf einer gleichmäßig zufällig gemischten Liste mit einer Länge von 100 ohne wiederholte Einträge verwenden.

Ich behalte mir das Recht vor, weniger Tests durchzuführen, wenn die Einsendung eindeutig nicht wettbewerbsfähig ist oder nicht beendet wird, und ich werde mehr Tests durchführen, um die besten Konkurrenten zu differenzieren und einen einzigen Gewinner zu finden. Wenn mehrere Top-Einreichungen innerhalb der Fehlergrenze meiner Rechenressourcen verbleiben, erkläre ich die frühere Einreichung zum Gewinner, bis weitere Rechenressourcen zur Geltung gebracht werden können.

Hier ist ein Beispiel für ein Bewertungsprogramm 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

Ihre Funktion behält möglicherweise keinen veränderlichen Status bei, interagiert nicht mit globalen Variablen, wirkt sich auf die Liste lusw. aus. Die einzige Eingabe Ihrer Funktion muss die Länge der Liste sein lund ein geordnetes Paar von Ganzzahlen im Bereich [0, len(l)-1](oder passend für Ihre Sprache) ausgeben Indexierung der Liste). Fühlen Sie sich frei zu fragen, ob etwas in den Kommentaren erlaubt ist.

Die Beiträge können in einer beliebigen Sprache eingereicht werden. Bitte legen Sie ein Bewertungsgeschirr bei, falls noch keines für Ihre Sprache veröffentlicht wurde. Sie können eine vorläufige Punktzahl veröffentlichen, aber ich werde einen Kommentar mit der offiziellen Punktzahl hinterlassen.

Die Bewertung ist die mittlere Anzahl von Schritten zu einer sortierten Liste auf einer gleichmäßig zufällig gemischten Liste mit einer Länge von 100. Viel Glück.

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 bestätigt.

Python, Score = 11009

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

Anscheinend ist eine zufällige Blasensorte nicht viel schlimmer als eine normale Blasensorte.

Optimale Verteilungen für kleine Längen

Es gibt keine Möglichkeit, diese Länge auf 100 zu erweitern, aber es ist trotzdem interessant, sie zu betrachten. Ich habe optimale Verteilungen für kleine Fälle (Länge ≤ 7) mit Gradientenabstieg und viel Matrixalgebra berechnet. Die k- te Spalte zeigt die Wahrscheinlichkeit für jeden Swap im Abstand 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

Ergebnis: 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)

Probieren Sie es online!

Gibt Zufallsindizes aus, deren Abstand einheitlich gewählt wird [1,1,4,16]. Die Idee ist eine Mischung aus 1-Schritt-Swaps mit Swaps in größerem Maßstab.

Ich habe diese Werte für Listen mit einer Länge von 100 von Hand angepasst, und sie sind wahrscheinlich alles andere als optimal. Einige Maschinensuchen könnten wahrscheinlich die Verteilung über Entfernungen für die Strategie des zufälligen Paars mit der gewählten Entfernung optimieren.

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

Probieren Sie es online!

Diese Lösung wählt nur unterschiedliche Werte für xund yzufällig aus dem Bereich aus und gibt sie in sortierter Reihenfolge zurück. Soweit ich das beurteilen kann, besser , dies führt als die Wahl xdann die Wahl yvon den übrigen Werten.

Python, Kerbe: 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$

Probieren Sie es online aus.

Python, Punktzahl ≈ 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

Mit einer Reihe von Epsilon-Werten versucht, scheint 0,25 die beste zu sein.

Ergebnis ≈ 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

Ein anderer Versuch. Nicht so gut, und es stirbt schrecklich mit Länge nicht durch die Anzahl der Segmente teilbar, aber immer noch Spaß zu bauen.

Ergebnis: 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)

Probieren Sie es online!

Ich habe keine Ahnung warum. Ich habe gerade Sequenzen ausprobiert, die auf Wikipedia für Shellsort aufgelistet sind . Und dieser scheint am besten zu funktionieren. Es wird eine ähnliche Punktzahl mit dem einen xnor angezeigt .

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

Probieren Sie es online!