Berikut adalah pola yang cukup umum untuk menyortir algoritma:

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]

Algoritma ini bekerja dengan baik karena indeks idan jdipilih dengan hati-hati, berdasarkan keadaan daftar l.

Namun, bagaimana jika kita tidak bisa melihat l, dan hanya harus memilih secara membabi buta? Seberapa cepat kita bisa mengurutkan daftar itu?

Tantangan Anda adalah menulis fungsi yang menghasilkan pasangan indeks acak, hanya diberi panjang l. Khususnya, Anda harus menampilkan dua indeks i, j,, dengan 0 <= i < j < len(l). Fungsi Anda harus bekerja pada daftar panjang mana pun, tetapi akan dicetak pada daftar panjang 100.

Skor Anda adalah jumlah rata-rata pilihan indeks yang diperlukan untuk mengurutkan daftar acak acak menurut pola di atas, di mana indeks dipilih sesuai dengan fungsi Anda.

Saya akan menilai pengiriman, dengan mengambil jumlah rata-rata pilihan indeks lebih dari 1000 percobaan pada daftar panjang acak 100 acak tanpa acak entri.

Saya berhak menjalankan uji coba lebih sedikit jika pengajuannya jelas tidak kompetitif atau tidak berakhir, dan saya akan menjalankan lebih banyak uji coba untuk membedakan pesaing teratas untuk menemukan pemenang tunggal. Jika beberapa pengajuan teratas tetap berada dalam margin of error pada batas sumber daya komputasi saya, saya akan menyatakan pengajuan sebelumnya pemenang, sampai sumber daya komputasi lebih lanjut dapat dibawa untuk menanggung.

Berikut ini contoh program penilaian, dengan 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

Fungsi Anda mungkin tidak mempertahankan status yang dapat berubah, berinteraksi dengan variabel global, memengaruhi daftar l, dll. Input fungsi Anda hanya boleh sepanjang daftar l, dan itu harus menampilkan sepasang bilangan bulat yang terurut dalam rentang [0, len(l)-1](atau sesuai untuk bahasa Anda daftar pengindeksan). Jangan ragu untuk bertanya apakah ada yang diizinkan dalam komentar.

Pengajuan mungkin dalam bahasa bebas untuk digunakan. Harap sertakan harness penilaian jika belum diposkan untuk bahasa Anda. Anda dapat memposting skor sementara, tetapi saya akan meninggalkan komentar dengan skor resmi.

Penilaian adalah jumlah rata-rata langkah-langkah ke daftar yang diurutkan pada daftar panjang acak 100 acak. Semoga berhasil.

Python, skor = 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 dikonfirmasi.

Python, skor = 11009

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

Rupanya semacam gelembung acak tidak melakukan semua yang jauh lebih buruk daripada jenis gelembung normal.

Distribusi optimal untuk panjang kecil

Tidak mungkin ini bisa diperpanjang ke panjang 100, tetapi menarik untuk dilihat pula. Saya menghitung distribusi optimal untuk kasus-kasus kecil (panjang ≤ 7) menggunakan gradient descent dan banyak aljabar matriks. Kolom k th menunjukkan probabilitas setiap swap pada jarak 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

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

Cobalah online!

Menghasilkan indeks acak yang jaraknya dipilih secara seragam [1,1,4,16]. Idenya adalah untuk memiliki campuran swap 1 langkah dengan swap pada skala yang lebih besar.

Saya men-tweak nilai-nilai ini untuk daftar panjang 100, dan mereka kemungkinan jauh dari optimal. Beberapa pencarian mesin mungkin dapat mengoptimalkan distribusi jarak untuk strategi acak-pasangan-dengan-dipilih-jarak.

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

Cobalah online!

Solusi ini hanya memilih nilai yang berbeda untuk xdan ysecara acak dari rentang dan mengembalikannya dalam urutan yang diurutkan. Sejauh yang saya tahu, ini berkinerja lebih baik daripada memilih xkemudian memilih ydari nilai yang tersisa.

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

Cobalah online.

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

Dicoba dengan banyak nilai epsilon, 0,25 tampaknya menjadi yang terbaik.

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

Pendekatan yang berbeda. Tidak sebagus itu, dan mati mengerikan dengan panjang tidak dibagi dengan jumlah segmen, tetapi masih menyenangkan untuk dibangun.

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

Cobalah online!

Saya tidak tahu kenapa. Saya baru saja mencoba urutan yang terdaftar di wikipedia artical untuk shellsort . Dan yang ini tampaknya paling berhasil. Itu mendapatkan skor yang sama dengan yang diposting .

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

Cobalah online!