Saya tertarik untuk menyortir array nilai integer positif 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 dari yang tidak benar-benar diurutkan secara umum tetapi "perkiraan yang baik" dari versi 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 menjadi , untuk setiap , kami mengharuskan (yaitu, "kuasi-diurutkan" "daftar dibatasi dari atas oleh fungsi penurunan ). Mudah untuk melihat bahwa jenis yang sebenarnya memenuhi ini: harus tidak lebih besar dari jadi paling banyak yang , dan secara umum harus tidak lebih besar dari yang .
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:
- Jika elemen ada di dalam ember maka .
dimasukkan ke dalam ember , dengan demikian
- Jika elemen ada di dalam ember maka atau .
dimasukkan ke dalam ember , dengan demikian atau . Dalam kasus pertama yang berarti dan dengan demikian .
Untuk , ada, paling banyak, elemen dalam bucket dari 1 hingga .
Misalkan dan misalkan adalah jumlah total elemen dalam salah satu ember 1..j. Dengan 2. kita mengetahui bahwa setiap elemen dalam ember (dengan ) sedemikian rupa sehingga . Oleh karena itu jumlah dari semua elemen dalam ember dari hingga lebih besar dari . Tetapi jumlah ini juga kurang dari sehingga dan dengan demikian yang memberi kita atau .
memenuhi (*) yaituelemen ke- dari sedemikian rupa sehingga
Dengan 3. kita memiliki , elemen ke- dari , berasal dari ember dengan oleh karena itu .
Algoritma ini membutuhkan waktu linier.
Perhitungan membutuhkan waktu linier. Bucket dapat diimplementasikan dengan daftar tertaut yang memiliki penyisipan dan iterasi . Loop bersarang berjalan sebanyak yang ada elemen (yaitu kali).
Jawaban:
Ini terdengar sangat mirip dengan algoritma ASort. Lihat artikel ini oleh Giesen et. Al.:
https://www.inf.ethz.ch/personal/smilos/asort3.pdf
EDIT , sebagai tanggapan atas klarifikasi dalam pertanyaan:
sumber
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.)
sumber