Sortowanie biblioteczne

Z Wikipedii

Library sort, lub Sortowanie biblioteczne to algorytm sortowania który bazuje na algorytmie sortowania przez wstawianie, ale z dodaniem pustych miejsc w tablicy w celu przyśpieszenie wstawiania elementów. Nazwa wywodzi się z następującej analogii:

Wyobraźmy sobię bibliotekarza, który układa książki alfabetycznie na półkach. Zaczynją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 bedzie musiał przesunąć wszystkie książki od miejsca, gdzie pasuje nowa książka aż do ostatniej książki. Ponieważ litera B występuje blisko poczatku alfabetu, więc praktycznie całą półkę książek należy przesunąć. W celu przyśpieszenia pracy bibliotekarz powinien zostawiać wolne miejsce po każdej książce i wówczas może wstawić jedną nową książkę na półkę bez przesuwania. Na tym polega algorytm Sortowania bibliotecznego.^{[potrzebne źródło]}

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

[edytuj] Bibliografia

• Original publication at Citeseer