Obie techniki sortowania, sortowanie szybkie i sortowanie są oparte na metodzie dziel i rządź, w której zestaw elementów jest rozdzielany, a następnie łączony po przegrupowaniu. Sortowanie szybkie zwykle wymaga więcej porównań niż sortowanie scalone do sortowania dużego zestawu elementów.
Wykres porównania
| Podstawa do porównania | Szybkie sortowanie | Połącz sortowanie |
|---|---|---|
| Partycjonowanie elementów w tablicy | Podział listy elementów niekoniecznie dzieli się na połowę. | Tablica jest zawsze podzielona na pół (n / 2). |
| Najgorsza złożoność sprawy | O (n2) | O (n log n) |
| Działa dobrze | Mniejszy układ | Działa dobrze w każdym rodzaju tablicy. |
| Prędkość | Szybszy niż inne algorytmy sortowania dla małego zestawu danych. | Stała prędkość we wszystkich typach zestawów danych. |
| Dodatkowe zapotrzebowanie na miejsce do przechowywania | Mniej | Więcej |
| Wydajność | Nieskuteczne 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 szybkie dla krótkich tablic. Zbiór elementów jest wielokrotnie podzielony na części, dopóki nie da się go dalej podzielić. Sortowanie szybkie jest również znane jako sortowanie wymiany partycji . Wykorzystuje kluczowy element (znany jako przestawny) do partycjonowania elementów. Jedna partycja zawiera te elementy, które są mniejsze niż element klucza. Kolejna partycja zawiera te elementy, które są większe niż klucz. Elementy są sortowane rekurencyjnie.
Załóżmy, że A jest tablicą A [1], A [2], A [3], ...... .., A [n] z n liczby, które należy posortować. Algorytm szybkiego sortowania składa się z następujących kroków.
- Pierwszy element lub dowolny element losowy wybrany jako klucz przyjmuje klucz = A (1).
- Wskaźnik "low" jest umieszczony na drugim, a wskaźnik "up" jest umieszczony na ostatnim elemencie tablicy, tzn. Low = 2 and up = n;
- Konsekwentnie, zwiększaj "niski" wskaźnik o jedną pozycję do (A [niski]> klucz).
- Ciągle zmniejszaj wskaźnik "w górę" o jedną pozycję aż do (A [w górę] <= klucz).
- Jeśli wartość jest większa niż mała zamiana A [niska] z A [w górę].
- Powtórz kroki 3, 4 i 5, aż warunek z punktu 5 nie powiedzie się (tj. W górę <= niski), a następnie zamień A [w górę] za pomocą klawisza.
- Jeżeli elementy po lewej stronie klucza są mniejsze od klucza, a elementy po prawej stronie klucza są większe od klucza, to tablica jest podzielona na dwie pod-tablice.
- Powyższa procedura jest wielokrotnie stosowana do podmarek, dopóki cała tablica nie zostanie posortowana.
Zalety i wady
Ma dobre średnie zachowanie w przypadku. Złożoność czasu szybkiego sortowania jest dobra, ponieważ jest szybsza niż algorytmy takie jak sortowanie bąbelkowe, sortowanie wstawiania i sortowanie sortowania. Jest jednak złożony i bardzo rekursywny, dlatego nie nadaje się do dużych tablic.
Definicja sortowania scalonego
Scal sort to zewnętrzny algorytm, który również opiera się na strategii dziel i rządź. Elementy są dzielone na pod-tablice (n / 2) raz po raz, aż pozostanie tylko jeden element, co znacznie zmniejsza czas sortowania. Wykorzystuje dodatkową pamięć do przechowywania macierzy pomocniczej. Sortowanie scalone wykorzystuje trzy tablice, w których dwa służą 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, subarrays są scalane, aby n rozmiar elementu tablicy. Lista zawsze dzieliła się na połowę (n / 2), podobnie jak w przypadku szybkiego sortowania.
Niech A będzie tablicą liczby n elementów do posortowania A [1], A [2], ........., A [n]. Sortowanie scalania następuje po podanych krokach.
- Podziel tablicę A na około 2 uporządkowaną pod-tablicę przez 2, co oznacza, że elementy w (A [1], A [2]), (A [3], A [4]), (A [ Podprasze k], A [k + 1]), (A [n-1], A [n]) muszą być posortowane.
- Połączyć każdą parę par, aby uzyskać listę posortowanych podmacierów o rozmiarze 4; elementy w podrozmaerkach są również uporządkowane w kolejności (A [1], A [2], A [3], A [4]), ......, (A [k-1], A [k], A [k + 1], A [k + 2]), ......., (A [n-3], A [n-2], A [n-1], A [n]).
- Krok 2 jest powtarzany wielokrotnie, dopóki nie ma tylko jednej posortowanej tablicy o rozmiarze n.
Zalety i wady
Algorytm sortowania scalonego działa dokładnie w ten sam i precyzyjny sposób, niezależnie od liczby elementów biorących udział w sortowaniu. Działa dobrze nawet z dużym zestawem danych. Jednak zużywa on większą część pamięci.
Kluczowe różnice między sortowaniem szybkim a sortowaniem
- W sortowaniu scalania tablica musi zostać podzielona na dwie połówki (tj. N / 2). W przeciwieństwie do tego, w szybkim sortowaniu, nie ma przymusu dzielenia listy na równe elementy.
- Najgorszym przypadku złożoności szybkiego sortowania jest O (n2), ponieważ wymaga znacznie więcej porównań w najgorszym stanie. Natomiast sortowanie scalone ma ten sam najgorszy przypadek i średnią złożoność, czyli O (n log n).
- Sortowanie scalone może działać dobrze na każdym typie zestawów danych, niezależnie od tego, czy jest duży, czy mały. Wręcz przeciwnie, sortowanie szybkie nie działa dobrze w przypadku dużych zestawów danych.
- Szybkie sortowanie jest szybsze niż sortowanie scalone w niektórych przypadkach, na przykład w przypadku małych zestawów danych.
- Scal sortowanie wymaga dodatkowego miejsca w pamięci do przechowywania tablic pomocniczych. Z drugiej strony sortowanie szybkie nie wymaga dużo miejsca na dodatkowe miejsce.
- Sortowanie scalania jest bardziej wydajne niż sortowanie szybkie.
- Sortowanie szybkie to wewnętrzna metoda sortowania, w której dane, które mają być sortowane, są korygowane w czasie w pamięci głównej. Odwrotnie, sortowanie scalone jest zewnętrzną metodą sortowania, w której dane, które mają być sortowane, nie mogą być umieszczone w pamięci w tym samym czasie, a niektóre muszą być przechowywane w pamięci pomocniczej.
Wniosek
Sortowanie szybkie jest szybsze, ale w niektórych sytuacjach jest nieefektywne, a także wykonuje wiele porównań w porównaniu do sortowania scalonego. Chociaż sortowanie scalone wymaga mniejszego porównania, potrzebuje dodatkowej przestrzeni pamięci 0 (n) do przechowywania dodatkowej tablicy, podczas gdy szybkie sortowanie wymaga przestrzeni O (log n).
