Sortowanie w bibliotece
| Klasa | Algorytm sortowania |
|---|---|
| Struktura danych | Szyk |
| Wydajność w najgorszym przypadku | |
| Najlepsza wydajność | |
| Średnia wydajność | |
| Złożoność przestrzeni w najgorszym przypadku |
Sortowanie biblioteczne lub sortowanie przez wstawianie z przerwami to algorytm sortowania , który wykorzystuje sortowanie przez wstawianie , ale z przerwami w tablicy, aby przyspieszyć kolejne wstawienia. Nazwa pochodzi z analogii:
Załóżmy, że bibliotekarz przechowuje swoje książki alfabetycznie na długiej półce, zaczynając od litery A na lewym końcu i kontynuując w prawo wzdłuż półki bez odstępów między książkami, aż do końca litery Z. Jeśli bibliotekarz nabył nową książkę, która należy do sekcji B, po znalezieniu odpowiedniego miejsca w sekcji B będzie musiał przesunąć każdą książkę, od środka sekcji B do Z, aby zrobić miejsce na nową książkę. To jest sortowanie przez wstawianie. Gdyby jednak mieli zostawić spację po każdej literze, o ile było jeszcze miejsce po B, musieliby przesunąć tylko kilka książek, aby zrobić miejsce na nową. Jest to podstawowa zasada sortowania bibliotecznego.
Algorytm został zaproponowany przez Michaela A. Bendera , Martína Farach-Coltona i Miguela Mosteiro w 2004 roku i został opublikowany w 2006 roku.
Podobnie jak sortowanie przez wstawianie, na którym jest oparte, sortowanie biblioteczne jest sortowaniem porównawczym ; wykazano jednak, że ma duże prawdopodobieństwo uruchomienia w czasie O(n log n) (porównywalnym z sortowaniem szybkim ), a nie O(n 2 ) sortowania przez wstawianie. W artykule nie podano pełnej implementacji ani dokładnych algorytmów ważnych części, takich jak wstawianie i równoważenie. Potrzebne byłyby dalsze informacje, aby omówić, w jaki sposób efektywność sortowania bibliotecznego wypada w porównaniu z innymi metodami sortowania w rzeczywistości.
W porównaniu z podstawowym sortowaniem przez wstawianie wadą sortowania bibliotecznego jest to, że wymaga dodatkowego miejsca na luki. Ilość i rozmieszczenie tej przestrzeni byłyby zależne od implementacji. W artykule rozmiar potrzebnej tablicy to (1 + ε)n , ale bez dalszych zaleceń dotyczących wyboru ε. Co więcej, nie jest ani adaptacyjny, ani stabilny. Aby zagwarantować granice czasowe z wysokim prawdopodobieństwem, wymaga losowej permutacji danych wejściowych, co zmienia względną kolejność równych elementów i tasuje dowolne wstępnie posortowane dane wejściowe. Algorytm wykorzystuje również wyszukiwanie binarne, aby znaleźć punkt wstawienia dla każdego elementu, co nie wykorzystuje wstępnie posortowanych danych wejściowych.
Inną wadą jest to, że nie można go uruchomić jako algorytmu online , ponieważ nie jest możliwe losowe przetasowanie danych wejściowych. Jeśli zostanie użyty bez tego tasowania, może łatwo przerodzić się w zachowanie kwadratowe.
Jedną ze słabości sortowania przez wstawianie jest to, że może wymagać dużej liczby operacji zamiany i być kosztowne, jeśli zapis w pamięci jest drogi. Sortowanie według biblioteki może to nieco poprawić na etapie wstawiania, ponieważ mniej elementów musi zostać przesuniętych, aby zrobić miejsce, ale powoduje również dodatkowy koszt na etapie ponownego równoważenia. Ponadto lokalizacja odniesienia będzie słaba w porównaniu z sortowaniem przez scalanie , ponieważ każde wstawienie z losowego zestawu danych może uzyskać dostęp do pamięci, która nie jest już w pamięci podręcznej, zwłaszcza w przypadku dużych zestawów danych.
Realizacja
Algorytm
Załóżmy, że mamy tablicę n elementów. Wybieramy lukę, którą zamierzamy dać. Wtedy otrzymalibyśmy końcową tablicę o rozmiarze (1 + ε)n. Algorytm działa w log n rundach. W każdej rundzie wstawiamy tyle elementów, ile jest już w ostatecznej tablicy, przed ponownym zbalansowaniem tablicy. Aby znaleźć miejsce wstawienia, stosujemy wyszukiwanie binarne w końcowej tablicy, a następnie zamieniamy kolejne elementy, aż trafimy na puste miejsce. Po zakończeniu rundy ponownie równoważymy ostateczną tablicę, wstawiając spacje między każdym elementem.
Poniżej przedstawiono trzy ważne kroki algorytmu:
- Wyszukiwanie binarne : Znajdowanie pozycji wstawienia poprzez zastosowanie wyszukiwania binarnego w ramach już wstawionych elementów. Można to zrobić, przesuwając się liniowo w kierunku lewej lub prawej strony tablicy, jeśli trafisz na puste miejsce w środkowym elemencie.
- Wstawianie : Wstawianie elementu w znalezionej pozycji i zamiana kolejnych elementów o 1 pozycję, aż zostanie trafione puste miejsce. Odbywa się to w czasie logarytmicznym z dużym prawdopodobieństwem.
- Ponowne równoważenie : Wstawianie spacji między każdą parą elementów w tablicy. Koszt ponownego zrównoważenia jest liniowy w stosunku do liczby już wstawionych elementów. Ponieważ długości te zwiększają się o potęgę 2 dla każdej rundy, całkowity koszt ponownego zrównoważenia jest również liniowy.
Pseudo kod
procedury (A, początek, koniec) to r ← koniec w ← koniec ÷ 2 podczas gdy r ≥ początek do A[w+1] ← przerwa A[w] ← A[r] r ← r − 1 w ← w − 2
procedura sort(A) is n ← length(A) S ← nowa tablica n przerw dla i ← 1 do floor(log2(n) + 1) do for j ← 2^i do 2^(i + 1) do ins ← wyszukiwanie binarne(A[j], S, 2^(i − 1)) wstaw A[j] w S[ins]
Tutaj binarysearch(el, A, k) wykonuje wyszukiwanie binarne w pierwszych k elementach A , pomijając luki, aby znaleźć miejsce, w którym można zlokalizować element el . Wstawianie powinno faworyzować luki w stosunku do elementów wypełnionych.