Apakah fungsi sort () python dijamin stabil?

96

The dokumentasi tidak menjamin bahwa. Apakah ada tempat lain yang didokumentasikan?

Saya menduga ini mungkin stabil karena metode sortir pada daftar dijamin stabil (Catatan poin ke-9: "Dimulai dengan Python 2.3, metode sort () dijamin stabil"), dan sortir secara fungsional serupa. Namun, saya tidak dapat menemukan sumber pasti yang menyatakan demikian.

Tujuan: Saya perlu mengurutkan berdasarkan kunci utama dan juga kunci sekunder dalam kasus di mana kunci utama sama di kedua catatan. Jika sort () dijamin stabil, saya dapat mengurutkan pada kunci sekunder, kemudian mengurutkan pada kunci primer dan mendapatkan hasil yang saya butuhkan.

PS: Untuk menghindari kebingungan, saya menggunakan stable dalam arti "sejenis stabil jika menjamin tidak mengubah urutan relatif elemen yang membandingkan sama".

python sorted stable-sort sundar - Kembalikan Monica
sumber

Jawaban:

127

Ya, maksud dari manual ini memang untuk menjamin bahwa sorteditu stabil dan memang menggunakan algoritma yang sama persis dengan sortmetodenya. Saya menyadari bahwa dokumen tidak 100% jelas tentang identitas ini; tambalan dokumen selalu diterima dengan senang hati!

Alex Martelli
sumber
2
Saya telah menemukan bahwa jika saya menyortir tupel atau daftar, setiap kali kunci pengurutan "primer" sama, itu berakhir dengan pengurutan berdasarkan kunci "sekunder". Misalnya, sorted([(1, 2), (1, 1)])mengembalikan [(1, 1), (1, 2)]alih-alih mengembalikan masukan asli dalam urutan / urutan yang sama. Bukankah jaminan stabilitas berarti harus mengembalikan [(1, 2), (1, 1)]input asli ? Dalam hal ini, Anda harus eksplisit dan mengatakansorted([(1, 2), (1, 1)], key=lambda t: t[0])
code_dredd
10
Bukankah ini yang diharapkan dalam kasus ini? Python akan membandingkan tupel melalui semua elemen secara default, bukan hanya yang "utama" yang pertama. Jika Anda hanya ingin mengurutkan elemen pertama, Anda dapat meneruskan keyparameter secara eksplisit.
Matias Grioni
2
@code_dredd ini adalah perilaku yang diharapkan. Inti dari stable-sort adalah mengurutkan menggunakan "kunci pengurutan" tetapi dua elemen berbeda yang memiliki kunci pengurutan yang sama akan berada dalam urutan yang sama. Kunci pengurutan default untuk tupel adalah semua elemen tupel.
guyarad
27

Mereka stabil .

Ngomong-ngomong: Anda terkadang bisa mengabaikan mengetahui apakah sortir dan sortir stabil, dengan menggabungkan pengurutan multi-pass dalam satu pass tunggal.

Misalnya, jika Anda ingin semacam benda berdasarkan mereka last_name, first_nameatribut, Anda dapat melakukannya dalam satu lulus:

sorted_list= sorted(
    your_sequence_of_items,
    key= lambda item: (item.last_name, item.first_name))

memanfaatkan perbandingan tupel.

Jawaban ini, sebagaimana adanya, mencakup pertanyaan awal. Untuk pertanyaan terkait penyortiran lebih lanjut, ada Python Sorting How-To .

tzot.dll
sumber
4
Ini dapat memiliki efek yang tidak diinginkan jika Anda ingin membalik urutan. Misalnya saat menyortir produk, Anda mungkin ingin mengurutkan berdasarkan peringkat (urutan naik) dan harga (juga naik). Jika Anda membalikkan ini, Anda ingin mengurutkan peringkat dalam urutan menurun tetapi harga dalam urutan naik. Ini tidak berfungsi dengan solusi ini.
Remco Wendt
2
@RemcoWendt: tidak ada persyaratan untuk apa yang Anda gambarkan. Dalam kasus apapun, pertimbangkan key= lambda item: (-item.rating, item.price)atau berikan a, cmpbukan keyargumen. Saya masih tidak yakin tentang tujuan komentar Anda.
tzot
1
Memang itu bukan persyaratan, tetapi ingin menunjukkan perbedaan halus ini ketika orang lain membaca ini dan membuat pilihan antara solusi Anda atau menggunakan fitur sortir stabil Python.
Remco Wendt
Saya melihat. Dengan kata lain, mengurutkan berdasarkan pasangan lebih jelas dan karenanya lebih disukai, kecuali Anda peduli dengan performanya. Saya membayangkan bahwa dua jenis stabil agak lebih cepat daripada satu jenis berdasarkan pasangan, meskipun perbedaannya dapat diabaikan -?
Sergey Orshanskiy
8
@ tzot Saya ingin menyebutkan, selalu ada persyaratan seperti itu untuk penyortiran yang stabil. Misalnya, saya memiliki daftar tuple (rate, comment), komentar disimpan dalam urutan kapan dibuat, dan saya ingin mengurutkan berdasarkan rate dan menjaga urutan waktu, namun, saya tidak menyimpan stempel waktu dalam daftar. Untuk mengatakannya secara singkat, saya hanya ingin mengurutkan daftar berdasarkan tarif, dan menjaga komentar dalam urutan yang sama.
wsysuper
3

Sementara itu, dokumentasi berubah ( komit relevan ) dan dokumentasi terkini sortedsecara eksplisit menjaminnya:

Fungsi built-in sorted()dijamin stabil. Pengurutan stabil jika menjamin untuk tidak mengubah urutan relatif elemen yang membandingkan sama - ini berguna untuk mengurutkan dalam beberapa langkah (misalnya, urutkan menurut departemen, lalu menurut nilai gaji).

Bagian dari dokumentasi ini telah ditambahkan ke Python 2.7 dan Python 3.4 (+) sehingga setiap implementasi yang sesuai dari versi bahasa tersebut harus memiliki stabil sorted.

Perhatikan bahwa untuk CPython list.sorttelah stabil sejak Python 2.3

  • Tim Peters menulis ulang list.sort()implementasinya - yang ini adalah "urutan stabil" (input yang sama muncul dalam urutan yang sama dalam output) dan lebih cepat dari sebelumnya.

Saya tidak 100% yakin sorted, saat ini penggunaannya sederhana list.sort, tetapi saya belum memeriksa riwayatnya. Tapi kemungkinan itu "selalu" digunakan list.sort.

MSeifert
sumber
0

Dokumen "What's New" untuk Python 2.4 secara efektif membuat titik yang diurutkan () pertama-tama membuat daftar, kemudian memanggil sort () di atasnya, memberi Anda jaminan yang Anda perlukan meskipun tidak dalam dokumen "resmi". Anda juga dapat memeriksa sumbernya, jika Anda benar-benar khawatir.

Peter Hansen
sumber
1
Bisakah Anda menunjukkan di mana dikatakan demikian? Ia mengatakan diurutkan () "berfungsi seperti list.sort () di tempat" dan "salinan yang baru dibentuk diurutkan", tetapi saya tidak melihatnya mengatakan bahwa ia secara internal menggunakan sort ().
sundar - Kembalikan Monica
"Salin" yang dibentuk adalah daftar (itulah yang Anda dapatkan sebagai nilai kembali), dan .sort () dipanggil di daftar itu sebelum kembali. QED. Tidak, ini bukan bukti yang tidak dapat disangkal, tetapi sampai Python memiliki standar resmi, Anda tidak akan mendapatkannya.
Peter Hansen
0

Dokumen Python 3.6 tentang pengurutan sekarang menyatakan bahwa

Macam dijamin stabil

Selanjutnya, di dalam dokumen tersebut, terdapat link ke Timsort stable , yang menyatakan bahwa

Timsort telah menjadi algoritme pengurutan standar Python sejak versi 2.3

Wolfgang Kuehn
sumber