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
źródło
Odpowiedzi:
Łatwo jest udowodnić dolną granicę Ω (n 2 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 2 log n.
To znaczy, że standardowe algorytmy sortowania porównań są asymptotycznie optymalne dla siatek uporządkowanych podczas opisu.
źródło
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.
źródło