Dodawanie elementów do posortowanej tablicy

Jaki byłby najszybszy sposób na zrobienie tego (z punktu widzenia algorytmu, a także ze względów praktycznych)?

Myślałem o czymś następującym.

Mógłbym dodać na końcu tablicy, a następnie użyć bąbelkowego sortowania, ponieważ ma najlepszy przypadek (tablica całkowicie posortowana na początku), który jest zbliżony do tego i ma liniowy czas działania (w najlepszym przypadku).

Z drugiej strony, jeśli wiem, że zaczynam od posortowanej tablicy, mogę użyć wyszukiwania binarnego, aby znaleźć punkt wstawienia dla danego elementu.

Mam przeczucie, że drugi sposób jest prawie optymalny, ale ciekawy, co tam jest.

Jak można to najlepiej zrobić?

Bieżemy pod uwagę liczbę odczytów i zapisów elementu tablicy. Aby wykonać sortowanie bąbelkowe, potrzebujesz dostępu (początkowy zapis do końca, a następnie, w najgorszym przypadku, dwa odczyty i dwa zapisy do wykonania n zamiany). Aby przeprowadzić wyszukiwanie binarne, potrzebujemy 2 log n + 2 n + 1 ( 2 log n dla wyszukiwania binarnego, a następnie, w najgorszym przypadku, 2 n, aby przesunąć elementy tablicy w prawo, a następnie 1, aby zapisać element tablicy do jego właściwe położenie).$1 + 4n$$n$$2\log n + 2n + 1$$2\log n$$2n$

Tak więc obie metody mają tę samą złożoność dla implementacji tablic, ale metoda wyszukiwania binarnego wymaga na dłuższą metę mniejszego dostępu do tablicy ... asymptotycznie, o połowę mniej. W grę wchodzą oczywiście inne czynniki.

W rzeczywistości można użyć lepszych implementacji i liczyć tylko rzeczywiste dostępy do tablicy (nie dostęp do elementu, który ma zostać wstawiony). Możesz zrobić dla sortowania bąbelkowego i zalogować n + 2 n + 1 dla wyszukiwania binarnego ... więc jeśli dostęp do rejestru / pamięci podręcznej jest tani, a dostęp do tablicy jest drogi, wyszukiwanie od końca i przesuwanie się po drodze (mądrzejsze sortowanie bąbelkowe do wstawienia) mogłoby być lepsze, choć nie asymptotycznie.$2n + 1$$\log n + 2n + 1$

Lepsze rozwiązanie może wymagać użycia innej struktury danych. Tablice dają dostęp O (1) (dostęp losowy), ale wstawianie i usuwanie może kosztować. Tabela skrótów może zawierać wstawianie i usuwanie O (1), dostęp będzie kosztował. Inne opcje obejmują BST i sterty itp. Warto rozważyć potrzeby użycia aplikacji w zakresie wstawiania, usuwania i dostępu oraz wybierania bardziej specjalistycznej struktury.

Zauważ też, że jeśli chcesz dodać elementów do posortowanej tablicy n elementów, dobrym pomysłem może być wydajne sortowanie m elementów, a następnie scalenie dwóch tablic; sortowane tablice można również efektywnie budować przy użyciu np. hałd (sortowania stosów).$m$$n$$m$

Jeśli masz powód, aby nie używać sterty, rozważ użycie sortowania wstawianego zamiast sortowania bąbelkowego. Lepiej jest, gdy masz kilka nieposortowanych elementów.

Ponieważ używasz tablicy, wstawienie elementu kosztuje - na przykład, gdy dodajesz coś do środka tablicy, musisz przesunąć wszystkie elementy za sobą, aby tablica pozostała posortowana .$O(n)$

Najszybszym sposobem, aby dowiedzieć się, gdzie umieścić przedmiot, jest jak wspomniano, wyszukiwanie binarne, które jest , więc całkowita złożoność będzie wynosić O ( n + lg n ) , która jest rzędu O ( n ) .$O(\lg n)$$O(n + \lg n)$$O(n)$

Biorąc to pod uwagę, gdybym poczuł się wyjątkowo nieswojo, mógłbym argumentować, że można „dodać do posortowanej tablicy” w $O(1)$ , po prostu uderzając go na końcu tablicy, ponieważ opis nie wskazuje, że tablica musi pozostać posortowane po wstawieniu nowego elementu.

W każdym razie nie widzę powodu, by wyciągać bańki z tym problemem.

Patrick87 wszystko to wyjaśnił bardzo dobrze. Ale jedną dodatkową optymalizacją, którą możesz zrobić, byłoby użycie czegoś w rodzaju bufora kołowego: jak zwykle możesz przesuwać elementy na prawo od położenia wstawionego elementu w prawo. Ale możesz także przenosić przedmioty na lewo od właściwej pozycji na lewo. Aby to zrobić, musisz traktować tablicę jako okrągłą, tzn. Ostatni element jest tuż przed pierwszym, a także wymaga utrzymania indeksu w miejscu, w którym aktualnie zaczynają się elementy.

Jeśli to zrobisz, może to oznaczać, że uzyskasz około połowy dostępów do tablicy (zakładając równomierny rozkład indeksów, do których wstawisz). W przypadku wyszukiwania binarnego w celu znalezienia pozycji banalne jest wybranie, czy przesunąć w lewo, czy w prawo. W przypadku sortowania bąbelkowego musisz „odgadnąć” poprawnie przed rozpoczęciem. Ale robienie tego jest proste: wystarczy porównać wstawiony element z medianą tablicy, co można zrobić w trybie dostępu do jednej tablicy.

Dla tego problemu skutecznie wykorzystałem algorytm sortowania wstawiania . Kiedyś mieliśmy problem z wydajnością obiektu tablicy skrótów, napisałem nowy obiekt, który zamiast tego użył wyszukiwania binarnego, co znacznie zwiększyło wydajność. Aby utrzymać sortowanie listy, śledziłaby liczbę elementów dodanych od ostatniego sortowania (tj. Liczbę nieposortowanych elementów), gdy lista musiała zostać posortowana z powodu żądania wyszukiwania, przeprowadziła sortowanie z wstawianiem lub szybkie sortowanie w zależności od na procent pozycji nieposortowanych. Zastosowanie metody wstawiania było kluczowe w poprawie wydajności.