Jenis gelembung itu mengerikan. Itu selalu O (n ^ 2). Setidaknya keluarkan itu dari jawaban Anda agar itu benar.
jjnguy
79
jjnguy, itu salah sekali. Saya pikir Anda perlu mengambil kembali kelas algoritme Anda. Pada data yang hampir diurutkan (ini kasus adaptif) itu adalah O (N). Namun, dibutuhkan 2 melewati data dan Penyisipan hanya membutuhkan 1 untuk data yang hampir diurutkan, yang membuat Penyisipan pemenang. Gelembung masih baik
mmcdole
3
Kinerja menurun sangat buruk jika data Anda hampir tidak pernah diurutkan. Saya masih tidak akan menggunakannya, secara pribadi.
Blorgbeard keluar
5
Tautan itu terputus ketika saya mencobanya. Coba ini sebagai gantinya: sorting-algorithms.com
Michael La Voie
107
Hanya beberapa item => SORT INSERTION
Sebagian besar item sudah diurutkan => SORT INSERTION
Khawatir tentang skenario terburuk => HEAP SORT
Tertarik pada hasil kasus rata-rata yang baik => QUICKSORT
Item diambil dari alam semesta yang padat => BUCKET SORT
Berkeinginan untuk menulis kode sesedikit mungkin => INSERTION SORT
Itulah jawaban yang sebenarnya saya cari, saya membaca buku tapi sepertinya saya tidak menemukan penjelasan yang jelas untuk pemilihan alogoritma pada kasus tertentu, dapatkah Anda menjelaskannya atau mengirimkan tautan sehingga saya dapat mengikuti lebih sedikit? Terima kasih
Simran kaur
9
Anda harus menambahkan "Data sudah diurutkan berdasarkan kriteria lain => MERGE SORT"
Jim Hunziker
30
timsort
Timsort adalah "mergesort alami, adaptif, stabil" dengan " kinerja supernatural pada banyak jenis array yang dipesan sebagian (kurang dari lg (N!) Yang diperlukan, dan sesedikit N-1)". Built-in pythonsort()telah menggunakan algoritma ini selama beberapa waktu, tampaknya dengan hasil yang baik. Ini secara khusus dirancang untuk mendeteksi dan mengambil keuntungan dari urutan diurutkan sebagian dalam input, yang sering terjadi dalam dataset nyata. Sering terjadi di dunia nyata bahwa perbandingan jauh lebih mahal daripada menukar item dalam daftar, karena orang biasanya hanya menukar pointer, yang sangat sering menjadikan timsort pilihan yang sangat baik. Namun, jika Anda tahu bahwa perbandingan Anda selalu sangat murah (menulis program mainan untuk mengurutkan integer 32-bit, misalnya), ada algoritma lain yang cenderung berkinerja lebih baik. Cara termudah untuk memanfaatkan timsort tentu saja menggunakan Python, tetapi karena Python adalah open source, Anda mungkin juga dapat meminjam kode. Sebagai alternatif, uraian di atas mengandung lebih dari cukup detail untuk menulis implementasi Anda sendiri.
@ JF Sebastian: timsort jauh lebih cepat daripada lg(n!)perbandingan pada array yang hampir diurutkan, semua jalan sampai ke O(n)! | @behrooz: Tidak ada jenis perbandingan yang dapat memiliki kasus rata-rata lebih baik daripada O(n log n), dan lg(n!)sekarang O(n log n). Jadi kasus terburuk timsort secara asimptotik tidak lebih buruk daripada jenis perbandingan lainnya. Selain itu kasus terbaiknya lebih baik daripada atau sama dengan jenis perbandingan lainnya.
Artelius
3
Timsort masih O (nlogn) dalam kasus terburuk, tetapi kasus bagusnya cukup menyenangkan. Berikut ini perbandingan, dengan beberapa grafik: stromberg.dnsalias.org/~strombrg/sort-comparison Perhatikan bahwa timsort di Cython tidak secepat secepat timon yang dibangun oleh Python di C.
user1277476
19
Jenis penyisipan dengan perilaku berikut:
Untuk setiap elemen kdalam slot 1..n, periksa dulu apakah el[k] >= el[k-1]. Jika demikian, buka elemen berikutnya. (Jelas melewatkan elemen pertama.)
Jika tidak, gunakan pencarian biner dalam elemen 1..k-1untuk menentukan lokasi penyisipan, lalu geser elemen tersebut. (Anda mungkin melakukan ini hanya jika k>Tdi mana Tbeberapa nilai ambang batas, dengan kecil kini berlebihan.)
Metode ini menghasilkan perbandingan paling sedikit.
Saya pikir bubble sort bisa mengalahkan ini jika jumlah elemen yang tidak disortir sangat kecil (seperti, satu atau dua), tetapi secara umum ini menurut saya mungkin merupakan solusi terbaik.
Sol
Karena langkah 1, untuk setiap elemen yang sudah diurutkan ada tepat satu perbandingan dan nol data bergerak, yang jelas yang terbaik yang dapat Anda lakukan. Langkah 2 adalah yang Anda bisa tingkatkan, tetapi gelembung akan memindahkan jumlah elemen yang sama dan mungkin memiliki lebih banyak perbandingan, tergantung pada impl Anda.
Jason Cohen
Sebenarnya, pada pemikiran lebih lanjut saya pikir semacam gelembung lebih kuat daripada yang saya pikirkan. Ini sebenarnya pertanyaan yang cukup sulit. Misalnya, jika Anda mengambil kasus di mana daftar sepenuhnya diurutkan kecuali elemen yang harus terakhir adalah yang pertama, semacam gelembung akan jauh mengungguli apa yang Anda gambarkan.
Sol
Saya mencoba menerapkan ini tetapi pencarian biner tidak banyak perbaikan karena Anda masih harus memindahkan seluruh blok untuk memasukkan elemen. Jadi, bukannya 2xrange Anda mendapatkan rentang + logb (rentang).
Berbasis quicksort, tetapi menghindari perilaku terburuk yang dimiliki quicksort untuk daftar yang hampir diurutkan.
Kuncinya adalah bahwa algoritma semacam ini mendeteksi kasus di mana quicksort masuk ke mode terburuk dan beralih ke tumpukan atau gabungan. Partisi yang hampir diurutkan terdeteksi oleh beberapa metode partisi non-naif dan partisi kecil ditangani dengan menggunakan jenis penyisipan.
Anda mendapatkan yang terbaik dari semua algoritma penyortiran utama untuk biaya kode yang lebih banyak dan kompleksitas. Dan Anda dapat yakin bahwa Anda tidak akan pernah mengalami perilaku terburuk, tidak peduli seperti apa data Anda.
Jika Anda seorang programmer C ++ periksa algoritma std :: sort Anda. Ini mungkin sudah menggunakan semacam introspektif secara internal.
Splaysort adalah metode penyortiran yang tidak jelas berdasarkan pohon hamparan , sejenis pohon biner adaptif. Splaysort baik tidak hanya untuk data yang diurutkan sebagian, tetapi juga sebagian data yang diurutkan mundur, atau memang data apa pun yang memiliki jenis pesanan yang sudah ada sebelumnya. Ini adalah O (nlogn) dalam kasus umum, dan O (n) dalam kasus di mana data diurutkan dalam beberapa cara (maju, mundur, pipa organ, dll.).
Keuntungan besar dari penyisipan adalah bahwa ia tidak kembali ke perilaku O (n ^ 2) ketika data tidak diurutkan sama sekali, jadi Anda tidak perlu benar-benar yakin bahwa data diurutkan sebagian sebelum menggunakannya .
Kerugiannya adalah overhead ruang tambahan dari struktur pohon splay yang dibutuhkannya, serta waktu yang dibutuhkan untuk membangun dan menghancurkan pohon splay. Tetapi tergantung pada ukuran data dan jumlah pra-sortir yang Anda harapkan, overhead mungkin layak untuk peningkatan kecepatan.
Smoothsort Dijkstra sangat cocok untuk data yang sudah diurutkan. Ini adalah varian heapsort yang berjalan dalam O (n lg n) kasus terburuk dan O (n) kasus terbaik. Saya menulis analisis algoritme, jika Anda penasaran bagaimana cara kerjanya.
Natural mergesort adalah satu lagi yang sangat bagus untuk ini - ini adalah varian mergesort bottom-up yang bekerja dengan memperlakukan input sebagai gabungan dari beberapa rentang diurutkan yang berbeda, kemudian menggunakan algoritma gabungan untuk bergabung bersama-sama. Anda ulangi proses ini sampai semua rentang input diurutkan. Ini berjalan dalam waktu O (n) jika data sudah diurutkan dan O (n lg n) kasus terburuk. Ini sangat elegan, meskipun dalam praktiknya tidak sebagus beberapa jenis adaptif lainnya seperti Timsort atau smoothsort.
apa konstanta runtime smoothsort dibandingkan dengan algoritma pengurutan lainnya? (yaitu runtime (smoothsort) / runtime (insertionsort) untuk data yang sama)
Arne Babenhauserheide
4
Jika elemen sudah diurutkan atau hanya ada beberapa elemen, itu akan menjadi kasus penggunaan yang sempurna untuk Penyisipan Sortir!
Sortasi penyisipan membutuhkan waktu O (n + jumlah inversi).
Inversi adalah pasangan (i, j)sedemikian rupa sehingga i < j && a[i] > a[j]. Yaitu, pasangan yang rusak.
Salah satu ukuran menjadi "hampir diurutkan" adalah jumlah inversi --- seseorang dapat mengambil "data yang hampir diurutkan" untuk berarti data dengan sedikit inversi. Jika seseorang tahu jumlah inversi menjadi linier (misalnya, Anda baru saja menambahkan O (1) elemen ke daftar diurutkan), penyisipan membutuhkan waktu O (n) waktu.
Seperti yang orang lain katakan, berhati-hatilah dengan Quicksort yang naif - yang dapat memiliki kinerja O (N ^ 2) pada data yang diurutkan atau hampir diurutkan. Namun demikian, dengan algoritma yang tepat untuk pilihan pivot (baik acak atau median-of-three - lihat Memilih Pivot untuk Quicksort ), Quicksort masih akan berfungsi dengan baik.
Secara umum, kesulitan dalam memilih algoritma seperti insert sort adalah dalam menentukan kapan data cukup rusak sehingga Quicksort benar-benar akan lebih cepat.
Saya tidak akan berpura-pura memiliki semua jawaban di sini, karena saya pikir mendapatkan jawaban yang sebenarnya mungkin memerlukan pengkodean algoritma dan profil mereka terhadap sampel data yang representatif. Tetapi saya telah memikirkan pertanyaan ini sepanjang malam, dan inilah yang terjadi pada saya sejauh ini, dan beberapa tebakan tentang apa yang terbaik di mana.
Biarkan N menjadi jumlah item total, M menjadi nomor tidak sesuai pesanan.
Bubble sort harus membuat sesuatu seperti 2 * M + 1 melewati semua item N. Jika M sangat kecil (0, 1, 2?), Saya pikir ini akan sangat sulit dikalahkan.
Jika M kecil (misalkan kurang dari log N), jenis penyisipan akan memiliki kinerja rata-rata yang hebat. Namun, kecuali ada trik yang tidak saya lihat, itu akan memiliki kinerja kasus terburuk yang sangat buruk. (Benar? Jika item terakhir dalam urutan diutamakan, maka Anda harus memasukkan setiap item, sejauh yang saya bisa lihat, yang akan mematikan kinerja.) Saya menduga ada algoritma pengurutan yang lebih andal di luar sana untuk ini kasus, tapi saya tidak tahu apa itu.
Jika M lebih besar (katakanlah sama atau lebih besar dari log N), jenis introspektif hampir pasti yang terbaik.
Pengecualian untuk semua itu: Jika Anda benar-benar tahu sebelumnya elemen mana yang tidak disortir, maka taruhan terbaik Anda adalah menarik item-item itu keluar, mengurutkannya menggunakan pengurutan introspektif, dan menggabungkan kedua daftar yang diurutkan menjadi satu daftar yang diurutkan. Jika Anda dapat dengan cepat mengetahui item mana yang rusak, ini akan menjadi solusi umum yang bagus juga - tetapi saya belum dapat menemukan cara sederhana untuk melakukan ini.
Pikiran lebih lanjut (dalam semalam): Jika M + 1 <N / M, maka Anda dapat memindai daftar untuk mencari N / M dalam satu baris yang diurutkan, dan kemudian memperluas menjalankan itu di kedua arah untuk menemukan hasil di luar item -order. Itu akan membutuhkan paling banyak perbandingan 2N. Anda kemudian dapat mengurutkan item yang tidak disortir, dan melakukan gabungan diurutkan pada dua daftar. Total perbandingan harus kurang dari sesuatu seperti 4N + M log2 (M), yang akan mengalahkan rutin penyortiran non-khusus, saya pikir. (Bahkan berpikir lebih jauh: ini lebih sulit daripada yang saya pikirkan, tetapi saya masih berpikir itu cukup masuk akal.)
Interpretasi lain dari pertanyaan ini adalah bahwa mungkin ada banyak item yang tidak sesuai pesanan, tetapi mereka sangat dekat dengan tempat mereka seharusnya berada dalam daftar. (Bayangkan dimulai dengan daftar yang disortir dan bertukar setiap item lain dengan item yang datang setelah itu.) Dalam hal ini saya pikir bubble sort berkinerja sangat baik - saya pikir jumlah lintasan akan sebanding dengan yang terjauh dari tempat item adalah. Jenis penyisipan akan bekerja dengan buruk, karena setiap item yang tidak dipesan akan memicu penyisipan. Saya menduga jenis introspektif atau sesuatu seperti itu akan bekerja dengan baik juga.
Jika Anda membutuhkan implementasi spesifik untuk menyortir algoritma, struktur data atau apa pun yang memiliki tautan ke di atas, dapatkah saya merekomendasikan Anda proyek "Struktur Data dan Algoritma" yang luar biasa pada CodePlex?
Ini akan memiliki semua yang Anda butuhkan tanpa menciptakan kembali roda.
Kumpulan algoritma penyortiran yang bagus untuk tujuan ini dalam jawaban, tampaknya tidak memiliki Gnome Sort , yang juga cocok, dan mungkin membutuhkan upaya implementasi yang paling sedikit.
Jenis penyisipan adalah kasus O (n) terbaik pada input yang diurutkan. Dan sangat dekat pada sebagian besar input yang diurutkan (lebih baik daripada quick sort).
Konsistensi tidak menjadi perhatian di sini. Heapsort akan memberikan O (n lg n) bahkan pada data yang diurutkan, dan tidak benar-benar adaptif. Opsi yang dapat dilakukan adalah: Jenis penyisipan, Timsort, dan Bubblesort.
Maks
0
Bubble-sort (atau, lebih aman lagi, semacam bubble bi-directional) kemungkinan ideal untuk sebagian besar daftar yang diurutkan, meskipun saya bertaruh semacam comb-tweak (dengan ukuran celah awal yang jauh lebih rendah) akan menjadi sedikit lebih cepat ketika daftar tidak t cukup sempurna diurutkan. Sisir mengurutkan degradasi ke bubble-sort.
Ini "sejauh yang saya ketahui" tes efisiensi algoritma mencerahkan hari saya :) Menjadi serius, meskipun, ketika menulis "hapus dan sisipkan" maksud Anda Penyisipan Sortir (yang sudah disebutkan dalam jawaban sebelumnya), atau apakah Anda menawarkan jenis baru dari algoritma? Jika demikian, perluas jawaban Anda.
yoniLavi
0
Bubble sort pasti adalah pemenang. Yang berikutnya pada radar adalah sorting sort.
Saya sarankan Anda melihat jawaban yang tersedia sebelum memposting untuk menghindari duplikat.
angainor
-1
Jauhkan dari QuickSort - sangat tidak efisien untuk data yang diurutkan sebelumnya. Jenis penyisipan menangani data yang hampir diurutkan dengan baik dengan memindahkan nilai sesedikit mungkin.
Jawaban:
Berdasarkan metode yang sangat ilmiah menonton gif animasi saya akan mengatakan jenis Penyisipan dan Gelembung adalah kandidat yang baik.
sumber
Hanya beberapa item => SORT INSERTION
Sebagian besar item sudah diurutkan => SORT INSERTION
Khawatir tentang skenario terburuk => HEAP SORT
Tertarik pada hasil kasus rata-rata yang baik => QUICKSORT
Item diambil dari alam semesta yang padat => BUCKET SORT
Berkeinginan untuk menulis kode sesedikit mungkin => INSERTION SORT
sumber
timsort
Timsort adalah "mergesort alami, adaptif, stabil" dengan " kinerja supernatural pada banyak jenis array yang dipesan sebagian (kurang dari lg (N!) Yang diperlukan, dan sesedikit N-1)". Built-in python
sort()telah menggunakan algoritma ini selama beberapa waktu, tampaknya dengan hasil yang baik. Ini secara khusus dirancang untuk mendeteksi dan mengambil keuntungan dari urutan diurutkan sebagian dalam input, yang sering terjadi dalam dataset nyata. Sering terjadi di dunia nyata bahwa perbandingan jauh lebih mahal daripada menukar item dalam daftar, karena orang biasanya hanya menukar pointer, yang sangat sering menjadikan timsort pilihan yang sangat baik. Namun, jika Anda tahu bahwa perbandingan Anda selalu sangat murah (menulis program mainan untuk mengurutkan integer 32-bit, misalnya), ada algoritma lain yang cenderung berkinerja lebih baik. Cara termudah untuk memanfaatkan timsort tentu saja menggunakan Python, tetapi karena Python adalah open source, Anda mungkin juga dapat meminjam kode. Sebagai alternatif, uraian di atas mengandung lebih dari cukup detail untuk menulis implementasi Anda sendiri.sumber
lg(n!)perbandingan pada array yang hampir diurutkan, semua jalan sampai keO(n)! | @behrooz: Tidak ada jenis perbandingan yang dapat memiliki kasus rata-rata lebih baik daripadaO(n log n), danlg(n!)sekarangO(n log n). Jadi kasus terburuk timsort secara asimptotik tidak lebih buruk daripada jenis perbandingan lainnya. Selain itu kasus terbaiknya lebih baik daripada atau sama dengan jenis perbandingan lainnya.Jenis penyisipan dengan perilaku berikut:
kdalam slot1..n, periksa dulu apakahel[k] >= el[k-1]. Jika demikian, buka elemen berikutnya. (Jelas melewatkan elemen pertama.)1..k-1untuk menentukan lokasi penyisipan, lalu geser elemen tersebut. (Anda mungkin melakukan ini hanya jikak>Tdi manaTbeberapa nilai ambang batas, dengan kecilkini berlebihan.)Metode ini menghasilkan perbandingan paling sedikit.
sumber
Coba semacam introspektif. http://en.wikipedia.org/wiki/Introsort
Berbasis quicksort, tetapi menghindari perilaku terburuk yang dimiliki quicksort untuk daftar yang hampir diurutkan.
Kuncinya adalah bahwa algoritma semacam ini mendeteksi kasus di mana quicksort masuk ke mode terburuk dan beralih ke tumpukan atau gabungan. Partisi yang hampir diurutkan terdeteksi oleh beberapa metode partisi non-naif dan partisi kecil ditangani dengan menggunakan jenis penyisipan.
Anda mendapatkan yang terbaik dari semua algoritma penyortiran utama untuk biaya kode yang lebih banyak dan kompleksitas. Dan Anda dapat yakin bahwa Anda tidak akan pernah mengalami perilaku terburuk, tidak peduli seperti apa data Anda.
Jika Anda seorang programmer C ++ periksa algoritma std :: sort Anda. Ini mungkin sudah menggunakan semacam introspektif secara internal.
sumber
Splaysort adalah metode penyortiran yang tidak jelas berdasarkan pohon hamparan , sejenis pohon biner adaptif. Splaysort baik tidak hanya untuk data yang diurutkan sebagian, tetapi juga sebagian data yang diurutkan mundur, atau memang data apa pun yang memiliki jenis pesanan yang sudah ada sebelumnya. Ini adalah O (nlogn) dalam kasus umum, dan O (n) dalam kasus di mana data diurutkan dalam beberapa cara (maju, mundur, pipa organ, dll.).
Keuntungan besar dari penyisipan adalah bahwa ia tidak kembali ke perilaku O (n ^ 2) ketika data tidak diurutkan sama sekali, jadi Anda tidak perlu benar-benar yakin bahwa data diurutkan sebagian sebelum menggunakannya .
Kerugiannya adalah overhead ruang tambahan dari struktur pohon splay yang dibutuhkannya, serta waktu yang dibutuhkan untuk membangun dan menghancurkan pohon splay. Tetapi tergantung pada ukuran data dan jumlah pra-sortir yang Anda harapkan, overhead mungkin layak untuk peningkatan kecepatan.
Sebuah kertas pada splaysort diterbitkan pada Software - Praktek & Experience.
sumber
penyisipan atau semacam shell!
sumber
Smoothsort Dijkstra sangat cocok untuk data yang sudah diurutkan. Ini adalah varian heapsort yang berjalan dalam O (n lg n) kasus terburuk dan O (n) kasus terbaik. Saya menulis analisis algoritme, jika Anda penasaran bagaimana cara kerjanya.
Natural mergesort adalah satu lagi yang sangat bagus untuk ini - ini adalah varian mergesort bottom-up yang bekerja dengan memperlakukan input sebagai gabungan dari beberapa rentang diurutkan yang berbeda, kemudian menggunakan algoritma gabungan untuk bergabung bersama-sama. Anda ulangi proses ini sampai semua rentang input diurutkan. Ini berjalan dalam waktu O (n) jika data sudah diurutkan dan O (n lg n) kasus terburuk. Ini sangat elegan, meskipun dalam praktiknya tidak sebagus beberapa jenis adaptif lainnya seperti Timsort atau smoothsort.
sumber
Jika elemen sudah diurutkan atau hanya ada beberapa elemen, itu akan menjadi kasus penggunaan yang sempurna untuk Penyisipan Sortir!
sumber
Sortasi penyisipan membutuhkan waktu O (n + jumlah inversi).
Inversi adalah pasangan
(i, j)sedemikian rupa sehinggai < j && a[i] > a[j]. Yaitu, pasangan yang rusak.Salah satu ukuran menjadi "hampir diurutkan" adalah jumlah inversi --- seseorang dapat mengambil "data yang hampir diurutkan" untuk berarti data dengan sedikit inversi. Jika seseorang tahu jumlah inversi menjadi linier (misalnya, Anda baru saja menambahkan O (1) elemen ke daftar diurutkan), penyisipan membutuhkan waktu O (n) waktu.
sumber
Seperti yang orang lain katakan, berhati-hatilah dengan Quicksort yang naif - yang dapat memiliki kinerja O (N ^ 2) pada data yang diurutkan atau hampir diurutkan. Namun demikian, dengan algoritma yang tepat untuk pilihan pivot (baik acak atau median-of-three - lihat Memilih Pivot untuk Quicksort ), Quicksort masih akan berfungsi dengan baik.
Secara umum, kesulitan dalam memilih algoritma seperti insert sort adalah dalam menentukan kapan data cukup rusak sehingga Quicksort benar-benar akan lebih cepat.
sumber
Saya tidak akan berpura-pura memiliki semua jawaban di sini, karena saya pikir mendapatkan jawaban yang sebenarnya mungkin memerlukan pengkodean algoritma dan profil mereka terhadap sampel data yang representatif. Tetapi saya telah memikirkan pertanyaan ini sepanjang malam, dan inilah yang terjadi pada saya sejauh ini, dan beberapa tebakan tentang apa yang terbaik di mana.
Biarkan N menjadi jumlah item total, M menjadi nomor tidak sesuai pesanan.
Bubble sort harus membuat sesuatu seperti 2 * M + 1 melewati semua item N. Jika M sangat kecil (0, 1, 2?), Saya pikir ini akan sangat sulit dikalahkan.
Jika M kecil (misalkan kurang dari log N), jenis penyisipan akan memiliki kinerja rata-rata yang hebat. Namun, kecuali ada trik yang tidak saya lihat, itu akan memiliki kinerja kasus terburuk yang sangat buruk. (Benar? Jika item terakhir dalam urutan diutamakan, maka Anda harus memasukkan setiap item, sejauh yang saya bisa lihat, yang akan mematikan kinerja.) Saya menduga ada algoritma pengurutan yang lebih andal di luar sana untuk ini kasus, tapi saya tidak tahu apa itu.
Jika M lebih besar (katakanlah sama atau lebih besar dari log N), jenis introspektif hampir pasti yang terbaik.
Pengecualian untuk semua itu: Jika Anda benar-benar tahu sebelumnya elemen mana yang tidak disortir, maka taruhan terbaik Anda adalah menarik item-item itu keluar, mengurutkannya menggunakan pengurutan introspektif, dan menggabungkan kedua daftar yang diurutkan menjadi satu daftar yang diurutkan. Jika Anda dapat dengan cepat mengetahui item mana yang rusak, ini akan menjadi solusi umum yang bagus juga - tetapi saya belum dapat menemukan cara sederhana untuk melakukan ini.
Pikiran lebih lanjut (dalam semalam): Jika M + 1 <N / M, maka Anda dapat memindai daftar untuk mencari N / M dalam satu baris yang diurutkan, dan kemudian memperluas menjalankan itu di kedua arah untuk menemukan hasil di luar item -order. Itu akan membutuhkan paling banyak perbandingan 2N. Anda kemudian dapat mengurutkan item yang tidak disortir, dan melakukan gabungan diurutkan pada dua daftar. Total perbandingan harus kurang dari sesuatu seperti 4N + M log2 (M), yang akan mengalahkan rutin penyortiran non-khusus, saya pikir. (Bahkan berpikir lebih jauh: ini lebih sulit daripada yang saya pikirkan, tetapi saya masih berpikir itu cukup masuk akal.)
Interpretasi lain dari pertanyaan ini adalah bahwa mungkin ada banyak item yang tidak sesuai pesanan, tetapi mereka sangat dekat dengan tempat mereka seharusnya berada dalam daftar. (Bayangkan dimulai dengan daftar yang disortir dan bertukar setiap item lain dengan item yang datang setelah itu.) Dalam hal ini saya pikir bubble sort berkinerja sangat baik - saya pikir jumlah lintasan akan sebanding dengan yang terjauh dari tempat item adalah. Jenis penyisipan akan bekerja dengan buruk, karena setiap item yang tidak dipesan akan memicu penyisipan. Saya menduga jenis introspektif atau sesuatu seperti itu akan bekerja dengan baik juga.
sumber
Jika Anda membutuhkan implementasi spesifik untuk menyortir algoritma, struktur data atau apa pun yang memiliki tautan ke di atas, dapatkah saya merekomendasikan Anda proyek "Struktur Data dan Algoritma" yang luar biasa pada CodePlex?
Ini akan memiliki semua yang Anda butuhkan tanpa menciptakan kembali roda.
Hanya sebutir garam.
sumber
Kumpulan algoritma penyortiran yang bagus untuk tujuan ini dalam jawaban, tampaknya tidak memiliki Gnome Sort , yang juga cocok, dan mungkin membutuhkan upaya implementasi yang paling sedikit.
sumber
Jenis penyisipan adalah kasus O (n) terbaik pada input yang diurutkan. Dan sangat dekat pada sebagian besar input yang diurutkan (lebih baik daripada quick sort).
sumber
renungkan Coba Tumpukan. Saya percaya itu yang paling konsisten dari jenis O (n lg n).
sumber
Bubble-sort (atau, lebih aman lagi, semacam bubble bi-directional) kemungkinan ideal untuk sebagian besar daftar yang diurutkan, meskipun saya bertaruh semacam comb-tweak (dengan ukuran celah awal yang jauh lebih rendah) akan menjadi sedikit lebih cepat ketika daftar tidak t cukup sempurna diurutkan. Sisir mengurutkan degradasi ke bubble-sort.
sumber
baik itu tergantung pada use case. Jika Anda tahu elemen mana yang diubah, hapus dan masukkan akan menjadi kasus terbaik sejauh yang saya ketahui.
sumber
Bubble sort pasti adalah pemenang. Yang berikutnya pada radar adalah sorting sort.
sumber
Jauhkan dari QuickSort - sangat tidak efisien untuk data yang diurutkan sebelumnya. Jenis penyisipan menangani data yang hampir diurutkan dengan baik dengan memindahkan nilai sesedikit mungkin.
sumber