Co to jest dobry algorytm sortowania specjalnych przypadków?

13

Mam zestaw danych, który jest liczbą obiektów ułożonych w siatkę 2D. Wiem, że mam ścisłą kolejność, rosnącą wraz z ruchem od lewej do prawej w każdym rzędzie i rosnącą od góry do dołu w każdej kolumnie. Na przykład,

1 2 3
4 6 7
5 8 9

Czy mogę ulepszyć naiwne sortowanie, aby posortować cały zestaw danych liniowo (mierzony w porównaniach)?

Co z zestawami danych? Arbitralne skończone zestawy danych ze znanym podzbiorem porównań?

ds.algorithms total-ordering sorting

— Zachary Vance
źródło

1

Czy możesz zadać bardziej precyzyjne pytanie? Twój pierwszy akapit można odczytać, aby sugerować, że Twoje dane są już posortowane! Jaki dokładnie jest twój wkład i jaki wynik chcesz?

— Jacques Carette

1

Tak, język jest trochę mylący. Zajęło mi trochę czasu uświadomienie sobie, że zestaw danych składa się z n liczb do posortowania, ale te liczby są ułożone w siatkę sqrt (n) x sqrt (n), tak że każdy wiersz i każda kolumna są już posortowane. Czy o to ci chodziło?

Tak właśnie miałem na myśli. Zredaguję dla jasności.

— Zachary Vance

19

Łatwo jest udowodnić dolną granicę Ω (n ² log n) tego problemu (w porównawczym modelu sortowania): jeśli element w pozycji (i, j) zawsze znajduje się w odległości 1/2 od i + j, to siatka przekątne są od siebie niezależne, a porządek sortowania w przekątnej każdej siatki jest dowolny. Zatem pod tym ograniczeniem całkowita możliwa liczba uporządkowań jest iloczynem (we wszystkich przekątnych siatki) silni długości przekątnych, która jest wykładnicza w n ² log n.

To znaczy, że standardowe algorytmy sortowania porównań są asymptotycznie optymalne dla siatek uporządkowanych podczas opisu.

— David Eppstein
źródło

Druga odpowiedź daje wyraźny algorytm o tej złożoności, więc rozważę ten problem rozwiązany dla siatek 2-D i, bez faktycznego sprawdzania, prawdopodobnie dla siatek o dowolnych wymiarach.

— Zachary Vance

4

Jeśli dobrze rozumiem problem (a mogę nie, nie krępuj się i powiedz mi, jeśli nie), czy chcesz przekształcić siatkę 2D w posortowaną tablicę 1D, podczas gdy każdy wiersz i kolumna jest już posortowana w siatce 2D?

Pierwszym elementem na liście w tym przypadku musi być lewy górny róg ((0,0), z definicji problemu). Następnie musi to być element (1,0) lub (0,1), ponieważ wszystkie inne będą z definicji większe niż te.

Możesz uogólnić, mówiąc, że następny najmniejszy element na siatce zawsze znajduje się bezpośrednio pod elementem już używanym (lub krawędzią siatki), a także na prawo od elementu już używanego (lub krawędzi siatki), ponieważ oba są zdefiniowane jako mniejsze od niego. Dlatego przy każdej iteracji należy brać pod uwagę tylko najmniejszą wartość, która spełnia to wymaganie.

Możesz zachować potencjalnych kandydatów w uporządkowanej kolejności, w miarę ich znajdowania (nie więcej niż dwóch będzie dostępnych w jednej iteracji), a przy każdej iteracji sprawdź nowe wartości (jeśli istnieją). Jeśli są niższe niż najniższy z poprzednich kandydatów, od razu dodaj ich do listy i powtórz, w przeciwnym razie dodaj najniższego poprzedniego kandydata i porównaj z następnym najniższym itp.

Niestety, nie twierdzę, że jestem w stanie zapewnić dokładną złożoność tego, ani nie twierdzę, że jest to najbardziej skuteczny możliwy, z pewnością wydaje się lepszy niż naiwne podejście i mam nadzieję, że wyjaśniłem to wystarczająco dobrze, abyś mógł to zrozumieć.

EDYCJA: W przypadku takich siatek jak ta, uważam, że obowiązuje ta sama podstawowa zasada, ale każda iteracja powoduje, że dostępnych jest n nowych kandydatów, a kandydaci ci muszą być w tym momencie najmniejszymi nieużywanymi elementami w każdym z n wymiarów.

— Paweł
źródło

Krótko mówiąc, możesz wykonać łączenie w sqrt (N), na przykład w scalesort? To była moja najlepsza metoda, ale okazuje się, że to O (N log N) - nie mam tam dokładnej stałej, ale jest co najmniej 0,5 dla log (sqrt (N)).

— Zachary Vance