Bilangan bulat "Almost sorting" dalam waktu linier

16

Saya tertarik untuk menyortir array nilai integer positif L=v1,,vn dalam waktu linier (dalam model RAM dengan ukuran biaya seragam, yaitu, bilangan bulat dapat memiliki ukuran logaritmik tetapi operasi aritmatika pada mereka diasumsikan ambil satuan waktu). Tentu saja, ini tidak mungkin dengan algoritma pengurutan berbasis perbandingan, jadi saya tertarik untuk menghitung semacam "perkiraan", yaitu, menghitung beberapa permutasi vσ(1),,vσ(n) dari Lyang tidak benar-benar diurutkan secara umum tetapi "perkiraan yang baik" dari versi L diurutkan . Saya akan berasumsi bahwa kita sedang mengurutkan bilangan bulat dalam urutan menurun karena itu membuat sekuelnya sedikit lebih menyenangkan untuk dinyatakan, tetapi tentu saja orang bisa mengutarakan masalahnya dengan cara sebaliknya.

Salah satu kriteria yang mungkin untuk jenis perkiraan adalah sebagai berikut (*): membiarkan N menjadi ivi , untuk setiap 1in , kami mengharuskan vσ(i)N/i (yaitu, "kuasi-diurutkan" "daftar dibatasi dari atas oleh fungsi penurunan iN/i ). Mudah untuk melihat bahwa jenis yang sebenarnya memenuhi ini: vσ(2) harus tidak lebih besar dari vσ(1)jadi paling banyak (vσ(1)+vσ(2))/2 yang N/2 , dan secara umum vσ(i) harus tidak lebih besar dari (jivσ(i))/i yang N/i .

Misalnya, persyaratan (*) dapat dicapai dengan algoritma di bawah ini (disarankan oleh @Louis). Pertanyaanku adalah: Apakah ada pekerjaan yang ada pada tugas ini dari "hampir menyortir" bilangan bulat dalam waktu linier, dengan memaksakan beberapa persyaratan seperti (*) yang jenis nyata akan memuaskan? Apakah algoritme di bawah ini, atau beberapa varian darinya, memiliki nama mapan?

Sunting: memperbaiki algoritme dan menambahkan lebih banyak penjelasan


Algoritma:

INPUT: V an array of size n containing positive integers
OUTPUT: T

N = Σ_{i<n} V[i]
Create n buckets indexed by 1..n
For i in 1..n
| Add V[i] into the bucket min(floor(N/V[i]),n)
+

For bucket 1 to bucket n
| For each element in the bucket
| | Append element to T
| +
+

Algoritma ini berfungsi sebagaimana dimaksud untuk alasan berikut:

  1. Jika elemen v ada di dalam ember j maka vN/j .

    v dimasukkan ke dalam emberj=min(N/v,n) , dengan demikianjN/vN/v

  2. Jika elemen v ada di dalam ember j maka N/(j+1)<v atau j=n .

    v dimasukkan ke dalam emberj=min(N/v,n) , dengan demikianj=N/v atauj=n . Dalam kasus pertamaj=N/v yang berartijN/v<j+1 dan dengan demikianN/(j+1)<v .

  3. Untuk j<n , ada, paling banyak, elemen j dalam bucket dari 1 hingga j .

    Misalkan j<n dan misalkan k adalah jumlah total elemen dalam salah satu ember 1..j. Dengan 2. kita mengetahui bahwa setiap elemen v dalam ember i (dengan ij ) sedemikian rupa sehingga N/(j+1)N/(i+1)<v . Oleh karena itu jumlah K dari semua elemen dalam ember dari 1 hingga j lebih besar dari k×N/(J+1) . Tetapi jumlahK ini juga kurang dariN sehinggak×N/(j+1)<KN dan dengan demikian k/(j+1)<1 yang memberi kitak<j+1 ataukj .

  4. T memenuhi (*) yaituelemen ke-j dariT sedemikian rupa sehinggaT[j]N/j

    Dengan 3. kita memiliki T[j] , elemen ke- j dari T , berasal dari ember i dengan ij oleh karena itu T[j]N/iN/j .

  5. Algoritma ini membutuhkan waktu linier.

    Perhitungan N membutuhkan waktu linier. Bucket dapat diimplementasikan dengan daftar tertaut yang memiliki penyisipan dan iterasi O(1) . Loop bersarang berjalan sebanyak yang ada elemen (yaitu n kali).

a3nm
sumber
1
Tidak mengabaikan pertanyaan (+1, ini pertanyaan yang bagus) tetapi bukankah radix sort akan melakukan lebih dari yang Anda butuhkan?
user541686
@Mehrdad: Terima kasih atas komentar Anda! Sortir Radix akan mengurutkan integer, tetapi akan membutuhkan waktu . O(nlog(maxivi))
a3nm
Bisakah Anda mengomentari apa yang sebenarnya tidak diinginkan tentang kompleksitas waktu itu? Apakah Anda memiliki satu bilangan bulat yang sangat besar dan yang lainnya kecil, misalnya?
user541686
1
@ a3nm jenis radix bukan O (n log n) itu O (n) maka linier jika ukuran bilangan bulat diperbaiki, misalnya angka 32 bit atau angka 64 bit. Apakah angka yang Anda sortir memiliki ukuran variabel?
Xavier Combelle
1
@ XavierCombelle: Ya, saya sedang bekerja dalam model RAM dan saya tidak bisa mengira bahwa bilangan bulat input dibatasi oleh konstanta.
a3nm

Jawaban:

8

Ini terdengar sangat mirip dengan algoritma ASort. Lihat artikel ini oleh Giesen et. Al.:

https://www.inf.ethz.ch/personal/smilos/asort3.pdf

nn2/ν(n)nlog(ν(n))ν(n)<n


EDIT , sebagai tanggapan atas klarifikasi dalam pertanyaan:

N/V[i]

lg(n)n

Trixie Wolf
sumber
1
Terima kasih telah mengarahkan kami ke artikel ini! Memang itu sedikit terkait dengan pertanyaan itu. Namun, algoritma saya (baik versi asli maupun versi revisi yang sedikit berbeda) tidak begitu mirip dengan ASort ;. Pertama, saya percaya algoritma saya berjalanHAI(n), tidak dalam waktu superlinear seperti ASort. Kedua, kriteria (*) sangat berbeda dari perkiraan jarak footrule Spearman; misalnya, kriteria (*) lebih atau kurang ketat tergantung pada nilai-nilai bilangan bulat, tidak seperti jarak footrule. Ketiga, meskipun algoritme dan ASort kami adalah elemen penyemenan, kriterianya sangat berbeda.
a3nm
@ a3nm Klarifikasi apa yang Anda poskan di atas menyarankan Anda menggunakan jenis ember , yang linear (dan bukan berbasis perbandingan, yang berarti menguji dua item terhadap satu sama lain). Masalahnya adalah itu tidak bekerja untuk semua bilangan bulat matematika. Ini hanya berfungsi jika ukuran bilangan bulat dibatasi.
Trixie Wolf
Ketika Anda mengatakan "Itu hanya berfungsi jika ukuran bilangan bulat dibatasi", saya pikir ini hanya benar jika saya benar-benar menyortir bilangan bulat. Tetapi secara umum algoritma yang saya posting tidak benar-benar mengurutkan mereka, itu hanya menegakkan kriteria yang lebih lemah (*). Jadi saya pikir itu berjalan dalam waktu linier bahkan ketika ukuran bilangan bulat tidak dibatasi.
a3nm
2
@ a3nm Itu tidak linier. Lihat respons saya yang diperluas di atas.
Trixie Wolf
Terima kasih atas jawabannya, dan maaf atas keterlambatannya. Saya pikir ada beberapa kebingungan tentang model. Saya bekerja dalam model RAM dengan ukuran waktu yang seragam (seperti pada van Emde Boas, Model Mesin dan Simulasi, dalam Handbook of Computation): sehingga angka yang saya manipulasi dapat memiliki ukuran logaritmik, tetapi operasi aritmatika pada angka-angka ini memiliki biaya satuan. Saya telah mengedit pertanyaan saya sesuai dengan itu. Saya berpikir bahwa, dalam model ini, algoritma yang saya usulkan benar-benar berjalan dalam waktu linier (tapi tentu saja dalam model ini)ncatatannbatas bawah untuk penyortiran berbasis perbandingan aktual masih berlaku).
a3nm
2

Ternyata, pertanyaan saya agak tidak relevan. Memang, saya bekerja pada mesin RAM dengan ukuran biaya yang seragam (yaitu, kami memiliki register yang registernya tidak harus berukuran konstan tetapi dapat menyimpan bilangan bulat ukuran logaritmik dalam input paling banyak, dan operasi pada register ini membutuhkan waktu konstan, termasuk setidaknya penambahan). Dan pada kenyataannya, dalam model ini, penyortiran bilangan bulat (dengan dasarnya melakukan semacam radix) dapat dilakukan dalam waktu linier. Ini dijelaskan dalam makalah 1996 oleh Grandjean, Sorting, waktu linier dan masalah kepuasan .

(Ini tidak menjawab pertanyaan saya tentang apakah ada gagasan yang dipelajari dengan baik tentang "hampir menyortir" satu set bilangan bulat, tetapi agar mereka menjadi menarik orang mungkin akan membutuhkan gagasan yang lebih lemah ini untuk lebih mudah ditegakkan, yaitu, bekerja pada yang lebih lemah. model atau entah bagaimana berjalan dalam waktu sublinear. Namun, saya saat ini tidak mengetahui perasaan di mana ini akan terjadi.)

a3nm
sumber