Sortowanie biblioteczne

Sortowanie biblioteczne (ang. Library sort) – algorytm sortowania, który bazuje na algorytmie sortowania przez wstawianie, ale z dodawaniem pustych miejsc w tablicy w celu przyspieszenia wstawiania elementów.

Sortowanie biblioteczne

Rodzaj	Sortowanie
Struktura danych	Tablica
Złożoność
Czasowa	Średnie: ${\displaystyle O(n\cdot \log(n))}$ Pesymistyczne: ${\displaystyle O(n^{2})}$
Pamięciowa	${\displaystyle O(n)}$

Nazwa wywodzi się z następującej analogii:

Wyobraźmy sobie bibliotekarza, który układa książki alfabetycznie na półkach. Zaczynając od książek na literę A ustawia jedną przy drugiej, aż dojdzie do litery Z. Jeśli bibliotekarz postanowi dodać nową książkę na półkę, której nazwa zaczyna się na literę B, to będzie musiał przesunąć wszystkie książki od miejsca, gdzie pasuje nowa książka aż do ostatniej książki. Ponieważ litera B występuje blisko początku alfabetu, więc praktycznie całą półkę książek należy przesunąć. Tak działa sortowanie przez wstawianie. Gdyby jednak bibliotekarz pozostawiał wolne miejsce po każdej literze, to musiałby przesunąć tylko niewielką liczbę książek (dopóki miejsce za literą B by się nie wyczerpało). Na tym polega algorytm Sortowania bibliotecznego^[1].

Algorytm zaproponowali: Michael A. Bender, Martín Farach-Colton oraz Miguel Mosteiro w 2004 roku^[2]. Podobnie jak sortowanie przez wstawianie, na którym bazuje, sortowanie biblioteczne jest algorytmem stabilnym. Wykazano, że jego złożoność czasowa wynosi najczęściej ${\displaystyle O(n\cdot \log(n))}$ (podobnie jak algorytmu quicksort), rzadziej ${\displaystyle O(n^{2})}$ (jak przy sortowaniu przez wstawianie). Mankamentem algorytmu jest zwiększone zapotrzebowanie na pamięć.

Przypisy

1. Timothy A.: An Active Learning approach to Data Structures using C. [dostęp 2017-07-30]. [zarchiwizowane z tego adresu (2011-07-20)]. (ang.).
2. M.A. Bender, M. Farach-Colton, M. Mosteiro: Insertion Sort is O(n log n). [dostęp 2017-07-30]. (ang.).