Bisakah penyortiran daftar diverifikasi tanpa membandingkan tetangga?

14

Daftar n item dapat diverifikasi sebagai diurutkan dengan membandingkan setiap item dengan tetangganya. Dalam aplikasi saya, saya tidak akan dapat membandingkan setiap item dengan tetangganya: sebagai gantinya, perbandingan terkadang akan berada di antara elemen yang jauh. Mengingat bahwa daftar berisi lebih dari tiga item dan juga perbandingan itu adalah satu-satunya operasi yang didukung, apakah pernah ada "jaringan" perbandingan yang akan membuktikan bahwa daftar diurutkan, tetapi hilang setidaknya satu tetangga-ke-tetangga langsung perbandingan?

Secara formal, untuk urutan elemen ei , saya memiliki satu set pasangan indeks (j,k) yang saya tahu apakah ej>ek , ej=ek , atau ej<ek . Ada pasangan (l,l+1) yang hilang dari rangkaian perbandingan. Jadi, apakah mungkin untuk membuktikan bahwa urutannya diurutkan?

sorting Nama tampilan
sumber
1
Catatan kalau-kalau ada yang menemukan halaman ini nanti dengan pertanyaan apakah Anda dapat memverifikasi daftar diurutkan tanpa membandingkan apa pun; Hanya jika Anda dapat membatasi input, dan / atau mengetahui sesuatu tentang bentuk input; (mis., jenis radix).
HammerN'Songs
Namun, ada kemungkinan mengoptimalkan jumlah perbandingan yang digunakan dalam kasus-kasus di mana itu tidak diurutkan.
Akumulasi
1
@Akumulasi Apakah sebenarnya ada kemungkinan seperti itu? Seharusnya sepele untuk mengambil program semacam itu dan memasak daftar panjang yang berlawanan n yang memaksa program untuk melakukan perbandingan n-1. Lihat juga A Killer Musuh untuk QuickSort , yang membawa ide ini lebih jauh untuk memaksa quicksort ke bagian buruk dari analisis asimptotiknya.
Daniel Wagner
@DanielWagner Ya, optimasi seperti itu harus dilakukan sehubungan dengan input yang diharapkan dari aplikasi tertentu.
Akumulasi
Mungkin tidak mungkin. Namun tolong jelaskan: apakah maksud Anda bahwa Anda hanya mengetahui perbandingan bentuk (j, j + 1), bukan umum (j, k)? Misalnya, apakah Anda pernah tahu perbandingan dua item indeks (j, j + 3)?
Ron

Jawaban:

34

Itu tidak mungkin. Misalkan Anda memiliki hasil semua perbandingan kecuali untuk pasangan (i,i+1) . Maka Anda tidak akan dapat membedakan antara dua kasus berikut:

1,2,…,i−1,i,i+1,i+2,…,n1,2,…,i−1,i+1,i,i+2,…,n

Yuval Filmus
sumber