Czy wymagana jest przechodnie algorytm sortowania

14

Czy można zastosować algorytm sortowania z nieprzechodnim porównaniem, a jeśli tak, dlaczego wymienność przechodni jest wymieniona jako wymóg dla sortujących komparatorów?

Tło:

Algorytm sortowania ogólnie sortuje elementy listy według funkcji komparatora C (x, y), przy pomocy

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

Wymagania dla tego komparatora są, o ile je rozumiem:
- zwrotny: $\forall x: C(x,x)=0$
- antysymetryczny: $\forall x,y: C(x,y) = - C(y,x)$
- przechodnie: $\forall x,y,z, a: C(x,y)=a \land C(y,z)=a \Rightarrow C(x,z)=a$
- C (x, y) jest zdefiniowane dla wszystkich x i y, a wyniki zależą tylko od x i y
(Te wymagania są zawsze wymienione inaczej w różnych implementacjach, więc nie jestem pewien, czy dobrze je zrozumiałem)

Teraz zastanawiam się nad „tolerancyjną” funkcją komparatora, która przyjmuje liczby x, y jako podobne, jeśli : $|x - y| \le 1$

\begin{array}{ll} do (x, y) = {\begin{cases} - 1 & gdyby x < y - 1 \\ 0 & gdyby | x - y | \leq 1 \\ + 1 & gdyby x > y + 1 \end{cases} \end{array}

$\begin{array}{ll} C(x,y) = \begin{cases} -1 & {\text{if}}\ x\lt y-1 \\ 0 & {\text{if}}\ |x - y| \le 1 \\ +1 & {\text{if}}\ x\gt y+1 \\ \end{cases} \end{array}$

Przykłady: obydwa [ 1, 2, 3, 4, 5]i [1, 4, 3, 2, 5]prawidłowo sortowane w kolejności rosnącej zgodnie z porównawczy tolerancyjnej ( gdy X jest przed Y na liście) , ale nie jest, ponieważ C (4,2) = 1 $C(x,y) \le 0$
[1, 4, 2, 3, 5]

Ten tolerancyjny komparator jest refleksyjny i antysymetryczny, ale nie przechodni.

tj. C (1,2) = 0, c (2,3) = 0, ale C (1,3) = -1, naruszając przechodniość

Jednak nie mogę wymyślić żadnego algorytmu sortowania, który nie dałby „poprawnie posortowanego” wyjścia, gdy otrzyma ten komparator i losową listę.

Czy zatem w tym przypadku przechodnie nie jest wymagane? Czy istnieje mniej ścisła wersja przechodniości, która jest wymagana, aby sortowanie działało?

Powiązane pytania:

Dlaczego do sortowania porównawczego potrzebna jest antysymetria? (o antysymetrii)
Algorytmy sortowania, które akceptują losowy komparator (około losowego C (x, y))
OrderBy z nieprzechodnym IComparer (o moim algorytmie sortowania c #)

— HugoRune
źródło

Myślę, że quicksort z „zawsze wybieraj środek” dla osi przestawnej nie powiódłby się przy użyciu tego komparatora na [3, 2, 1].

— G. Bach,

2

Podejrzewam, że jakiś nieprzechodni komparator użyty w pewnym algorytmie sortowania może spowodować nieskończoną pętlę.

— Karolis Juodelė

1

a_{i} \leq a_{i + 1}

$a_i \leq a_{i+1}$

a_{i} \leq a_{j}

$a_i \leq a_j$

i \leq j

$i \leq j$

@ G.Bach Myślę, że quicksort faktycznie się całkowicie nie powiedzie, jeśli twoja tablica ma n razy 3, raz 2, n razy 1, a środkowa 2 jest używana jako pierwsza oś, bez względu na to, co stanie się później.

— gnasher729,

12

Zapytałeś: Czy możemy uruchomić algorytm sortowania, który zapewni mu nieprzechodni komparator?

Odpowiedź: oczywiście. Możesz uruchomić dowolny algorytm z dowolnym wejściem.

Znasz jednak zasadę: Garbage In, Garbage Out. Jeśli uruchomisz algorytm sortowania z nieprzechodowym komparatorem, możesz otrzymać nonsensowne dane wyjściowe. W szczególności nie ma gwarancji, że dane wyjściowe zostaną „posortowane” według komparatora. Tak więc uruchomienie algorytmu sortowania z nieprzechodnim komparatorem prawdopodobnie nie będzie przydatne w sposób, w jaki prawdopodobnie oczekiwałeś.

$[3, 2, 1]$

— DW
źródło

1

moją pierwszą myślą było to, że lista [3,2,1] jest posortowana według mojego komparatora, więc oczywiście sortowanie powinno pozostawić ją bez zmian; ale mogłem użyć niewłaściwej definicji sortowania. Po prostu porównuję każdy element z jego bezpośrednimi sąsiadami, ale może to być zbyt słabe ograniczenie do rozważenia posortowania listy

— HugoRune

4

@ HugoRune Cóż, to interesujący punkt. Co pan myśli o sortowane ? Jeśli potrafisz pokazać, że algorytm sortowania zakończy się, biorąc pod uwagę nieprzechodni komparator, i że za każdym razem, gdy algorytm się kończy, jakiś warunek jest spełniony, a tym warunkiem jest sortowanie ... wtedy oczywiście ten algorytm posortuje twoją listę za każdym razem dla tej definicji sortowania . Jeśli komparator nie jest przechodni, może nie mieć sensu przyjmowanie definicji sortowania, która wymaga porównania parami wszystkich elementów na posortowanej liście.

— Patrick87

3

@ HugoRune, z „porównywane są tylko sąsiedzi” prawdopodobnie będziesz potrzebować niestandardowego sortowania. Standardowe algorytmy zakładają przechodniość, aby uniknąć zbędnych porównań. Lub możesz osadzić nieprzechodnie zamówienie w przechodnie. A może szukasz czegoś w rodzaju sortowania topologicznego ?

— vonbrand

Natknąłem się na to jakiś czas temu i stwierdziłem, że sortowanie bąbelkowe faktycznie działa dobrze, ponieważ zawsze porównuje tylko sąsiednie elementy.

— Mooing Duck

4

Biorąc pod uwagę zestaw elementów i binarną relację porządkującą, przechodnie jest wymagane do całkowitego uporządkowania elementów. W rzeczywistości przejściowość jest nawet wymagana do zdefiniowania częściowego porządku na elementach. http://en.m.wikipedia.org/wiki/Total_order

Potrzebowałbyś znacznie szerszej definicji tego, co oznacza „posortowane”, aby posortować elementy bez przechodniości. Trudno być samowystarczalnym. Inna odpowiedź brzmi: „W szczególności nie ma gwarancji, że dane wyjściowe zostaną„ posortowane ”według komparatora.” Ale możemy powiedzieć coś znacznie silniejszego. Masz gwarancję, że dane wyjściowe nie zostaną posortowane według twojego komparatora.

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

— Joe
źródło

1

Zinterpretowałem pytanie, aby zadać pytanie o sortowanie przy użyciu częściowego uporządkowania (takie, że porównania, które mówią, że rzeczy są nierówne, są przechodnie, ale te, które dotyczą elementów, których nie można odróżnić, nie są). Sortowanie na podstawie częściowego uporządkowania jest czasem przydatne, ale w najgorszym przypadku wymaga porównania N (N-1) / 2. Każdy algorytm sortujący, który w najgorszym przypadku wykonuje mniej niż N (N-1) / 2 porównań, nie będzie w stanie poprawnie uszeregować częściowo zamówionych przedmiotów z powodów opisanych w mojej odpowiedzi.

— supercat

2

Brzmi tak, jakbyś chciał ułożyć przedmioty w taki sposób, aby wszystkie dostrzegalne pozycje w rankingu były poprawne, ale przedmioty, które są blisko, można uznać za „nierozróżnialne”. Możliwe jest zaprojektowanie algorytmów sortowania, które będą działać z takimi porównaniami, ale jeśli nie ma ograniczeń co do liczby porównań, które mogą wskazywać, że rzeczy są nierozróżnialne, nie ma sposobu, aby uniknąć konieczności ich porównywania N (N-1) / 2. Aby zrozumieć dlaczego, wybierz pewną liczbę N i dowolny algorytm sortujący, który wykonuje mniej niż N (N-1) / 2 porównań. Następnie wypełnij listę L [0..N-1], ustawiając każdy element L [I] na I / N i „sortuj” go za pomocą komparatora (minimalna wartość to 0, a maksymalna (N-1) / N , więc różnica będzie wynosić (N-1) / N, czyli mniej niż 1).

Ponieważ istnieje N (N-1) / 2 pary elementów, które można porównać, a sortowanie nie wykonało tak wielu porównań, musi istnieć pewna para elementów, które nie zostały bezpośrednio porównane ze sobą. Zastąp, którykolwiek z nich zostanie posortowany najpierw przez 1, a drugi przez -1 / N, przywróć wszystkie pozycje do ich początkowej pozycji i powtórz operację sortowania. Każda pojedyncza operacja porównania da zero, tak samo jak za pierwszym razem, więc zostaną wykonane te same porównania, a elementy skończą w tej samej kolejności. Aby lista była poprawnie posortowana, „1” musiałoby sortować po „-1 / N” (ponieważ różnią się o więcej niż jeden), ale ponieważ algorytm sortowania nigdy nie porównałby tych dwóch elementów bezpośrednio względem siebie, to nie byłby w stanie tego wiedzieć.

— supercat
źródło

0

Wypełnij tablicę n elementów wartościami n, n-1, n-2, ..., 2, 1. Następnie spróbuj posortować przy użyciu algorytmu „prostego wstawiania”. Przekonasz się, że każdy element jest uważany za równy pierwiastkowi tuż przed nim i dlatego nie jest przenoszony. Wynikiem „sortowania” jest ta sama tablica.

— gnasher729
źródło