Apakah diperlukan transitivitas untuk algoritme pengurutan

Apakah mungkin untuk menggunakan algoritma penyortiran dengan perbandingan non-transitif, dan jika ya, mengapa transitivitas terdaftar sebagai persyaratan untuk menyortir komparator?

Latar Belakang:

• Algoritma pengurutan umumnya mengurutkan elemen daftar sesuai dengan fungsi komparator C (x, y), dengan

  $$\begin{array}{ll} C(x,y) = \begin{cases} -1 & {\text{if}}\ x\prec y \\ 0 & {\text{if}}\ x\sim y \\ +1 & {\text{if}}\ x\succ y \\ \end{cases} \end{array}$$

  Persyaratan untuk pembanding ini adalah, sejauh yang saya mengerti:

  • refleksif: $\forall x: C(x,x)=0$
  • antisymmetric: $\forall x,y: C(x,y) = - C(y,x)$
  • transitif: $\forall x,y,z, a: C(x,y)=a \land C(y,z)=a \Rightarrow C(x,z)=a$
  • C (x, y) didefinisikan untuk semua x dan y, dan hasilnya hanya bergantung pada x dan y

  (Persyaratan ini selalu terdaftar secara berbeda di seluruh implementasi yang berbeda, jadi saya tidak yakin saya mendapatkannya dengan benar)

Sekarang saya bertanya-tanya tentang fungsi komparator "toleran", yang menerima angka x, y sama seperti jika : $|x - y| \le 1$

Contoh: keduanya [ 1, 2, 3, 4, 5]dan [1, 4, 3, 2, 5]secara benar diurutkan dalam urutan naik sesuai dengan pembanding yang toleran ( jika x datang sebelum y dalam daftar) tetapi tidak, karena C (4,2) = 1$C(x,y) \le 0$
[1, 4, 2, 3, 5]

Komparator toleran ini bersifat refleksif dan antisimetris, tetapi tidak transitif.

yaitu C (1,2) = 0, c (2,3) = 0, tetapi C (1,3) = -1, melanggar transitivitas

Namun saya tidak dapat memikirkan algoritma pengurutan apa pun yang akan gagal menghasilkan keluaran yang "diurutkan dengan benar" ketika diberi komparator ini dan daftar acak.

Apakah karena itu transitivitas tidak diperlukan dalam kasus ini? Dan apakah ada versi kurang ketat transitivitas yang adalah diperlukan untuk menyortir bekerja?

Pertanyaan-pertanyaan Terkait:

• Mengapa antisimetri diperlukan untuk jenis perbandingan? (tentang antisimetri)
• Algoritma pengurutan yang menerima pembanding acak (sekitar C acak (x, y))
• OrderBy dengan IComparer non-transitif (tentang algoritma c # sort, oleh saya)

Anda bertanya: Bisakah kita menjalankan algoritme pengurutan, memberinya perbandingan non-transitif?

Jawabannya: tentu saja. Anda dapat menjalankan algoritma apa pun dengan input apa pun.

Namun, Anda tahu aturannya: Sampah Masuk, Sampah Keluar. Jika Anda menjalankan algoritme pengurutan dengan pembanding non-transitif, Anda mungkin mendapatkan hasil yang tidak masuk akal. Secara khusus, tidak ada jaminan bahwa output akan "diurutkan" sesuai dengan pembanding Anda. Jadi, menjalankan algoritme pengurutan dengan komparator non-transitif kemungkinan tidak akan berguna seperti yang Anda harapkan.

Sebagai contoh tandingan, menjalankan penyisipan mengurutkan pada daftar input menggunakan komparator Anda akan membuat daftar tidak berubah - namun daftar output yang dihasilkan tidak dalam urutan diurutkan (sesuai dengan komparator Anda).$[3, 2, 1]$

Dengan serangkaian elemen dan hubungan pemesanan biner, transitivitas diperlukan untuk memesan elemen secara total. Bahkan, transitivitas bahkan diperlukan untuk menentukan urutan parsial pada elemen. http://en.m.wikipedia.org/wiki/Total_order

Anda akan memerlukan definisi yang lebih luas tentang arti "diurutkan" untuk mengurutkan elemen tanpa transitivitas. Sulit untuk konsisten dengan diri sendiri. Jawaban lain mengatakan, "Secara khusus, tidak ada jaminan bahwa output akan 'diurutkan' sesuai dengan pembanding Anda." Tapi kita sebenarnya bisa mengatakan sesuatu yang jauh lebih kuat. Anda dijamin bahwa output tidak diurutkan sesuai dengan pembanding Anda.

$a<b$$b<c$$c<a$

Kedengarannya seperti apa yang Anda inginkan adalah mengatur item sehingga semua peringkat yang terlihat benar, tetapi item yang dekat mungkin dianggap "tidak bisa dibedakan". Dimungkinkan untuk merancang algoritma pengurutan yang akan bekerja dengan perbandingan seperti itu, tetapi kecuali ada batasan berapa banyak perbandingan dapat melaporkan bahwa hal-hal tidak dapat dibedakan, tidak ada cara untuk menghindarinya karena mereka memerlukan perbandingan N (N-1) / 2. Untuk memahami alasannya, pilih beberapa angka N dan algoritma penyortiran apa pun yang melakukan perbandingan kurang dari N (N-1) / 2. Kemudian mengisi daftar L [0..N-1], mengatur setiap elemen L [I] ke I / N dan "mengurutkan" menggunakan komparator Anda (nilai minimum akan menjadi 0 dan maksimum (N-1) / N , jadi perbedaannya adalah (N-1) / N, yang kurang dari 1).

Karena ada N (N-1) / 2 pasang item yang dapat dibandingkan, dan jenisnya tidak melakukan banyak perbandingan, pasti ada beberapa item yang tidak secara langsung dibandingkan satu sama lain. Ganti yang mana saja yang akhirnya disortir terlebih dahulu dengan 1, dan yang lainnya dengan -1 / N, kembalikan semua item ke posisi awal, dan ulangi operasi penyortiran. Setiap operasi perbandingan tunggal akan menghasilkan nol, sama seperti yang dilakukan pertama kali, sehingga perbandingan yang sama akan dilakukan dan item akan berakhir dalam urutan yang sama. Agar daftar diurutkan dengan benar, "1" harus mengurutkan setelah "-1 / N" (karena mereka berbeda lebih dari satu) tetapi karena algoritma pengurutan tidak akan pernah membandingkan kedua item secara langsung terhadap satu sama lain, itu tidak akan memiliki cara untuk mengetahui hal itu.

Isi larik elemen n dengan nilai n, n-1, n-2, ..., 2, 1. Kemudian cobalah mengurutkan menggunakan algoritma "straight insertion". Anda akan menemukan bahwa setiap elemen dianggap sama dengan elemen sebelum itu, dan karenanya tidak dipindahkan. Hasil dari "sort" adalah array yang sama.