Sortowanie porównawcze

Sortowanie zestawu nieoznakowanych odważników według wagi przy użyciu samej wagi wymaga zastosowania algorytmu sortowania porównawczego.

Sortowanie przez porównanie to rodzaj algorytmu sortowania , który odczytuje tylko elementy listy za pomocą pojedynczej abstrakcyjnej operacji porównania (często operatora „mniejsze niż lub równe” lub porównania trójstronnego ), która określa, który z dwóch elementów powinien wystąpić jako pierwszy w ostateczna posortowana lista. Jedynym wymaganiem jest, aby operator utworzył całkowite zamówienie przedpremierowe na dane, z:

1. jeśli a ≤ b i b ≤ c, to a ≤ c (przechodniość)
2. dla wszystkich a i b , a ≤ b lub b ≤ a ( spójność ).

Jest możliwe, że zarówno a ≤ b , jak i b ≤ a ; w tym przypadku każdy z nich może zająć pierwsze miejsce na posortowanej liście. W przypadku sortowania stabilnego kolejność wejściowa określa w tym przypadku kolejność sortowania.

Metaforą myślenia o rodzajach porównawczych jest to, że ktoś ma zestaw nieoznakowanych odważników i wagę równoważącą . Ich celem jest ustawienie odważników w kolejności 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 czy ważą tyle samo).

Przykłady

Szybkie sortowanie w akcji na liście numerów. Linie poziome to wartości obrotowe.

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

• Szybkie sortowanie
• sortowanie
• sortowanie skorup
• Sortuj przez scalanie
• Introsort
• Sortowanie przez wstawianie
• Sortowanie przez wybór
• Sortowanie bąbelkowe
• Sortowanie nieparzyste-parzyste
• Rodzaj shakera do koktajli
• Sortowanie cykliczne
• Sortowanie przez wstawianie
• Sortowanie gładkie
• Timsort
• Sortowanie blokowe

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

Istnieją podstawowe ograniczenia dotyczące wydajności sortowania porównawczego. Sortowanie porównawcze musi mieć dolną granicę operacji porównania Ω ( n log n ), która jest znana jako czas liniowy . Jest to konsekwencją ograniczonych informacji dostępnych poprzez same porównania — lub, mówiąc inaczej, niejasnej struktury algebraicznej zbiorów całkowicie uporządkowanych. W tym sensie mergesort, 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, pozwalając im ominąć tę dolną granicę (zakładając, że elementy mają stały rozmiar).

Sortowanie przez porównanie 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. Dolna granica Ω ( n log n ) dotyczy tylko przypadku, w którym lista wejść może być w dowolnej 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ą pojawiać się użytkownikowi szybko (a następnie prędkość użytkownika czytania będzie czynnikiem ograniczającym) w przeciwieństwie do metod sortowania, w których żadne dane wyjściowe nie są dostępne, dopóki cała lista nie zostanie posortowana.

Pomimo tych ograniczeń, sortowanie porównawcze oferuje zauważalną 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 sposobem sortowania listy. Na przykład odwrócenie wyniku funkcji porównania umożliwia posortowanie listy w odwrotnej kolejności; i można posortować listę krotek w porządku leksykograficznym , tworząc po prostu funkcję porównania, która porównuje każdą część po kolei:

         funkcja  tupleCompare((lewo, lewob, lewoc), (prawoa, prawob, prawoc))  if  lefta ≠ righta  return  porównaj(lewo, righta)  else if  leftb ≠ rightb  return  porównaj(lewob, rightb)  else  return  porównaj(lewoc, rightc) 

Sortowanie przez porównanie generalnie łatwiej dostosowuje się do złożonych porządków, takich jak kolejność liczb zmiennoprzecinkowych . Dodatkowo, po napisaniu funkcji porównania, można użyć dowolnego sortowania porównania bez modyfikacji; sortowanie bez porównania zazwyczaj wymaga 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 prac praktycznych.

Alternatywy

Niektóre problemy z sortowaniem dopuszczają ściśle szybsze rozwiązanie niż Ω( n log n ) związane z sortowaniem porównawczym przy użyciu sortowania bez porównania ; 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, przykładowym algorytmem działającym w czasie liniowym jest sortowanie zliczające . Inne algorytmy sortowania liczb całkowitych, takie jak radix sort , 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 wiązaniu Ω( n ² log n ) (kwadrat wynikający z parowania); najbardziej znany algorytm nadal zajmuje czas O( n ² log n ) , 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
10000	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 ${\ Displaystyle \ lewo \ lceil \ log _ {2} (n!) \ prawo \ rceil}$ z rzeczywistą minimalną liczbą porównań (z OEIS : A036604 ) wymagane do posortowania listy n elementów (w najgorszym przypadku). Poniżej: Używając przybliżenia Stirlinga , ta dolna granica jest dobrze przybliżona przez ${\ Displaystyle n \ log _ {2} n- {\ Frac {n} {\ ln 2}}}$ .

$wymaganych$$przez$ proporcjonalnie do , gdzie jest elementów Ta granica jest asymptotycznie ścisła .

Biorąc pod uwagę listę różnych liczb (możemy to założyć, ponieważ jest to analiza najgorszego przypadku), istnieją $permutacje$ , z których dokładnie jedna jest listą w posortowanej kolejności. 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 $,$$różne$ rozróżnić więcej klucze a każde porównanie ma tylko dwa możliwe wyniki. Dlatego,

${\ Displaystyle 2 ^ {f (n)} \ geq n!}$ lub równoważnie ${\ Displaystyle f (n) \ geq \ log _ {2} (n!).}$

Patrząc ${\ Displaystyle n! = n (n-1) \ cdots 1}$$czynniki$ _ , otrzymujemy

${\ 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. Bardziej precyzyjną granicę można podać za pomocą przybliżenia Stirlinga . Górna granica tej samej postaci, z tym samym członem wiodącym, co granica uzyskana z przybliżenia Stirlinga, wynika z istnienia algorytmów, które osiągają tę granicę w najgorszym przypadku, jak sortowanie przez scalanie .

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

Określenie dokładnej liczby porównań potrzebnych do posortowania danej liczby wpisów jest trudnym obliczeniowo problemem nawet dla małych n i nie jest znany żaden prosty wzór na rozwiązanie. Niektóre z kilku konkretnych wartości, które zostały obliczone, można znaleźć w 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 , oraz
• wejście jest losową permutacją, wybraną jednostajnie 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 ₂ ( n !) .

Najłatwiej można to zaobserwować, posługując się pojęciami z teorii informacji . Entropia Shannona takiej losowej permutacji wynosi log ₂ ( n !) bitów. Ponieważ porównanie może dać tylko dwa wyniki, maksymalna ilość dostarczanych informacji wynosi 1 bit. Dlatego po k porównaniach pozostała entropia permutacji, biorąc pod uwagę wyniki tych porównań, wynosi średnio co najmniej log ₂ ( n !) − k bitów. Aby przeprowadzić sortowanie, potrzebne są pełne informacje, więc pozostała entropia musi wynosić 0. Wynika z tego, że k musi wynosić średnio co najmniej log ₂ ( n !) .

Dolna granica wyprowadzona z teorii informacji jest określana jako „dolna granica teorii informacji”. Dolna granica teorii 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 dolna granica wyboru w teorii informacji to ${\ Displaystyle \ lewo \ lceil \ log _ {2} (n) \ prawo \ rceil}$ podczas gdy ${\ Displaystyle n- 1}$ porównania są potrzebne w kontradyktoryjnym argumencie. Wzajemne oddziaływanie między dolną granicą 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ę przeciętny przypadek.

Aby odkryć, co dzieje się podczas analizy przeciętnego przypadku, kluczem jest to, do czego odnosi się „średnia”? Średnio ponad co? Przy pewnej znajomości teorii informacji dolna granica teorii informacji jest uśredniana w zbiorze wszystkich permutacji jako całości. Ale wszelkie algorytmy komputerowe (według tego, co się obecnie uważa) muszą traktować każdą permutację jako indywidualną instancję problemu. Stąd średnia dolna granica, której szukamy, jest uśredniona dla wszystkich indywidualnych przypadków.

Aby wyszukać dolną granicę dotyczącą nieosiągalności komputerów, przyjmujemy model drzewa decyzyjnego . Sformułujmy trochę, jaki jest nasz cel. W modelu drzewa decyzyjnego dolna granica, którą należy pokazać, jest dolną granicą średniej długości ścieżek od korzeni do liści ${\ displaystyle n!}$ -liściaste drzewo binarne (w którym każdy liść odpowiada permutacji). Można by z przekonaniem 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 ${\ displaystyle n!}$ liści, średnia długość ścieżek od korzeni do liści jest podana przez

${\ 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 teorii informacji dla przeciętnego przypadku wynosi około 2,58, podczas gdy średnia dolna granica wyznaczona za pomocą modelu drzewa decyzyjnego wynosi 8/3, czyli około 2,67.

W przypadku, gdy wiele elementów może mieć ten sam klucz, nie ma oczywistej statystycznej interpretacji terminu „przypadek przeciętny”, więc nie można zastosować powyższego argumentu bez przyjęcia określonych założeń dotyczących rozkładu kluczy.

n log n maksymalna liczba porównań dla wielkości tablicy w formacie 2^k

Może łatwo obliczyć dla prawdziwego algorytmu łączenia posortowanej listy (tablica to posortowane n-bloki o rozmiarze 1, łączenie do 1-1 do 2, łączenie 2-2 do 4 ...).

(1) = = = = = = = = (2) = = = = // maks. 1 porównuje (rozmiar1+rozmiar2-1), powtórzenia 4x w celu połączenia 8 tablic o rozmiarze 1 i 1 === === == = === (3) = = // maks. 7 porównań, 2x powtórzeń, aby połączyć 4 tablice o rozmiarze 2 i 2 === === ===== ===== ======= = ====== (4) // max 15 porównuje, 1x powtarza, aby połączyć 2 tablice o rozmiarze 4 i 4 Ekstrakcja formuły: n = 256 = 2^8 (rozmiar tablicy w formacie 2^k, dla uproszczenia) On = (n-1) + 2(n/2-1) + 4(n/4-1) + 8(n/8-1) + 16(n/16-1) + 32(n/32-1) + 64(n/64-1) + 128(n/128-1) Zał. = (n-1) + (n-2) + (n-4) + (n-8) + (n-16) + (n-32) + (n-64) + (n-128) Wł. = n+n+n+n+n+n+n+n - (1+2+4+8+16+32+64+ 128) | 1+2+4... = wzór na ciąg geometryczny Sn = a1 * (q^i - 1) / (n - 1), n ​​to liczba elementów, a1 to pierwszy element On = 8*n - 1 * ( 2^8 - 1) / (2 - 1) On = 8*n - (2^8 - 1) | 2^8 = n Wł. = 8*n - (n - 1) Wł. = (8-1)*n + 1 | 8 = ln(n)/ln(2) = ln(256)/ln(2) On = (ln(n)/ln(2) - 1) * n + 1 Przykład: n = 2^4 = 16, On ~= 3*n n = 2^8 = 256, On ~= 7*n n = 2^10 = 1,024, On ~= 9*n n = 2^20 = 1,048,576, On ~= 19*n

Sortowanie wstępnie posortowanej listy

Główny artykuł: Sortowanie adaptacyjne

Jeśli lista jest już bliska posortowania, według pewnej miary posortowania, liczba porównań wymaganych do jej posortowania może być mniejsza. Sortowanie adaptacyjne wykorzystuje to „wstępne posortowanie” i działa szybciej na prawie posortowanych danych wejściowych, $często$ . Przykładem jest adaptacyjne sortowanie sterty , algorytm sortowania oparty na drzewach kartezjańskich . $wymaga$ czasu $,$ gdzie $_$ _ _ $razy$ sekwencja przeskakuje z dołu $do$ lub .

Notatki

•   Donalda Knuta . Sztuka programowania komputerowego , tom 3: Sortowanie i wyszukiwanie , wydanie drugie. Addison-Wesley, 1997. ISBN 0-201-89685-0 . Sekcja 5.3.1: Sortowanie z minimalnym porównaniem, s. 180–197.