Zalecane, 2019

Wybór Redakcji

Różnica między sortowaniem szybkim a sortowaniem

Algorytmy szybkiego sortowania i scalania są oparte na algorytmie dziel i rządź, który działa w dość podobny sposób. Wcześniejsza różnica między sortowaniem szybkim a scalaniem polega na tym, że w szybkim sortowaniu element obrotowy jest używany do sortowania. Z drugiej strony sortowanie scalone nie używa elementu przestawnego do sortowania.

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ównaniaSzybkie sortowaniePołącz sortowanie
Partycjonowanie elementów w tablicyPodział listy elementów niekoniecznie dzieli się na połowę.Tablica jest zawsze podzielona na pół (n / 2).
Najgorsza złożoność sprawyO (n2)O (n log n)
Działa dobrzeMniejszy układDział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 przechowywaniaMniejWięcej
WydajnośćNieskuteczne w przypadku większych tablic.Bardziej wydajny.
Metoda sortowaniaWewnętrznyZewnę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.

  1. Pierwszy element lub dowolny element losowy wybrany jako klucz przyjmuje klucz = A (1).
  2. Wskaźnik "low" jest umieszczony na drugim, a wskaźnik "up" jest umieszczony na ostatnim elemencie tablicy, tzn. Low = 2 and up = n;
  3. Konsekwentnie, zwiększaj "niski" wskaźnik o jedną pozycję do (A [niski]> klucz).
  4. Ciągle zmniejszaj wskaźnik "w górę" o jedną pozycję aż do (A [w górę] <= klucz).
  5. Jeśli wartość jest większa niż mała zamiana A [niska] z A [w górę].
  6. 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.
  7. 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.
  8. 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.

  1. 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.
  2. 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]).
  3. 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

  1. 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.
  2. 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).
  3. 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.
  4. Szybkie sortowanie jest szybsze niż sortowanie scalone w niektórych przypadkach, na przykład w przypadku małych zestawów danych.
  5. 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.
  6. Sortowanie scalania jest bardziej wydajne niż sortowanie szybkie.
  7. 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).

Top