algorytmy sortowania są niewygodną kombinacją zasadniczo niezbędnych i głęboko spornych. Od nowych inżynierów, którzy chcą zaimponować w wywiadzie, po starszych inżynierów szukających rozwiązania dla szybko skalującej się bazy danych, istnieje wiele czynników, które należy wziąć pod uwagę. Jaka jest szybkość porównywania dwóch obiektów? Jaki jest czas wymiany? Jak duża jest baza danych? Jakiego rodzaju obiekty zawiera? Czy to już częściowo posortowane? Czy wyniki muszą być stabilne?

każde z tych pytań może wyciągnąć argumenty na korzyść jednego lub drugiego algorytmu. Czy dane źródłowe są duże i złożone? Większość języków domyślnie standardowego, szybkiego sortowania z jego O( N log N) złożoności czasu. Jest mniejszy? Sortowanie wstawiania działa na nich cuda. Głównie posortowane? Cholera, bańki prawie na to działają. Jeśli chcesz przeczytać / zobrazować zalety każdego z nich, sprawdź to porównanie według toptal.com.

jednym algorytmem sortowania, którego nie znajdziesz na tej stronie, ani prawie żadnym innym, jest Tim Sort. Ten niejasny rodzaj jest obecnie unikalny dla Pythona i jest używany jako domyślny algorytm sortowania. Wywołanie array.sort w Pythonie, A Tim Sort jest wykonywany. Mimo to rzadko spotyka się inżynierów, którzy znają i rozumieją Tima Sort. Więc: co to jest?

Tim Sort został po raz pierwszy zaimplementowany w 2002 roku przez Tima Petersa do użycia w Pythonie. Rzekomo wynikało to ze zrozumienia, że większość algorytmów sortujących rodzi się w szkołach i nie jest zaprojektowana do praktycznego zastosowania na rzeczywistych danych. Tim Sort wykorzystuje typowe wzorce w danych i wykorzystuje kombinację sortowania scalającego i sortowania wstawiania wraz z wewnętrzną logiką w celu optymalizacji manipulacji danymi o dużej skali.

dlaczego Tim sort?

patrząc na rysunek 2, od razu widać coś ciekawego. W najlepszym przypadku Tim Sort przewyższa Merge Sort i Quick Sort. W najgorszym przypadku działa z porównywalną prędkością Merge Sort i faktycznie przewyższa Quick Sort. Innymi słowy, jest nieoczekiwanie szybki.

Jeśli chodzi o przestrzeń, Tim Sort znajduje się na gorszym końcu spektrum, ale uwzględnienie przestrzeni dla większości algorytmów sortujących jest dość rzadkie. O (n) nie jest zbyt szorstki w większości przypadków; warto zauważyć jako możliwy niedobór, a jedyne miejsce, w którym Quick Sort naprawdę przyćmiewa Tima Sort.

ostatnim elementem, na którym często ocenia się algorytmy sortowania, jest stabilność. Stabilność to koncepcja, że po posortowaniu obiekty o równej wartości zachowują swój pierwotny porządek. Pewnie zastanawiasz się, dlaczego nam na tym zależy. Przedmioty mają jednakową wartość-dlaczego mamy na myśli sposób ich zamawiania?

prosta odpowiedź jest taka, że stabilność ma znaczenie dla ułożonych sortów. Oznacza to, że najpierw sortujesz na podstawie jednego kryterium, a następnie na podstawie drugiego. Jeśli zrobisz to w niestabilnym algorytmie, natychmiast stracisz niezawodność z pierwszego sortowania po uruchomieniu drugiego. Dla odniesienia, Quick Sort jest niestabilny, a Merge Sort jest stabilny.

Tim Sort jest również stabilny, nie wspominając o szybkim, jeśli nieco ciężkim(w porównaniu tylko do szybkiego sortowania). Podczas gdy algorytmy sortowania mogą (i powinny) być oceniane na podstawie innych czynników, są to wielkie trzy.

implementacja w trzech krokach

Tim Sort jest złożona, nawet według standardów algorytmicznych. Wdrożenie najlepiej podzielić na części.

Wyszukiwanie binarne

pierwszą rzeczą, której potrzebujesz, aby zaimplementować sortowanie Tim, jest metoda wyszukiwania binarnego. Jest to po prostu używane do późniejszej implementacji sortowania wstawiania.

dla odniesienia: binarne Algorytmy wyszukiwania

Insertion Sort& Merge Sort

Po drugie, musisz kodować Insertion Sort i Merge Sort. Są to znane algorytmy i powinny być w tylnej kieszeni większości inżynierów, ale omówimy podstawy ich działania i dlaczego są dla nas cenne.

sortowanie wstawiania jest bardzo podstawowym algorytmem sortowania. Przebiega przez tablicę i ilekroć napotka pozycję, która jest nie w porządku (ściśle mniej/więcej niż pozycja przed nią), przesuwa ją w odpowiednie miejsce w już posortowanej tablicy. Insertion Sort jest znany z bardzo szybkiego działania na już posortowanych tablicach, jak również na mniejszych tablicach. W rzeczywistości, możemy zobaczyć z Fig 2, że sortowanie wstawiania ma imponujący najlepszy czas działania O(n). Należy pamiętać o przechodzeniu do przodu z Tim Sort: najlepszym przypadkiem wstawiania Sort jest już posortowana tablica. To może zabrzmieć głupio, ale to będzie istotne.

Merge Sort działa natomiast na podstawowej zasadzie: scalanie już posortowanych tablic jest niezwykle łatwe. Tak więc, dzieli tablicę startową na pół w kółko, dopóki nie będzie niczym innym jak pojedynczymi elementami. Następnie powoli przebudowuje główną tablicę, łącząc te elementy z powrotem w posortowanej kolejności. Ponieważ zaczęliśmy od bloków o rozmiarze pierwszym, bardzo łatwo było zbudować początkowe posortowane tablice. Następnie łatwo je połączyć. W końcu spędzamy czas O (N log n) i (co ważne) robimy to w sposób gwarantujący stabilność.

przykładowe implementacje patrz:

Merge Sort:https://www.geeksforgeeks.org/merge-sort/

Insertion Sort:https://www.geeksforgeeks.org/insertion-sort/

implementacja Tim Sort

kluczem do zrozumienia implementacji Tim Sort jest zrozumienie jego użycia runów. Tim Sort wykorzystuje naturalnie występujące wstępnie skonfigurowane dane na swoją korzyść. Przez presorted rozumiemy po prostu, że wszystkie elementy sekwencyjne rosną lub maleją (nie dbamy o to, które).

najpierw ustawiamyminrun rozmiar. Rozumiemy przez to, że chcemy mieć pewność, że wszystkie nasze biegi mają co najmniej określoną długość. Pamiętaj, że nie gwarantujemy, że znajdziemy biegi tej wielkości — przejdziemy do tego później. Mówimy po prostu, że bieg musi mieć co najmniej określoną długość.

kiedy napotkamy bieg, odkładamy go na bok. Gdy znajdziemy najdłuższy przebieg w zakresie minrun. Mamy teraz znaną strukturę danych: małą, posortowaną tablicę. Jeśli jest to co najmniej minrun w długości, to huzzah! Możemy iść dalej. Jeśli tak nie jest, w grę wchodzi funkcja Insertion Sort.

z góry możesz pamiętać, że sortowanie wstawiania jest szczególnie skuteczne na dwóch typach tablic: małych i już posortowanych. To, co właśnie zrobiliśmy, to mała, posortowana tablica. Jeśli nie jest to przynajmniej minrun w długości, sięgamy do przodu i chwytamy wystarczająco dużo innych elementów, aby zakończyć bieg, a następnie użyj Insertion Sort, aby szybko i łatwo wprowadzić je do naszej posortowanej tablicy. Oczywiście, jeśli run napotka koniec tablicy, możesz pozwolić, aby była trochę krótka.

Po utworzeniu wszystkich uruchomień (tj. posortowanych podparć), używasz sortowania scalania, aby je połączyć. W najlepszym przypadku cała tablica jest już posortowana, A Tim Sort jest na tyle mądry, że wie, że nie musi robić nic innego. Innym razem jest to po prostu niezwykle wydajne. Dodatkową korzyścią jest to, że zarówno Insertion Sort, jak i Merge Sort są stabilne, więc wynikowa tablica jest stabilna.

dla tych, którzy wolą kule:

1. ustalminrun rozmiar, który jest mocą 2 (Zwykle 32, nigdy więcej niż 64 lub sortowanie wstawiania straci wydajność)
2. Znajdź run w pierwszymminrun danych.
3. Jeśli run nie ma co najmniejminrun długości, użyj opcji Insertion Sort, aby pobrać kolejne lub poprzednie elementy i wstawić je do run, dopóki nie będzie to prawidłowy minimalny rozmiar.
4. powtarzaj aż cała tablica zostanie podzielona na posortowane podrozdziały.
5. użyj drugiej połowy sortowania scalania, aby połączyć uporządkowane tablice.

wniosek

Tim Sort jest potężny. Jest szybki i stabilny, ale co najważniejsze wykorzystuje wzorce z prawdziwego świata i wykorzystuje je do budowy produktu końcowego. Czy na każdą sytuację? Prawdopodobnie nie. Powodzenia w programowaniu go na tablicy podczas rozmowy kwalifikacyjnej, a jeśli potrzebujesz tylko szybkiego prostego algorytmu sortowania w mgnieniu oka, prawdopodobnie nie chcesz zawracać sobie głowy implementacją czegoś tak złożonego. Jednak dla naukowców danych chrupanie liczb jest więcej niż warto spojrzeć.

dla ciekawych, możesz sprawdzić cały kod Tim Sort na GitHubie.

dzięki

dziękuję wszystkim czytelnikom. Doceniam twój czas i mam szczerą nadzieję, że znalazłeś treść informacyjną. Jeśli masz jakieś pytania lub odpowiedzi, napisz je poniżej.