Apa algoritma penyortiran ruang konstan yang paling efisien?

Saya mencari algoritma pengurutan untuk array int yang tidak mengalokasikan byte apa pun selain ukuran array, dan terbatas pada dua instruksi:

SWAP: menukar indeks berikutnya dengan yang sekarang;
MOVE: memindahkan kursor ke indeks +1 atau -1;

Artinya, Anda tidak dapat menukar indeks yang tidak bertetangga, atau menukar indeks 100, setelah Anda baru saja menukar indeks 10. Apa algoritma yang paling efisien - yaitu algoritma yang menggunakan jumlah gerakan total yang lebih sedikit?

algorithms sorting in-place Viktor Maia
sumber

Tidak aneh, itu adalah mesin fisik yang akan mengurutkan daftar kereta yang direkatkan ke selotip yang digulung. Mesin hanya dapat memindahkan kaset ke depan atau ke belakang, dan hanya dapat menukar kartu tetangga, dari corse. Di dunia nyata kamu tidak bisa berteleportasi, jadi, itulah batasannya ...

MaiaVictor

Jadi, ketika Anda mengatakan bahwa Anda menginginkan algoritme yang tidak mengalokasikan byte apa pun selain ukuran array , saya kira Anda hanya merujuk ke penyimpanan elemen, bukan? Saya masih bisa mengalokasikan counter dan semacamnya?

Darkhogg

Oh tentu saja. Tentu saja. Anda dapat mengalokasikan beberapa struktur tambahan. Anda bahkan dapat mengalokasikan seluruh array dan melakukan banyak perhitungan yang sangat berat dan itu dihitung sebagai biaya 0. Satu-satunya hal yang perlu Anda minimalkan adalah jumlah SWAP / MOVE mesin fisik yang sebenarnya, karena lambat. Bubble sort adalah yang terbaik yang bisa saya lakukan, tetapi saya kira seharusnya ada pilihan yang lebih baik.

MaiaVictor

Saya tidak berpikir ada algoritma seperti itu. Tanpa setiap memori tambahan, Anda akan memiliki cara untuk menyimpan kontrol negara.

Raphael

@svrm: ya, maka dengan RAM tanpa batas dan kemampuan untuk menyalin kaset ke dalam RAM dan melakukan perhitungan sewenang-wenang secara gratis, algoritma "coba semuanya dan terapkan yang terbaik" adalah optimal dalam hal jumlah gerakan kaset. Tidak mungkin praktis, tapi itu karena dalam prakteknya runtime akan menjadi triliunan tahun, bukan 0 ;-) Jika biaya N bergerak untuk menyalin kaset panjang N ke RAM, maka kekuatan kasar naif mungkin tidak optimal tetapi itu dalam N optimal. Tapi tidak ada yang khusus untuk masalah Anda: banyak masalah ketika dinyatakan dengan cara ini bisa diselesaikan "offline" menggunakan algoritma palsu.

Steve Jessop

Jawaban:

Pertimbangkan jenis pengocok koktail , yang merupakan versi dua arah jenis gelembung. Anda bubblesort dari rendah ke tinggi, dan kemudian (ini adalah bagian yang ditambahkan) Anda bubblesort dari tinggi ke rendah, ulangi sampai selesai. Ini masih , tetapi ia membuat rata-rata lintasan lebih sedikit secara signifikan, karena elemen-elemen kecil di dekat ujung tinggi larik akan dipindahkan ke posisi terakhirnya dalam lintasan tunggal daripada lintasan N. Anda juga dapat melacak posisi terendah dan tertinggi di mana terjadi pertukaran; operan selanjutnya tidak perlu memindai melebihi titik-titik tersebut. $O(n^2)$

zwol
sumber

Jumlah swap elemen yang berdekatan yang diperlukan untuk memesan array sama dengan jumlah inversi dalam array. Dengan n elemen secara total, ada paling banyak inversi n * (n-1) / 2 , jadi bubble sort memberikan jumlah swap optimal asimptotik dalam model ini.

Charles
sumber

Sebenarnya, bubble sort akan memberikan jumlah swap yang tepat. Namun, untuk setiap permutasi ada beberapa cara untuk melakukan jumlah optimal swap, dan tidak jelas yang mana yang mengurangi jumlah total pergerakan. (Menurut bubble sort saya maksudkan "pilih yang terbesar yang tidak disortir dan pindahkan ke akhir yang disortir")

Peter Kravchuk

$O(n^2)$

$-\infty$ $+\infty$

Algoritma yang tidak menggunakan boolean flag untuk mengetahui apakah kita telah menukar elemen atau tidak, diberikan di bawah ini (trik untuk menjaga informasi dalam keadaan mesin, daripada memori):

Start:
    Do until we are not at the leftmost position (Op 4)
        move left (Op 2b)

Check:
    If we are at rightmost position (Op 3)
        goto Finished:
    If current value is larger than next value (Op 5)
        goto Unfinished:
    move right (Op 2a)
    Repeat Check:

Unfinished:
    If we are at rightmost position (Op 3)
        goto Start:
    If current value is larger than next value (Op 5)
        swap the elements (Op 1) and move right (Op 2a)
    Repeat Unfinished:

Finished:
    The list is sorted now, output it.

Solusi dari Eric Lippert, semacam gnome juga berfungsi, karena pada dasarnya itu adalah semacam gelembung dua arah.

Shreesh
sumber

Bagaimana dengan jenis penyisipan?

Darkhogg

Bubble sort membutuhkan setidaknya dua counter loop yang sudah lebih dari yang diizinkan.

Raphael

Tidak, Anda bisa ke kiri dan ke kanan, lalu ke kanan ke kiri, sampai tidak ada perubahan (yang maksimum n kali) tanpa menggunakan penghitung. Anda bahkan tidak perlu ruang ekstra untuk bendera boolean untuk dicatat jika ada perubahan. Jika ada perubahan, Anda hanya melompat ke subrutin lain yang melakukan hal yang sama, kecuali bahwa itu adalah subrutin lain.

Shreesh

Dan tentu saja, saya berasumsi Anda dapat membaca kosong di kedua ujungnya sehingga Anda mungkin tahu itu awal atau akhir daftar. Juga, saya berasumsi kita membaca elemen saat ini dan selanjutnya untuk mengetahui apakah kita perlu bertukar.

Shreesh

Atau, jika kita memodifikasi swap operator sebagai "swap jika tidak dalam urutan menaik".

Shreesh