Kasus terburuk di tempat yang stabil?

Saya mengalami kesulitan menemukan sumber daya yang baik yang memberikan kasus terburuk di tempat algoritma penyortiran stabil . Adakah yang tahu sumber daya yang bagus? $O(n \ln n)$

Hanya pengingat, di tempat berarti menggunakan array yang diteruskan dan algoritma pengurutan hanya diperbolehkan untuk menggunakan ruang ekstra konstan. Stabil berarti bahwa elemen dengan kunci yang sama muncul dalam urutan yang sama dalam array yang diurutkan seperti yang mereka lakukan pada aslinya.

Misalnya, semacam gabungan naif adalah kasus terburuk dan stabil tetapi menggunakan ruang ekstra. Quicksort standar dapat dibuat stabil, sudah ada tetapi kasus terburuk . Heapsort sudah ada, kasus terburuk tetapi tidak stabil. Wikipedia memiliki bagan yang bagus tentang algoritma pengurutan yang memiliki kekurangan. Perhatikan bahwa tidak ada algoritma penyortiran yang mereka daftarkan yang memiliki ketiga kondisi stabilitas, kasus terburuk dan berada di tempat. $O(n \ln n)$ $O(n)$ $O(n^2)$ $O(n \ln n)$ $O(n \ln n)$

Saya telah menemukan sebuah makalah yang disebut "Praktis di tempat mergesort" oleh Katajainen, Pasanen dan Teuhola, yang mengklaim memiliki kasus terburuk di tempat varian mergesort stabil. Jika saya memahami hasil mereka dengan benar, mereka menggunakan (bottom-up?) Mergesort secara rekursif pada dari array dan yang terakhir dari array dan menggunakan yang kedua sebagai ruang awal untuk melakukan penggabungan. Saya masih membaca ini sehingga informasi lebih lanjut tentang apakah saya menafsirkan hasil mereka dengan benar dihargai. $O(n \ln n)$ $\frac{1}{4}$ $\frac{1}{2}$ $\frac{1}{4}$

Saya juga akan sangat tertarik pada kasus terburuk di tempat quicksort stabil. Dari apa yang saya pahami, memodifikasi quicksort menjadi case terburuk membutuhkan pemilihan poros yang tepat yang akan menghancurkan stabilitas yang biasanya akan dinikmati. $O(n \ln n)$ $O(n \ln n)$

Ini murni kepentingan teoretis dan saya tidak punya aplikasi praktis. Saya hanya ingin tahu algoritma yang memiliki ketiga fitur ini.

algorithms reference-request sorting in-place pengguna834
sumber

Ada pertanyaan serupa pada SO di sini dengan jawaban yang memberikan referensi yang saya berikan dalam pertanyaan. Saya percaya ini bukan pertanyaan duplikat karena saya meminta klarifikasi lebih lanjut, lebih banyak literatur, dan, dengan sedikit keberuntungan, deskripsi algoritma.

user834

Lihat pertanyaan ini di math.stackexchange.com.

Tsuyoshi Ito

Mengapa cara berbeda memilih poros di QuickSort menghancurkan stabilitasnya?

svick

@vick, satu-satunya cara saya tahu bagaimana membuat QuickSort menjadi terburuk

adalah memilih pivot lebih cerdas daripada acak. Cara yang saya pelajari untuk melakukannya adalah dengan menggunakan algoritma pemilihan, yang menggunakan algoritma median-of-median, yang menghancurkan stabilitas. Jika saya melewatkan sesuatu, tolong beri tahu saya.

O (n \ln n)

$O(n \ln n)$

user834

@ TsuyoshiIto, pertimbangkan untuk membuat ini jawaban. Juga, jika Anda bisa memberikan sketsa singkat tentang algoritma, saya pikir itu akan sangat membantu juga.

user834

Jawaban:

Ada beberapa algoritma yang semuanya di atas, dan hampir semuanya telah ditemukan dalam 30 tahun terakhir.

Mungkin yang paling baik adalah kelas algoritma yang disebut Block sort , termasuk versi (disebut WikiSort) oleh Kim dan Kutzner pada tahun 2008. Tidak hanya stabil dan sepenuhnya di tempat (O (1) memori overhead dalam model transdichotomous), itu juga adaptif, dan dengan demikian akan mengambil langkah lebih sedikit untuk mengurutkan daftar hampir diurutkan, konvergen ke perbandingan O (n) dalam kasus daftar yang sudah diurutkan. Anda dapat menemukan implementasi di C, C ++, dan Java di sini: https://github.com/BonzaiThePenguin/WikiSort

Yang juga menarik adalah algoritma GrailSort (juga semacam Blok) oleh Huang dan Langston (1989-1992), yang sebenarnya mengungguli WikiSort pada beberapa jenis kasus uji. Implementasi C ++ tersedia di sini: https://github.com/Mrrl/GrailSort

kuintopia
sumber

Anda dapat menulis mergesort yang stabil dan di tempat. Lihat ini untuk detailnya. Dengan kata-kata penulis sendiri:

Algoritme yang indah - gabungkan. Uji pada array terbalik untuk memahami cara kerja rotasi. Paling cepat dikenal di tempat yang stabil. Tidak ada risiko meledak tumpukan. Biaya: jumlah gerakan yang relatif tinggi. Tumpukan masih bisa mahal juga. Ini adalah semacam gabungan dengan gabungan cerdas di tempat yang 'memutar' sub array. Kode ini disalin dari perpustakaan C ++ stl dan diterjemahkan ke dalam bahasa Jawa.

Saya tidak akan menyalin kode di sini, tetapi Anda dapat menemukannya di tautan atau dengan memeriksa C ++ STL. Harap beri tahu saya jika Anda ingin saya mencoba memberikan deskripsi yang lebih terperinci tentang apa yang terjadi di sini.

Patrick87
sumber

O (\ln n)

$O(\ln n)$

O (1)

$O(1)$

O (\ln n)

$O(\ln n)$

Knuth mengatasinya di TAoCP juga.

Raphael

O (n \ln^{2} n)

$O(n\ln^2n)$

Silakan anggap ini sebagai komentar panjang tentang beberapa pemikiran praktis. Meskipun ini bukan jawaban untuk pertanyaan Anda, saya pikir Anda mungkin tertarik dengan diskusi Python ini:

$\lg(N!)$ $N-1$

[...]

Menggabungkan run yang berdekatan dengan panjang A dan B di tempat sangat sulit . Konstruksi teoretis diketahui dapat melakukannya, tetapi mereka terlalu sulit dan lambat untuk penggunaan praktis . Tetapi jika kita memiliki memori temp sama dengan min (A, B), itu mudah.

Sumber: bugs.python.org , penulis: Tim Peters

$\mathcal{O}(n \log n)$

Perhatikan juga bahwa Timsort berkinerja baik pada array yang sudah diurutkan.

Jadi Python memanfaatkan Timsort (yang merupakan Mergesort dengan beberapa tweak) dan ketika saya telah melihat implementasi Java beberapa tahun yang lalu, itu juga Mergesort (saya pikir mereka sekarang juga menggunakan Timsort).

Martin Thoma
sumber