Zawartość

• Wykres porównania
• Definicja szybkiego sortowania
• Definicja sortowania korespondencji seryjnej
• Wniosek

Algorytmy szybkiego sortowania i scalania są oparte na algorytmie dzielenia i zdobywania, który działa w podobny sposób. Pierwszą różnicą między sortowaniem szybkim i scalaniem jest to, że w sortowaniu szybkim do sortowania wykorzystywany jest element przestawny. Z drugiej strony, sortowanie scalone nie używa elementu przestawnego do przeprowadzania sortowania.

Obie techniki sortowania, szybkie sortowanie i scalanie są oparte na metodzie dzielenia i podbijania, w której zestaw elementów jest dzielony, a następnie łączony po przegrupowaniu. Szybkie sortowanie zwykle wymaga więcej porównań niż sortowanie scalone w celu posortowania dużego zestawu elementów.

1. 1. Wykres porównania
   2. Definicja
   3. Kluczowe różnice
   4. Wniosek

Wykres porównania

Podstawa do porównania	Szybkie sortowanie	Scal sortuj
Partycjonowanie elementów w tablicy	Podział listy elementów niekoniecznie jest podzielony na pół.	Tablica jest zawsze podzielona na pół (n / 2).
W najgorszym przypadku złożoność	Na2)	O (n log n)
Działa dobrze na	Mniejszy zestaw	Działa dobrze w każdym typie tablicy.
Prędkość	Szybszy niż inne algorytmy sortowania dla małego zestawu danych.	Stała prędkość we wszystkich typach zestawów danych.
Wymagane dodatkowe miejsce do przechowywania	Mniej	Więcej
Wydajność	Nieefektywne w przypadku większych tablic.	Bardziej wydajny.
Metoda sortowania	Wewnętrzny	Zewnętrzny

Definicja szybkiego sortowania

Szybkie sortowanie jest powszechnie stosowanym algorytmem sortowania, ponieważ jest szybki dla krótkich tablic. Zestaw elementów jest wielokrotnie dzielony na części, dopóki nie można go dalej podzielić. Szybkie sortowanie jest również znane jako sortuj podział partycji. Używa kluczowego elementu (znanego jako pivot) do partycjonowania elementów. Jedna partycja zawiera te elementy, które są mniejsze niż kluczowy element. Kolejna partycja zawiera te elementy, które są większe niż element kluczowy. Elementy są sortowane rekurencyjnie.

Załóżmy, że A jest tablicą A, A, A, …… .., A o liczbie n, którą należy posortować. Algorytm szybkiego sortowania składał się z następujących kroków.

1. Pierwszy element lub dowolny losowy element wybrany jako klucz, załóż klucz = A (1).
2. Wskaźnik „niski” jest umieszczony na drugim, a wskaźnik „górny” na ostatnim elemencie tablicy, tj. Niski = 2 i góra = n;
3. Konsekwentnie zwiększaj wskaźnik „niski” o jedną pozycję, aż (klawisz A>).
4. Stale zmniejszaj wskaźnik „góra” o jedną pozycję do (klawisz A <=).
5. Jeśli wzrost jest większy niż niski, zamień A na A.
6. Powtarzaj kroki 3, 4 i 5, aż warunek w kroku 5 nie powiedzie się (tj. W górę <= niski), a następnie zamień A kluczem.
7. Jeśli elementy po lewej stronie klucza są mniejsze niż klucz, a elementy po prawej stronie klucza są większe niż klucz, tablica jest dzielona na dwie pod-tablice.
8. Powyższa procedura jest wielokrotnie stosowana do podrzędnych, aż cała tablica zostanie posortowana.

   

   
   

Zalety i wady

Ma dobre średnie zachowanie w przypadku. Złożoność szybkiego sortowania w czasie wykonywania jest dobra, to znaczy, że jest szybsza niż algorytmy, takie jak sortowanie bąbelkowe, sortowanie wstawiania i sortowanie wyboru. Jest to jednak złożone i bardzo rekurencyjne, dlatego nie nadaje się do dużych tablic.

Definicja sortowania korespondencji seryjnej

Scal sortowanie to zewnętrzny algorytm oparty również na strategii dziel i zwyciężaj. Elementy są dzielone na pod-tablice (n / 2) raz za razem, aż pozostanie tylko jeden element, co znacznie skraca czas sortowania. Wykorzystuje dodatkową pamięć do przechowywania tablicy pomocniczej. Sortowanie scalone wykorzystuje trzy tablice, w których dwie są używane do przechowywania każdej połowy, a trzecia służy do przechowywania końcowej posortowanej listy. Każda tablica jest następnie sortowana rekurencyjnie. W końcu podcienie są łączone, aby uzyskać rozmiar elementu n tablicy. Lista zawsze dzieli się na zaledwie połowę (n / 2) niepodobną do szybkiego sortowania.

Niech A będzie tablicą n liczby elementów do posortowania A, A, ………, A. Sortowanie według scalenia przebiega zgodnie z podanymi krokami.

1. Podziel tablicę A na mniej więcej n / 2 posortowaną pod-tablicę przez 2, co oznacza, że ​​elementy w pod-macierzach (A, A), (A, A), (A, A), (A, A) muszą być posortowane.
2. Połącz każdą parę par, aby uzyskać listę posortowanych podrzędnych rozmiarów 4; elementy w podobszarach również są posortowane, (A, A, A, A), ……, (A, A, A, A), ……., (A, A, A, A).
3. Krok 2 jest powtarzany do momentu, aż będzie tylko jedna posortowana tablica o rozmiarze n.

   

Zalety i wady

Algorytm scalania sortowania działa dokładnie w ten sam i precyzyjny sposób, niezależnie od liczby elementów zaangażowanych w sortowanie. Działa dobrze nawet z dużym zestawem danych. Zużywa jednak większą część pamięci.

1. W trybie scalania tablica musi być podzielona na dwie połowy (tj. N / 2). Przeciwnie, w szybkim sortowaniu, nie ma obowiązku dzielenia listy na równe elementy.
2. Najgorszym przypadkiem złożoności szybkiego sortowania jest O (n²), ponieważ wymaga znacznie więcej porównań w najgorszym stanie. Natomiast sortowanie scalone ma ten sam najgorszy przypadek i średnią złożoność przypadku, to jest O (n log n).
3. Sortowanie po scaleniu może działać dobrze na każdym typie zestawów danych, niezależnie od tego, czy jest duży czy mały. Przeciwnie, szybkie sortowanie nie działa dobrze z dużymi zestawami danych.
4. W niektórych przypadkach, na przykład w przypadku małych zestawów danych, szybkie sortowanie jest szybsze niż sortowanie scalone.
5. Sortowanie po scaleniu wymaga dodatkowej pamięci do przechowywania tablic pomocniczych. Z drugiej strony szybkie sortowanie nie wymaga dużo miejsca na dodatkowe miejsce.
6. Sortowanie scalone jest wydajniejsze niż sortowanie szybkie.
7. Szybkie sortowanie to wewnętrzna metoda sortowania, w której dane, które mają być sortowane, są dostosowywane jednocześnie w głównej pamięci. I odwrotnie, sortowanie scalone jest zewnętrzną metodą sortowania, w której dane, które mają być sortowane, nie mogą być jednocześnie umieszczone w pamięci, a niektóre muszą być przechowywane w pamięci pomocniczej.

Wniosek

Szybkie sortowanie to szybsze przypadki, ale w niektórych sytuacjach jest nieefektywne, a także wykonuje wiele porównań w porównaniu do sortowania po scaleniu. Chociaż sortowanie po scaleniu wymaga mniej porównania, wymaga dodatkowej przestrzeni pamięci 0 (n) do przechowywania dodatkowej tablicy, podczas gdy szybkie sortowanie wymaga przestrzeni O (log n).