Czy można zweryfikować sortowanie listy bez porównywania sąsiadów?

punkt A lista może być zweryfikowany jako klasyfikowane porównując każdy element do swojego sąsiada. W mojej aplikacji nie będę w stanie porównać każdego elementu z jego sąsiadem: zamiast tego porównania będą czasami dokonywane między odległymi elementami. Biorąc pod uwagę, że lista zawiera więcej niż trzy elementy, a także porównanie jest jedyną obsługiwaną operacją, czy kiedykolwiek istnieje „sieć” porównań, która udowodni, że lista jest posortowana, ale brakuje jej co najmniej jednego bezpośredniego sąsiada do sąsiada porównanie? $n$

Formalnie dla sekwencji elementów mam zestaw par indeksów dla których wiem, czy , , czy . Istnieje para której brakuje w zestawie porównań. Czy jest zatem kiedykolwiek możliwe udowodnienie, że sekwencja jest posortowana? $e_i$ $(j,k)$ $e_j > e_k$ $e_j = e_k$ $e_j < e_k$ $(l,l+1)$

sorting

— Wyświetlana nazwa
źródło

Uwaga na wypadek, gdyby ktokolwiek znalazł tę stronę później, z pytaniem, czy można zweryfikować listę, jest sortowana bez porównywania; Tylko jeśli możesz nałożyć ograniczenia na dane wejściowe i / lub wiedzieć coś o kształcie danych wejściowych; (np. sortowanie radix).

— HammerN'Songs

Istnieje jednak możliwość optymalizacji liczby porównań stosowanych w przypadkach, w których to nie posortowanych.

— Kumulacja

@Acccumulation Czy rzeczywiście istnieje taka możliwość? Powinno być trywialne wziąć taki program i przygotować listę przeciwników o długości n, która zmusza program do wykonywania porównań n-1. Zobacz także Killer Adversary for QuickSort , który posuwa ten pomysł jeszcze dalej, zmuszając quicksort do złej części jego asymptotycznej analizy.

— Daniel Wagner,

@DanielWagner Tak, taka optymalizacja musi być wykonana w odniesieniu do oczekiwanego wkładu konkretnej aplikacji.

— Kumulacja

Prawdopodobnie niemożliwe. Ale proszę wyjaśnić: czy miałeś na myśli, że znasz tylko porównania formy (j, j + 1), a nie ogólne (j, k)? Na przykład, czy znasz porównanie dwóch pozycji indeksów (j, j + 3)?

— Ron

To jest niemożliwe. Załóżmy, że masz wynik wszystkich porównań oprócz pary $(i,i+1)$ . Wówczas nie byłbyś w stanie rozróżnić następujących dwóch przypadków:

1, 2), \dots, ja - 1, ja, ja + 1, ja + 2), \dots, n 1, 2), \dots, ja - 1, ja + 1, ja, ja + 2), \dots, n

$1,2,\ldots,i-1,i,i+1,i+2,\ldots,n \\ 1,2,\ldots,i-1,i+1,i,i+2,\ldots,n$

— Yuval Filmus
źródło