Apa stabilitas dalam menyortir algoritma dan mengapa itu penting?

Saya sangat ingin tahu, mengapa stabilitas penting atau tidak penting dalam menyortir algoritma?

Algoritma pengurutan dikatakan stabil jika dua objek dengan kunci yang sama muncul dalam urutan yang sama dalam output yang diurutkan seperti yang muncul dalam array input yang akan diurutkan. Beberapa algoritma penyortiran stabil secara alami seperti Penyisipan, Penggabungan, Penyortiran, dll. Dan beberapa algoritma penyortiran tidak, seperti Heap Sort, Quick Sort, dll.

Latar belakang : algoritma penyortiran "stabil" menjaga item dengan kunci penyortiran yang sama secara berurutan. Misalkan kita memiliki daftar kata 5 huruf:

peach
straw
apple
spork

Jika kita mengurutkan daftar hanya dengan huruf pertama dari setiap kata maka jenis stabil akan menghasilkan:

apple
peach
straw
spork

Dalam algoritma pengurutan yang tidak stabil , strawatau sporkdapat dipertukarkan, tetapi dalam yang stabil, mereka tetap pada posisi relatif yang sama (yaitu, karena strawmuncul sebelumnya sporkdi input, juga muncul sebelum sporkdi output).

Kita bisa mengurutkan daftar kata menggunakan algoritma ini: pengurutan stabil dengan kolom 5, lalu 4, lalu 3, lalu 2, lalu 1. Pada akhirnya, kata itu akan diurutkan dengan benar. Yakinkan diri Anda akan hal itu. (Omong-omong, algoritma itu disebut radix sort)

Sekarang untuk menjawab pertanyaan Anda, misalkan kita memiliki daftar nama depan dan belakang. Kami diminta untuk mengurutkan "dengan nama belakang, lalu dengan yang pertama". Pertama-tama kita dapat mengurutkan (stabil atau tidak stabil) dengan nama depan, kemudian mengurutkan stabil dengan nama belakang. Setelah ini, daftar diurutkan berdasarkan nama belakang. Namun, di mana nama belakang sama, nama depan diurutkan.

Anda tidak dapat menumpuk jenis yang tidak stabil dengan cara yang sama.

Algoritma penyortiran yang stabil adalah yang menyortir elemen identik dalam urutan yang sama dengan yang muncul pada input, sementara penyortiran yang tidak stabil mungkin tidak memuaskan kasus ini. - _{^{Saya berterima kasih kepada dosen algoritme saya, Didem Gozupek karena telah memberikan wawasan tentang algoritma}} .

Algoritma Penyortiran Stabil:

• Penyisipan Sortir
• Gabungkan Sortir
• Sortir Bubble
• Sortir Tim
• Sortir Penghitungan
• Sortir Blok
• Quadsort
• Sortir Perpustakaan
• Cocktail shaker Sort
• Gnome Sort
• Sortir Ganjil-Genap

Algoritma Penyortiran Tidak Stabil:

• Heap sort
• Sortir seleksi
• Semacam shell
• Sortir cepat
• Introsort (tunduk pada Quicksort)
• Jenis pohon
• Urutkan siklus
• Smoothsort
• Urutan turnamen (tergantung Hesapsort)

Stabilitas pengurutan berarti bahwa catatan dengan kunci yang sama mempertahankan urutan relatifnya sebelum dan sesudah pengurutan.

Jadi stabilitas penting jika, dan hanya jika, masalah yang Anda selesaikan memerlukan retensi urutan relatif itu.

Jika Anda tidak membutuhkan stabilitas, Anda dapat menggunakan algoritma penghirup memori yang cepat dari perpustakaan, seperti heapsort atau quicksort, dan lupakan.

Jika Anda membutuhkan stabilitas, itu lebih rumit. Algoritme yang stabil memiliki CPU big-O dan / atau penggunaan memori yang lebih tinggi daripada algoritma yang tidak stabil. Jadi, ketika Anda memiliki kumpulan data besar, Anda harus memilih antara mengalahkan CPU atau memori. Jika Anda dibatasi pada CPU dan memori, Anda punya masalah. Algoritma stabil kompromi yang baik adalah jenis pohon biner; yang artikel Wikipedia memiliki C menyedihkan mudah ++ pelaksanaan berdasarkan STL.

Anda dapat membuat algoritma yang tidak stabil menjadi yang stabil dengan menambahkan nomor rekaman asli sebagai kunci tempat terakhir untuk setiap catatan.

Itu tergantung pada apa yang Anda lakukan.

Bayangkan Anda memiliki beberapa catatan orang dengan bidang nama depan dan belakang. Pertama, Anda mengurutkan daftar berdasarkan nama depan. Jika kemudian Anda mengurutkan daftar dengan algoritma stabil berdasarkan nama belakang, Anda akan memiliki daftar yang diurutkan berdasarkan nama depan dan nama belakang.

Ada beberapa alasan mengapa stabilitas bisa menjadi penting. Salah satunya adalah, jika dua catatan tidak perlu ditukar dengan menukar mereka, Anda dapat menyebabkan pembaruan memori, halaman ditandai kotor, dan perlu ditulis ulang ke disk (atau media lambat lainnya).

Algoritma pengurutan dikatakan stabil jika dua objek dengan kunci yang sama muncul dalam urutan yang sama dalam output yang diurutkan seperti yang muncul dalam input array yang tidak disortir. Beberapa algoritma penyortiran stabil secara alami seperti Penyisipan, Penggabungan, Penyortiran, dll. Dan beberapa algoritma penyortiran tidak, seperti Heap Sort, Quick Sort, dll.

Namun, setiap penyortiran algo yang tidak stabil dapat dimodifikasi menjadi stabil. Mungkin ada penyortiran algo cara khusus untuk membuatnya stabil, tetapi secara umum, setiap algoritma penyortiran berbasis perbandingan yang tidak stabil secara alami dapat dimodifikasi menjadi stabil dengan mengubah operasi perbandingan kunci sehingga perbandingan dua kunci menganggap posisi sebagai faktor untuk objek dengan kunci yang sama.

Referensi: http://www.math.uic.edu/~leon/cs-mcs401-s08/handouts/stability.pdf http://en.wikipedia.org/wiki/Sorting_algorithm#Stability

Saya tahu ada banyak jawaban untuk ini, tetapi bagi saya, jawaban ini , oleh Robert Harvey , merangkumnya dengan lebih jelas:

Sortir stabil adalah yang mempertahankan urutan asli set input, di mana algoritma [tidak stabil] tidak membedakan antara dua item atau lebih.

Sumber

Jika Anda menganggap apa yang Anda sortir hanyalah angka dan hanya nilainya yang mengidentifikasi / membedakannya (mis. Elemen dengan nilai yang sama adalah identicle), maka masalah stabilitas penyortiran tidak ada artinya.

Namun, objek dengan prioritas yang sama dalam penyortiran mungkin berbeda, dan terkadang urutan relatifnya adalah informasi yang bermakna. Dalam hal ini, pengurutan yang tidak stabil menghasilkan masalah.

Misalnya, Anda memiliki daftar data yang berisi biaya waktu [T] dari semua pemain untuk membersihkan labirin dengan Level [L] dalam game. Misalkan kita perlu memberi peringkat pemain dengan seberapa cepat mereka membersihkan labirin. Namun, aturan tambahan berlaku: pemain yang membersihkan labirin dengan tingkat yang lebih tinggi selalu memiliki peringkat yang lebih tinggi, tidak peduli berapa lama waktu yang dibutuhkan.

Tentu saja Anda dapat mencoba memetakan nilai berpasangan [T, L] ke bilangan real [R] dengan beberapa algoritma yang mengikuti aturan dan kemudian memberi peringkat semua pemain dengan nilai [R].

Namun, jika penyortiran stabil dapat dilakukan, maka Anda cukup mengurutkan seluruh daftar dengan [T] (pemain yang lebih cepat terlebih dahulu) dan kemudian dengan [L]. Dalam hal ini, urutan relatif pemain (berdasarkan biaya waktu) tidak akan berubah setelah Anda mengelompokkan mereka berdasarkan tingkat labirin yang mereka bersihkan.

PS: tentu saja pendekatan penyortiran dua kali bukan solusi terbaik untuk masalah khusus tetapi untuk menjelaskan pertanyaan poster itu sudah cukup.

Sortir yang stabil akan selalu mengembalikan solusi yang sama (permutasi) pada input yang sama.

Misalnya [2,1,2] akan diurutkan menggunakan sortasi stabil sebagai permutasi [2,1,3] (pertama adalah indeks 2, lalu indeks 1 kemudian indeks 3 dalam output yang diurutkan) Itu berarti bahwa output selalu dikocok dengan cara yang sama. Permutasi lain yang tidak stabil, tetapi masih benar adalah [2,3,1].

Penyortiran cepat bukanlah penyortiran yang stabil dan perbedaan permutasi di antara elemen yang sama tergantung pada algoritma untuk memilih pivot. Beberapa implementasi mengambil secara acak dan yang dapat membuat pengurutan cepat menghasilkan permutasi yang berbeda pada input yang sama menggunakan algoritma yang sama.

Algoritma sortir yang stabil diperlukan deterministik.

Beberapa contoh lagi alasan menginginkan jenis stabil. Database adalah contoh umum. Ambil contoh basis data transaksi dari pada menyertakan nama belakang, nama depan, tanggal pembelian, nomor barang, harga. Katakanlah basis data biasanya disortir berdasarkan tanggal | waktu. Kemudian dibuat kueri untuk membuat salinan data base yang diurutkan berdasarkan nama belakang | nama depan, karena pengurutan yang stabil mempertahankan pesanan asli, meskipun perbandingan penyelidikan hanya melibatkan nama belakang | nama depan, transaksi untuk setiap nama belakang | nama depan akan dalam data | urutan waktu.

Contoh serupa adalah Excel klasik, yang jenisnya dibatasi hingga 3 kolom sekaligus. Untuk mengurutkan 6 kolom, pengurutan dilakukan dengan 3 kolom paling signifikan, diikuti oleh pengurutan dengan 3 kolom paling signifikan.

Contoh klasik dari jenis radix stabil adalah penyortir kartu, yang digunakan untuk mengurutkan berdasarkan bidang basis 10 kolom numerik. Kartu diurutkan dari digit paling signifikan ke paling signifikan. Pada setiap kartu, setumpuk kartu dibaca dan dipisahkan menjadi 10 nampan berbeda sesuai dengan angka di kolom itu. Kemudian 10 nampan kartu dimasukkan kembali ke dalam hopper input secara berurutan ("0" kartu pertama, "9" kartu terakhir). Kemudian lulus lain dilakukan oleh kolom berikutnya, sampai semua kolom diurutkan. Penyortir kartu yang sebenarnya memiliki lebih dari 10 nampan karena ada 12 zona pada kartu, kolom bisa kosong, dan ada nampan yang salah baca. Untuk mengurutkan huruf, diperlukan 2 pass per kolom, pass pertama untuk digit, pass kedua untuk zona 12 11.

Kemudian (1937) ada mesin collating card (penggabungan) yang dapat menggabungkan dua deck kartu dengan membandingkan bidang. Inputnya adalah dua tumpukan kartu yang sudah disortir, satu dek utama dan satu tumpukan pembaruan. Kolektor menggabungkan dua deck ke dalam sebuah bin materi baru dan sebuah arsip bin, yang secara opsional digunakan untuk duplikat master sehingga master bin baru hanya akan memiliki kartu pembaruan jika ada duplikat. Ini mungkin merupakan dasar untuk ide di balik jenis gabungan asli (bawah ke atas).