Oto dość powszechny wzór algorytmów sortowania:

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]

Algorytmy te działają dobrze bo indeksów ii jsą starannie wybrane, na podstawie stanu listy l.

Co jednak, jeśli nie moglibyśmy zobaczyć l, a musielibyśmy wybrać na ślepo? Jak szybko moglibyśmy posortować listę?

Twoim wyzwaniem jest napisanie funkcji, która generuje losową parę wskaźników, biorąc pod uwagę tylko długość l. W szczególności musisz wygenerować dwa wskaźniki i, j, z 0 <= i < j < len(l). Twoja funkcja powinna działać na dowolnej długości listy, ale będzie oceniana na liście o długości 100.

Twój wynik to średnia liczba wyborów indeksu niezbędnych do posortowania losowo losowo losowej listy zgodnie z powyższym wzorem, przy czym wskaźniki są wybierane zgodnie z funkcją.

Ocenię wyniki, biorąc średnią liczbę wyborów indeksu ponad 1000 prób na jednolicie losowo losowanej liście o długości 100 bez powtarzających się wpisów.

Zastrzegam sobie prawo do przeprowadzenia mniejszej liczby prób, jeśli zgłoszenie jest wyraźnie niezgodne z zasadami konkurencji lub nie zakończy się, i przeprowadzę więcej prób, aby wyróżnić najlepszych konkurentów i znaleźć pojedynczego zwycięzcę. Jeśli wiele najlepszych zgłoszeń pozostanie w granicach błędu na granicy moich zasobów obliczeniowych, ogłosimy zwycięzcę wcześniejszego zgłoszenia, dopóki nie zostaną wykorzystane dalsze zasoby obliczeniowe.

Oto przykładowy program oceniania w Pythonie:

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

Twoja funkcja może nie utrzymywać żadnego stanu zmiennego, wchodzić w interakcje ze zmiennymi globalnymi, wpływać na listę litp. Jedyną wartością wejściową funkcji musi być długość listy li musi ona generować uporządkowaną parę liczb całkowitych z zakresu [0, len(l)-1](lub odpowiednią dla twojego języka indeksowanie list). Zapytaj, czy coś jest dozwolone w komentarzach.

Zgłoszenia mogą odbywać się w dowolnym darmowym języku. Dołącz uprząż punktacji, jeśli nie została jeszcze opublikowana w Twoim języku. Możesz opublikować tymczasowy wynik, ale zostawię komentarz z oficjalnym wynikiem.

Punktacja to średnia liczba kroków do posortowanej listy na jednolicie losowo losowanej liście o długości 100. Powodzenia.

Python, wynik = 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 potwierdzone.

Python, wynik = 11009

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

Najwyraźniej losowe sortowanie bąbelkowe nie robi o wiele gorszego niż normalne sortowanie bąbelkowe.

Optymalne rozkłady dla małej długości

Nie ma możliwości przedłużenia tej długości do 100, ale i tak warto na nią spojrzeć. Obliczyłem optymalne rozkłady dla małych przypadków (długość ≤ 7) przy użyciu spadku gradientu i mnóstwa algebry macierzy. K p pokazuje kolumnie prawdopodobieństwo każdej wymiany w odległości 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

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

Wypróbuj online!

Generuje losowe wskaźniki, których odległość od siebie jest wybierana równomiernie [1,1,4,16]. Chodzi o połączenie 1-krokowych swapów z swapami w większych skalach.

Ręcznie poprawiłem te wartości dla list o długości 100 i są one prawdopodobnie dalekie od optymalnych. Niektóre wyszukiwania maszynowe mogłyby prawdopodobnie zoptymalizować rozkład na odległości dla strategii losowej pary z wybraną odległością.

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

Wypróbuj online!

To rozwiązanie po prostu wybiera odrębne wartości dla zakresu xi ylosowo z zakresu i zwraca je w posortowanej kolejności. O ile mogę stwierdzić, działa to lepiej niż xwybieranie yspośród pozostałych wartości.

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

Wypróbuj online.

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

Wypróbowany z wieloma wartościami epsilon, 0.25 wydaje się najlepszy.

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

Inne podejście. Nie tak dobre i umiera okropnie, a długości nie dzielą liczby segmentów, ale budowanie sprawia przyjemność.

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

Wypróbuj online!

Nie mam pojęcia dlaczego. Właśnie wypróbowałem sekwencje wymienione na Wikipedii artical dla shellsort . I ten wydaje się działać najlepiej. Otrzymuje podobny wynik z tym opublikowanym xnor .

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

Wypróbuj online!