Sortowanie porównawcze - Comparison sort

Sortowanie zestawu nieoznakowanych odważników według wagi przy użyciu tylko wagi wyważającej wymaga algorytmu sortowania porównawczego.

Porównanie sortowania to rodzaj algorytmu sortowania , że tylko odczytuje elementy listy poprzez pojedynczej operacji streszczenie porównanie (często „mniej niż lub równy” operatora lub porównania trójdrożny ), który decyduje, który z dwóch elementów powinno nastąpić najpierw w ostateczna posortowana lista. Jedynym wymaganiem jest, aby operator złożył całkowite zamówienie przedpremierowe na dane, przy czym:

jeśli a ≤ b i b ≤ c, to a ≤ c (przechodniość)
dla wszystkich a i b , a ≤ b lub b ≤ a ( powiązanie ).

Możliwe, że a ≤ b i b ≤ a ; w takim przypadku którykolwiek z nich może zająć pierwsze miejsce na posortowanej liście. W stabilnym sortowaniu kolejność wprowadzania określa w tym przypadku porządek sortowania.

Metaforą myślenia o rodzajach porównawczych jest to, że ktoś ma zestaw nieoznaczonych odważników i wagę . Ich celem jest uporządkowanie odważników według ich wagi bez żadnych informacji, z wyjątkiem tych uzyskanych przez umieszczenie dwóch odważników na wadze i sprawdzenie, który z nich jest cięższy (lub jeśli waży tyle samo).

Przykłady

Szybkie sortowanie w akcji na liście liczb. Poziome linie są wartościami obrotowymi.

Niektóre z najbardziej znanych rodzajów porównań obejmują:

Ograniczenia wydajności i zalety różnych technik sortowania

Istnieją fundamentalne ograniczenia wydajności typów porównawczych. Sortowanie porównawcze musi mieć dolną granicę wielkości średniej wielkości Ω ( n log n ) operacji porównania, co jest znane jako czas liniowo-rytmiczny . Jest to konsekwencja ograniczonej ilości informacji dostępnych tylko poprzez porównania - lub, mówiąc inaczej, niejasnej struktury algebraicznej całkowicie uporządkowanych zbiorów. W tym sensie, scalanie, heapsort i introsort są asymptotycznie optymalne pod względem liczby porównań, które muszą wykonać, chociaż ta metryka pomija inne operacje. Sortowania bez porównania (takie jak przykłady omówione poniżej) mogą osiągnąć wydajność O ( n ) przy użyciu operacji innych niż porównania, co pozwala im ominąć tę dolną granicę (zakładając, że elementy mają stałą wielkość).

Sortowanie porównawcze może działać szybciej na niektórych listach; wiele sortowań adaptacyjnych, takich jak sortowanie przez wstawianie, działa w czasie O ( n ) na już posortowanej lub prawie posortowanej liście. Ω ( n log n ) dolna granica odnosi się tylko do przypadku, w którym lista wejściowe mogą być w każdej możliwej kolejności.

Rzeczywiste miary szybkości sortowania mogą wymagać uwzględnienia zdolności niektórych algorytmów do optymalnego wykorzystania stosunkowo szybkiej pamięci podręcznej komputera lub aplikacja może skorzystać z metod sortowania, w których posortowane dane zaczynają szybko pojawiać się użytkownikowi (a następnie szybkość użytkownika odczytu będzie czynnikiem ograniczającym) w przeciwieństwie do metod sortowania, w których dane wyjściowe nie są dostępne, dopóki cała lista nie zostanie posortowana.

Pomimo tych ograniczeń sortowanie porównawcze ma znaczącą praktyczną zaletę, polegającą na tym, że kontrola nad funkcją porównania umożliwia sortowanie wielu różnych typów danych i precyzyjną kontrolę nad sortowaniem listy. Na przykład odwrócenie wyniku funkcji porównania umożliwia odwrotne sortowanie listy; i można posortować listę krotek w porządku leksykograficznym, po prostu tworząc funkcję porównującą, która porównuje każdą część w kolejności:

function tupleCompare((lefta, leftb, leftc), (righta, rightb, rightc))
    if lefta ≠ righta
        return compare(lefta, righta)
    else if leftb ≠ rightb
        return compare(leftb, rightb)
    else
        return compare(leftc, rightc)

Zrównoważona notacja trójskładnikowa pozwala na dokonywanie porównań w jednym kroku, których wynikiem będzie „mniejszy niż”, „większy niż” lub „równy”.

Sortowania porównawcze zwykle łatwiej dostosowują się do złożonych zamówień, takich jak kolejność liczb zmiennoprzecinkowych . Ponadto po napisaniu funkcji porównawczej można używać dowolnego sortowania porównawczego bez modyfikacji; sortowania nieporównane zazwyczaj wymagają wyspecjalizowanych wersji dla każdego typu danych.

Ta elastyczność, wraz z wydajnością powyższych algorytmów sortowania porównawczego na nowoczesnych komputerach, doprowadziła do powszechnego preferowania sortowania porównawczego w większości praktycznych prac.

Alternatywy

Niektóre problemy z sortowaniem dopuszczają znacznie szybsze rozwiązanie niż $Ω (n log n)$ związane z sortowaniem porównawczym przy użyciu sortowania nieporównawczego ; przykładem jest sortowanie liczb całkowitych , gdzie wszystkie klucze są liczbami całkowitymi. Gdy klucze tworzą mały (w porównaniu do $n$ ) zakres, sortowanie zliczające jest przykładem algorytmu działającego w czasie liniowym. Inne algorytmy sortowania liczb całkowitych, takie jak sortowanie radix , nie są asymptotycznie szybsze niż sortowanie porównawcze, ale w praktyce mogą być szybsze.

Problem sortowania par liczb według ich sumy również nie podlega ograniczeniu $Ω (n ² log n)$ (kwadrat wynikający z parowania); najbardziej znany algorytm nadal zajmuje $O (n ² log n)$ czasu, ale tylko $O (n ²)$ porównań.

Liczba porównań wymaganych do posortowania listy

n	${\ Displaystyle \ lewo \ lceil \ log _ {2} (n!) \ prawo \ rceil}$	Minimum
1	0	0
2	1	1
3	3	3
4	5	5
5	7	7
6	10	10
7	13	13
8	16	16
9	19	19
10	22	22
11	26	26
12	29	30
13	33	34
14	37	38
15	41	42
16	45	45 lub 46
17	49	49 lub 50
18	53	53 lub 54
19	57	58
20	62	62
21	66	66
22	70	71

n	${\ Displaystyle \ lewo \ lceil \ log _ {2} (n!) \ prawo \ rceil}$	${\ Displaystyle n \ log _ {2} n - {\ Frac {n} {\ ln 2}}}$
10	22	19
100	525	521
1 000	8 530,	8 524,
dziesięć tysięcy	118 459,	118 451,
100 000	1 516 705,	1 516 695,
1 000 000	18 488 885,	18 488 874,

Powyżej: Porównanie dolnej granicy z rzeczywistą minimalną liczbą porównań (z OEIS : A036604 ) wymaganych do posortowania listy n pozycji (dla najgorszego przypadku). Poniżej: używając przybliżenia Stirlinga , ta dolna granica jest dobrze przybliżona przez .

{\ Displaystyle \ lewo \ lceil \ log _ {2} (n!) \ prawo \ rceil}

{\ Displaystyle n \ log _ {2} n - {\ Frac {n} {\ ln 2}}}

Liczba porównań wymaganych przez algorytm sortowania porównawczego rośnie proporcjonalnie , gdzie jest liczbą elementów do sortowania. To wiązanie jest asymptotycznie ciasne . ${\ Displaystyle n \ log (n)}$ ${\ displaystyle n}$

Biorąc pod uwagę listę różnych liczb (możemy to założyć, ponieważ jest to analiza najgorszego przypadku), istnieją permutacje czynnikowe , z których dokładnie jedna jest listą w porządku posortowanym. Algorytm sortowania musi uzyskać wystarczającą ilość informacji z porównań, aby zidentyfikować poprawną permutację. Jeśli algorytm zawsze kończy działanie po co najwyżej krokach, nie może rozróżnić więcej niż przypadków, ponieważ klucze są różne, a każde porównanie daje tylko dwa możliwe wyniki. W związku z tym, ${\ displaystyle n}$ ${\ displaystyle f (n)}$ ${\ Displaystyle 2 ^ {f (n)}}$

{\ Displaystyle 2 ^ {f (n)} \ geq n!}

lub równoważnie

{\ Displaystyle f (n) \ geq \ log _ {2} (n!).}

Patrząc na pierwsze czynniki , otrzymujemy ${\ displaystyle n / 2}$ ${\ Displaystyle n! = n (n-1) \ cdots 1}$

{\ Displaystyle \ log _ {2} (n!) \ geq \ log _ {2} \ lewo (\ lewo ({\ Frac {n} {2}} \ prawo) ^ {\ Frac {n} {2} } \ right) = {\ frac {n} {2}} {\ frac {\ log n} {\ log 2}} - {\ frac {n} {2}} = \ Theta (n \ log n). }

{\ Displaystyle \ log _ {2} (n!) = \ Omega (n \ log n).}

Zapewnia to dolną część roszczenia. Lepszą granicę można podać za pomocą przybliżenia Stirlinga .

Identyczna górna granica wynika z istnienia algorytmów, które osiągają tę granicę w najgorszym przypadku, takich jak sortowanie i łączenie .

Powyższy argument zapewnia bezwzględną , a nie tylko asymptotyczną dolną granicę liczby porównań, czyli porównań. Ta dolna granica jest dość dobra (można ją osiągnąć w ramach liniowej tolerancji przez proste sortowanie przez scalanie), ale wiadomo, że jest niedokładna. Na przykład, ale wykazano, że minimalna liczba porównań do sortowania 13 elementów wynosi 34. ${\ Displaystyle \ lewo \ lceil \ log _ {2} (n!) \ prawo \ rceil}$ ${\ Displaystyle \ lewo \ lceil \ log _ {2} (13!) \ prawo \ rceil = 33}$

Określenie dokładnej liczby porównań potrzebnych do posortowania określonej liczby wpisów jest trudnym obliczeniowo problemem nawet dla małego n i nie jest znany prosty wzór na rozwiązanie. Niektóre z nielicznych konkretnych wartości, które zostały obliczone, można znaleźć w artykule OEIS : A036604 .

Dolna granica średniej liczby porównań

Podobna granica dotyczy średniej liczby porównań. Przy założeniu, że

wszystkie klucze są różne, tj. każde porównanie da albo a > b, albo a < b , i
wejście jest permutacją losową, wybraną równomiernie ze zbioru wszystkich możliwych permutacji n elementów,

nie można określić, w jakiej kolejności znajdują się dane wejściowe, przy średniej liczbie porównań mniejszej niż $log 2 (n!)$ .

Najłatwiej można to zobaczyć, używając pojęć z teorii informacji . Shannon entropia takiego losowego permutację $log 2 (n!)$ Bitów. Ponieważ porównanie może dać tylko dwa wyniki, maksymalna ilość dostarczonych informacji to 1 bit. Dlatego po k porównaniach pozostała entropia permutacji, biorąc pod uwagę wyniki tych porównań, wynosi średnio co najmniej $log 2 (n!) - k$ bitów. Aby przeprowadzić sortowanie, potrzebna jest pełna informacja, więc pozostała entropia musi wynosić 0. Wynika z tego, że k musi wynosić średnio co najmniej $log 2 (n!)$ .

Dolna granica uzyskana za pomocą teorii informacji jest określana jako „dolna granica teoretyczno-informacyjna”. Teoretyczna dolna granica informacji jest poprawna, ale niekoniecznie jest najsilniejszą dolną granicą. W niektórych przypadkach teoretyczna dolna granica problemu może być nawet daleka od prawdziwej dolnej granicy. Na przykład, dolną granicą selekcji w teorii informacji jest, podczas gdy porównania są potrzebne przez kontradyktoryjny argument. Wzajemne oddziaływanie między dolną granicą opartą na teorii informacji a prawdziwą dolną granicą jest bardzo podobne do funkcji o wartościach rzeczywistych ograniczającej dolną granicę funkcji całkowitej. Jednak nie jest to dokładnie poprawne, gdy weźmie się pod uwagę średni przypadek. ${\ Displaystyle \ lewo \ lceil \ log _ {2} (n) \ prawo \ rceil}$ ${\ displaystyle n-1}$

Aby odkryć, co się dzieje podczas analizy przeciętnego przypadku, kluczowe jest to, do czego odnosi się termin „średnia”? Uśrednianie nad czym? Mając pewną wiedzę z teorii informacji, teoretyczno-informacyjna dolna granica uśrednia zbiór wszystkich permutacji jako całości. Jednak wszelkie algorytmy komputerowe (w ramach tego, co się obecnie uważa) muszą traktować każdą permutację jako indywidualny przypadek problemu. W związku z tym średnia dolna granica, której szukamy, jest uśredniana dla wszystkich indywidualnych przypadków.

Aby wyszukać dolną granicę związaną z nieosiągalnością komputerów, przyjmujemy model drzewa decyzyjnego . Powiedzmy trochę inaczej, jaki jest nasz cel. W modelu drzewa decyzyjnego dolną granicą, która ma być pokazana, jest dolna granica średniej długości ścieżek od korzenia do liścia drzewa binarnego (w którym każdy liść odpowiada permutacji). Można by powiedzieć, że zrównoważone pełne drzewo binarne osiąga minimum średniej długości. Po dokładnych obliczeniach, dla zrównoważonego pełnego drzewa binarnego z liśćmi, średnia długość ścieżek od korzenia do liścia jest wyrażona wzorem ${\ displaystyle n!}$ ${\ displaystyle n!}$

{\ Displaystyle {\ Frac {(2n! -2 ^ {\ lfloor \ log _ {2} n! \ rfloor +1}) \ cdot \ lceil \ log _ {2} n! \ rceil + (2 ^ {\ lfloor \ log _ {2} n! \ rfloor +1} -n!) \ cdot \ lfloor \ log _ {2} n! \ rfloor} {n!}}}

Na przykład dla $n = 3$ dolna granica teoretyczno-informacyjna dla przeciętnego przypadku wynosi około 2,58, podczas gdy średnia dolna granica uzyskana z modelu drzewa decyzyjnego wynosi 8/3, około 2,67.

W przypadku, gdy wiele pozycji może mieć ten sam klucz, nie ma oczywistej interpretacji statystycznej terminu „przypadek średni”, więc argument taki jak powyższy nie może być zastosowany bez przyjęcia konkretnych założeń dotyczących rozmieszczenia kluczy.

Sortowanie wstępnie posortowanej listy

Jeśli lista jest już wstępnie posortowana, liczba porównań wymaganych do posortowania listy jest zwykle mniejsza. Pojęcie listy wstępnie posortowanej można sformalizować za pomocą różnych miar presortowania . Przy takiej miary istnieje pojęcie (słabo) optymalnego algorytmu sortowania. ${\ displaystyle m}$ ${\ displaystyle m}$

Uwagi

^ Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009) [1990]. Wprowadzenie do algorytmów (3rd ed.). MIT Press i McGraw-Hill. s. 191–193. ISBN 0-262-03384-4 .
^ Mark Wells, Zastosowania języka do obliczeń w kombinatoryce, Przetwarzanie informacji 65 (Proceedings of the 1965 IFIP Congress), 497–498, 1966.
^ Mark Wells, Elements of Combinatorial Computing, Pergamon Press, Oxford, 1971.
^ Takumi Kasai, Shusaku Sawato, Shigeki Iwata, Trzydzieści cztery porównania są wymagane do sortowania 13 pozycji, LNCS 792, 260-269, 1994.
^ Marcin Peczarski, Sortowanie 13 elementów wymaga 34 porównań, LNCS 2461, 785–794, 2002.
^ ^a ^b ^c Marcin Peczarski, Nowe wyniki sortowania porównawczego minimum, Algorithmica 40 (2), 133–145, 2004.
^ Marcin Peczarski, Komputerowe wspomaganie badań posetów, praca doktorska, Uniwersytet Warszawski, 2006.
^ Peczarski, Marcin (2007). „Algorytm Forda-Johnsona jest wciąż niepokonany dla mniej niż 47 elementów”. Inf. Proces. Lett . 101 (3): 126–128. doi : 10.1016 / j.ipl.2006.09.001 .
^ ^a ^b Cheng, Weiyi; Liu, Xiaoguang; Wang, Gang; Liu, Jing (październik 2007). "最少比较排序问题中 S （15）和 S （19）的解决" [Wyniki z S (15) i S (19) do problemu sortowania porównania minimum]. Journal of Frontiers of Computer Science and Technology (w języku chińskim). 1 (3): 305–313.
^ Peczarski, Marcin (3 sierpnia 2011). „W kierunku optymalnego sortowania 16 elementów”. Acta Universitatis Sapientiae . 4 (2): 215–224. arXiv : 1108.0866 . Bibcode : 2011arXiv1108.0866P .

Bibliografia

Donald Knuth . The Art of Computer Programming , tom 3: Sorting and Searching , wydanie drugie. Addison-Wesley, 1997. ISBN 0-201-89685-0 . Sekcja 5.3.1: Sortowanie według minimum porównawczego, s. 180–197.

[1] Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009) [1990]. Wprowadzenie do algorytmów (3rd ed.). MIT Press i McGraw-Hill. s. 191–193. ISBN 0-262-03384-4 .

[Wells1965-2] Mark Wells, Zastosowania języka do obliczeń w kombinatoryce, Przetwarzanie informacji 65 (Proceedings of the 1965 IFIP Congress), 497–498, 1966.

[Wells1971-3] Mark Wells, Elements of Combinatorial Computing, Pergamon Press, Oxford, 1971.

[KasaiSawatoIwata1994-4] Takumi Kasai, Shusaku Sawato, Shigeki Iwata, Trzydzieści cztery porównania są wymagane do sortowania 13 pozycji, LNCS 792, 260-269, 1994.

[Peczarski2002-5] Marcin Peczarski, Sortowanie 13 elementów wymaga 34 porównań, LNCS 2461, 785–794, 2002.

[Peczarski2004-6] Marcin Peczarski, Nowe wyniki sortowania porównawczego minimum, Algorithmica 40 (2), 133–145, 2004.

[Peczarski2006-7] Marcin Peczarski, Komputerowe wspomaganie badań posetów, praca doktorska, Uniwersytet Warszawski, 2006.

[Peczarski2007-8] Peczarski, Marcin (2007). „Algorytm Forda-Johnsona jest wciąż niepokonany dla mniej niż 47 elementów”. Inf. Proces. Lett . 101 (3): 126–128. doi : 10.1016 / j.ipl.2006.09.001 .

[ChengLiuWang2007-9] Cheng, Weiyi; Liu, Xiaoguang; Wang, Gang; Liu, Jing (październik 2007). "最少比较排序问题中 S （15）和 S （19）的解决" [Wyniki z S (15) i S (19) do problemu sortowania porównania minimum]. Journal of Frontiers of Computer Science and Technology (w języku chińskim). 1 (3): 305–313.

[10] Peczarski, Marcin (3 sierpnia 2011). „W kierunku optymalnego sortowania 16 elementów”. Acta Universitatis Sapientiae . 4 (2): 215–224. arXiv : 1108.0866 . Bibcode : 2011arXiv1108.0866P .

Languages

In other projects