Jak najszybciej uporządkować książki? - Chand John

Zobacz całą lekcję: http://ed.ted.com/lessons/what-s-the-fastest-way-to-alphabetize-your-bookshelf-chand-john

Pracujesz w bibliotece uniwersyteckiej. Jest środek spokojnego popołudnia, kiedy nagle przybywa dostawa 1280 książek. Książki są ustawione w rzędzie w losowej kolejności, a automatyczny system do segregacji się zepsuł. Jak można je szybko posortować? Chand John odpowiada na to pytanie, pokazując, jak algorytmy pomagają bibliotekarzom i wyszukiwarkom w szybkim sortowaniu informacji.

Lekcja: Chad John, animacja: Anton Trofimov.

Pracujesz w bibliotece uniwersyteckiej.

Jest środek spokojnego popołudnia,

kiedy nagle przybywa dostawa 1280 książek.

Książki zostały ułożone
w jednym, długim rzędzie

w losowej kolejności,

a automatyczny system
do segregacji jest zepsuty.

Co gorsza, jutro zaczynają się zajęcia,

co oznacza, że z samego rana

książek będą szukać tłumy studentów.

Jak posortować je na czas?

Jeden ze sposobów to rozpoczęcie
od pierwszej pary książek z jednego końca.

Jeśli dwie pierwsze książki
są dobrze ułożone, zostaw je bez zmian.

W przeciwnym razie zamień je miejscami.

Teraz spójrz na drugą i trzecią książkę,

powtórz proces

i kontynuuj, aż dotrzesz do końca linii.

W końcu natkniesz się na książkę,
która powinna być ostatnia.

Zamieniaj ją z każdą kolejną książką,

przesuwając wzdłuż rzędu aż na koniec.

Następnie zacznij od początku
i powtórz cały proces,

żeby umieścić przedostatnią
książkę na swoim miejscu.

Kontynuuj, aż książki będą posortowane.

Ten sposób to sortowanie bąbelkowe.

Jest łatwe, ale powolne.

W pierwszej rundzie
byłoby 1279 porównań,

w kolejnej 1278 i tak dalej,

co w sumie daje 818 560 porównań.

Gdyby każde zajęło tylko sekundę,
proces potrwałby ponad dziewięć dni.

Inny sposób rozpoczyna się od ułożenia
tylko dwóch pierwszych książek.

Następnie weź trzecią książkę i porównaj
do tej stojącej na drugim miejscu.

Jeśli powinna znaleźć się
przed nią, zamień je.

Potem porównaj ją do pierwszej książki

i jeśli trzeba, zamień miejscami.

Trzy pierwsze książki są już posortowane.

Dodawaj po jednej nowej książce
do posortowanej grupy,

porównując ją i zamieniając
z książką stojącą przed nią,

aż trafi na właściwe miejsce.

Ten sposób to sortowanie przez wstawianie.

W odróżnieniu od sortowania bąbelkowego
nie trzeba porównywać każdej pary książek.

Każdą książkę będzie trzeba
porównać średnio

tylko z połową tych, stojących przed nią.

W tym przypadku
całkowita liczba porównań

wyniosłaby 409 280,

co zajęłoby prawie pięć dni.

To wciąż zbyt wiele porównań.

Oto lepszy pomysł.

Najpierw wybierz przypadkową książkę.

Nazwijmy ją przegrodą
i porównajmy z pozostałymi książkami.

Następnie podzielmy rząd,

umieszczając wszystkie książki, które mają
znaleźć się przed przegrodą po jej lewej,

a te, które powinny stanąć za nią,
po jej prawej stronie.

Właśnie oszczędziliśmy mnóstwo czasu.

Już nie będzie trzeba porównywać
żadnej z książek po lewej

do tych po prawej stronie.

Teraz patrząc tylko na książki
po lewej stronie,

można wybrać przypadkową przegrodę

i oddzielić książki, mające stać przed,
od tych, które powinny stanąć za nią.

Można dalej tworzyć takie przegrody,

aż uzyska się wiele małych grup,

z których każdą posortuje się,
używając innej strategii.

Każde rozdzielenie wymaga
około 1280 porównań.

Jeśli segmenty są w miarę równe,

podzielenie książek na 128 grup po 10
będzie wymagało około siedmiu rund

albo 8960 sekund.

Posortowanie każdej grupy
zajmie wtedy około 22 sekund.

Tak czy inaczej ta metoda
znana jako sortowanie szybkie

może posortować książki
w mniej niż 3,5 godziny.

Ale jest haczyk.

Segmenty mogą okazać się niesymetryczne,
co oznacza brak oszczędności czasu.

Na szczęście rzadko się to zdarza.

Dlatego sortowanie szybkie
to jedna z najbardziej wydajnych strategii

używanych przez dzisiejszych programistów.

Korzysta się z niej do sortowania towarów
w sklepie internetowym według ceny

albo tworzenia listy
pobliskich stacji benzynowych,

ułożonych według odległości.

Właśnie udało się skończyć
szybkie sortowanie przed czasem.

Za tobą kolejny
pracowity dzień w bibliotece.