quick sort c with examples
Szybkie sortowanie w C ++ z ilustracjami.
Quicksort to szeroko stosowany algorytm sortowania, który wybiera określony element zwany „pivot” i dzieli tablicę lub listę do posortowania na dwie części w oparciu o ten przestawienie s0, że elementy mniejsze niż pivot znajdują się po lewej stronie listy i elementy większe niż oś obrotu znajdują się po prawej stronie listy.
W ten sposób lista jest podzielona na dwie podlisty. Podlisty mogą nie być potrzebne dla tego samego rozmiaru. Następnie Quicksort wywołuje się rekurencyjnie, aby posortować te dwie podlisty.
=> Sprawdź idealny przewodnik szkoleniowy C ++ tutaj.
Czego się nauczysz:
- Wprowadzenie
- Algorytm ogólny
- Pseudokod do szybkiego sortowania
- Ilustracja
- Przykład w C ++
- Przykład Java
- Analiza złożoności algorytmu szybkiego sortowania
- 3-drożny Quicksort
- Randomized Quicksort
- Szybkie sortowanie a sortowanie przez scalanie
- Wniosek
- rekomendowane lektury
Wprowadzenie
Quicksort działa wydajnie i szybciej, nawet w przypadku większych tablic lub list.
W tym samouczku dowiemy się więcej o działaniu funkcji Quicksort wraz z kilkoma przykładami programowania algorytmu quicksort.
Jako wartość obrotu możemy wybrać pierwszą, ostatnią lub środkową wartość lub dowolną wartość losową. Ogólna idea polega na tym, że ostatecznie wartość obrotu jest umieszczana we właściwej pozycji w tablicy, przesuwając inne elementy w tablicy w lewo lub w prawo.
Algorytm ogólny
Ogólny algorytm Quicksort jest podany poniżej.
quicksort(A, low, high) begin Declare array A(N) to be sorted low = 1st element; high = last element; pivot if(low Przyjrzyjmy się teraz pseudokodowi dla techniki Quicksort.
Pseudokod do szybkiego sortowania
//pseudocode for quick sort main algorithm procedure quickSort(arr(), low, high) arr = list to be sorted low – first element of array high – last element of array begin if (low Działanie algorytmu partycjonowania opisano poniżej na przykładzie.
Na tej ilustracji bierzemy ostatni element jako oś. Widzimy, że tablica jest sukcesywnie dzielona wokół elementu pivot, aż otrzymamy pojedynczy element w tablicy.
Teraz przedstawiamy poniżej ilustrację Quicksort, aby lepiej zrozumieć koncepcję.
Ilustracja
Zobaczmy ilustrację algorytmu szybkiego sortowania. Rozważ następującą tablicę z ostatnim elementem jako przestawną. Ponadto pierwszy element jest oznaczony jako niski, a ostatni element jest wysoki.
jak utworzyć podwójnie linkowaną listę java
Na ilustracji widać, że przesuwamy wskaźniki w górę i w dół na obu końcach tablicy. Ilekroć dołek wskazuje element większy niż pivot, a górny wskazuje element mniejszy niż pivot, wówczas zamieniamy pozycje tych elementów i przesuwamy niskie i wysokie wskaźniki w odpowiednich kierunkach.
Dzieje się tak, dopóki niskie i wysokie wskaźniki nie przecinają się. Po ich skrzyżowaniu element obrotowy jest umieszczany w odpowiednim miejscu, a tablica jest dzielona na dwie części. Następnie obie te pod-tablice są sortowane niezależnie przy użyciu rekursywnego sortowania quicksort.
Przykład w C ++
Poniżej podano implementację algorytmu Quicksort w C ++.
#include using namespace std; // Swap two elements - Utility function void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } // partition the array using last element as pivot int partition (int arr(), int low, int high) { int pivot = arr(high); // pivot int i = (low - 1); for (int j = low; j <= high- 1; j++) { //if current element is smaller than pivot, increment the low element //swap elements at i and j if (arr(j) <= pivot) { i++; // increment index of smaller element swap(&arr(i), &arr(j)); } } swap(&arr(i + 1), &arr(high)); return (i + 1); } //quicksort algorithm void quickSort(int arr(), int low, int high) { if (low < high) { //partition the array int pivot = partition(arr, low, high); //sort the sub arrays independently quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); } } void displayArray(int arr(), int size) { int i; for (i=0; i < size; i++) cout< Wynik:
Tablica wejściowa
12 23 3 43 51 35 19 45
Tablica posortowana za pomocą quicksort
3 12 19 23 35 43 45 51
Tutaj mamy kilka procedur, które są używane do partycjonowania tablicy i rekurencyjnego wywoływania quicksort w celu sortowania partycji, podstawowych funkcji quicksort i funkcji narzędziowych do wyświetlania zawartości tablicy i odpowiedniej zamiany dwóch elementów.
Najpierw wywołujemy funkcję quicksort z tablicą wejściową. Wewnątrz funkcji quicksort nazywamy funkcję partycji. W funkcji partycji używamy ostatniego elementu jako elementu przestawnego tablicy. Po podjęciu decyzji o przestawieniu tablica jest dzielona na dwie części, a następnie wywoływana jest funkcja quicksort w celu niezależnego sortowania obu tablic podrzędnych.
Po powrocie funkcji quicksort tablica jest sortowana w taki sposób, że element pivot znajduje się w prawidłowym położeniu, a elementy mniejsze niż pivot znajdują się po lewej stronie obrotu, a elementy większe niż pivot znajdują się po prawej stronie pivot.
Następnie zaimplementujemy algorytm quicksort w Javie.
Przykład Java
// Quicksort implementation in Java class QuickSort { //partition the array with last element as pivot int partition(int arr(), int low, int high) { int pivot = arr(high); int i = (low-1); // index of smaller element for (int j=low; j Wynik:
Tablica wejściowa
12 23 3 43 51 35 19 45
Tablica po sortowaniu za pomocą quicksort
3 12 19 23 35 43 45 51
W implementacji Java również użyliśmy tej samej logiki, której używaliśmy w implementacji C ++. Użyliśmy ostatniego elementu w tablicy, ponieważ przestawienie i szybkie sortowanie są wykonywane na tablicy w celu umieszczenia elementu przestawnego we właściwej pozycji.
Analiza złożoności algorytmu szybkiego sortowania
Czas potrzebny na sortowanie tablicy przez quicksort zależy od tablicy wejściowej i strategii lub metody partycji.
Jeśli k jest liczbą elementów mniejszą niż punkt obrotu, a n jest całkowitą liczbą elementów, to ogólny czas potrzebny do szybkiego sortowania można wyrazić w następujący sposób:
T (n) = T (k) + T (n-k-1) + O (n)
skopiuj DVD na dysk twardy za darmo
Tutaj T (k) i T (n-k-1) to czas potrzebny na wywołania rekurencyjne, a O (n) to czas potrzebny na wywołanie partycjonowania.
Przeanalizujmy szczegółowo tę złożoność czasu dla szybkiego sortowania.
# 1) Najgorszy przypadek : Najgorszy przypadek w technice quicksort występuje głównie wtedy, gdy jako element przestawny wybieramy najniższy lub najwyższy element tablicy. (Na powyższej ilustracji wybraliśmy najwyższy element jako oś). W takiej sytuacji najgorszy przypadek ma miejsce, gdy sortowana tablica jest już posortowana w kolejności rosnącej lub malejącej.
Stąd powyższe wyrażenie na całkowity czas trwania zmian jako:
T (n) = T (0) + T (n-1) + O (n) to rozwiązuje Nadwa)
# 2) Najlepszy przypadek: Najlepszy przypadek szybkiego sortowania występuje zawsze, gdy wybrany element przestawny znajduje się w środku tablicy.
Zatem powtarzalność dla najlepszego przypadku jest następująca:
tablice i funkcje c ++
T (n) = 2 T (n / 2) + O (n) = O (nlogn)
# 3) Średni przypadek: Aby przeanalizować średni przypadek szybkiego sortowania, powinniśmy rozważyć wszystkie permutacje tablicy, a następnie obliczyć czas potrzebny na każdą z tych permutacji. W skrócie, średni czas szybkiego sortowania również wynosi O (nlogn).
Poniżej podano różne zawiłości techniki Quicksort:
W najgorszym przypadku złożoność czasowa O (nr 2) stabilność Niestabilne, ponieważ dwa elementy o tych samych wartościach nie zostaną umieszczone w tej samej kolejności. Stabilne - dwa elementy o tych samych wartościach pojawią się w tej samej kolejności w posortowanym wyniku. Złożoność czasu w najlepszym przypadku O (n * log n) Średnia złożoność czasowa O (n * log n) Złożoność przestrzeni O (n * log n)
Możemy zaimplementować quicksort na wiele różnych sposobów, po prostu zmieniając wybór elementu pivot (środkowy, pierwszy lub ostatni), jednak najgorszy przypadek rzadko występuje w przypadku szybkiego sortowania.
3-drożny Quicksort
W oryginalnej technice szybkiego sortowania zwykle wybieramy element przestawny, a następnie dzielimy tablicę na pod-tablice wokół tego obrotu, tak że jedna podtablica składa się z elementów mniejszych niż pivot, a druga składa się z elementów większych niż pivot.
Ale co, jeśli wybierzemy element przestawny i w tablicy jest więcej niż jeden element, który jest równy pivot?
Na przykład, rozważ następującą tablicę {5,76,23,65,4,4,5,4,1,1,2,2,2,2}. Jeśli wykonamy proste szybkie sortowanie tej tablicy i wybierzemy 4 jako element przestawny, naprawimy tylko jedno wystąpienie elementu 4, a reszta zostanie podzielona na partycje wraz z innymi elementami.
Zamiast tego, jeśli użyjemy 3-drożnego szybkiego sortowania, podzielimy tablicę (l… r) na trzy pod-tablice w następujący sposób:
- Array (l… i) - w tym przypadku i jest przestawnym, a ta tablica zawiera elementy mniejsze niż przestaw.
- Array (i + 1… j-1) - zawiera elementy, które są równe osi.
- Tablica (j… r) - zawiera elementy większe niż oś obrotu.
Tak więc 3-drożne szybkie sortowanie może być używane, gdy mamy więcej niż jeden nadmiarowy element w tablicy.
Randomized Quicksort
Technika szybkiego sortowania nazywana jest techniką losowego szybkiego sortowania, gdy używamy liczb losowych do wybierania elementu obrotowego. W losowym sortowaniu szybkim nazywa się to „centralnym przestawieniem” i dzieli tablicę w taki sposób, aby każda strona miała co najmniej ¼ elementów.
Pseudokod losowego szybkiego sortowania podano poniżej:
// Sorts an array arr(low..high) using randomized quick sort randomQuickSort(array(), low, high) array – array to be sorted low – lowest element in array high – highest element in array begin 1. If low >= high, then EXIT. //select central pivot 2. While pivot 'pi' is not a Central Pivot. (i) Choose uniformly at random a number from (low..high). Let pi be the randomly picked number. (ii) Count elements in array(low..high) that are smaller than array(pi). Let this count be a_low. (iii) Count elements in array(low..high) that are greater than array(pi). Let this count be a_high. (iv) Let n = (high-low+1). If a_low >= n/4 and a_high >= n/4, then pi is a central pivot. //partition the array 3. Partition array(low..high) around the pivot pi. 4. // sort first half randomQuickSort(array, low, a_low-1) 5. // sort second half randomQuickSort(array, high-a_high+1, high) end procedureW powyższym kodzie na „randomQuickSort”, w kroku 2 wybieramy środkową oś. W kroku 2 prawdopodobieństwo, że wybrany element jest osią centralną, wynosi ½. W związku z tym oczekuje się, że pętla w kroku 2 uruchomi się 2 razy. Zatem złożoność czasowa dla kroku 2 w losowym sortowaniu szybkim wynosi O (n).
Używanie pętli do wybierania środkowego obrotu nie jest idealnym sposobem implementacji losowego szybkiego sortowania. Zamiast tego możemy losowo wybrać element i nazwać go centralnym przestawieniem lub przetasować elementy tablicy. Oczekiwana złożoność czasowa dla najgorszego przypadku dla algorytmu randomizowanego szybkiego sortowania to O (nlogn).
Szybkie sortowanie a sortowanie przez scalanie
W tej sekcji omówimy główne różnice między sortowaniem szybkim i scalaniem.
Parametr porównawczy Szybkie sortowanie Sortuj przez scalanie partycjonowanie Macierz jest podzielona wokół elementu obrotowego i niekoniecznie zawsze składa się z dwóch połówek. Można go podzielić w dowolnym stosunku. Macierz jest podzielona na dwie połowy (n / 2). Najgorszy przypadek złożoności O (n 2) - w najgorszym przypadku potrzeba wielu porównań. O (nlogn) - to samo, co przeciętny przypadek Wykorzystanie zbiorów danych Nie działa dobrze z większymi zestawami danych. Działa dobrze ze wszystkimi zbiorami danych, niezależnie od rozmiaru. Dodatkowa przestrzeń Na miejscu - nie wymaga dodatkowej przestrzeni. Nie na miejscu - wymaga dodatkowej przestrzeni do przechowywania macierzy pomocniczej. Metoda sortowania Wewnętrzne - dane są sortowane w pamięci głównej. Zewnętrzna - wykorzystuje pamięć zewnętrzną do przechowywania tablic danych. Wydajność Szybszy i wydajny w przypadku małych list. Szybkie i wydajne w przypadku większych list. Tablice / połączone listy Bardziej preferowane dla tablic. Działa dobrze w przypadku połączonych list.
Wniosek
Jak sama nazwa wskazuje, quicksort to algorytm, który sortuje listę szybciej niż jakikolwiek inny algorytm sortowania. Podobnie jak sortowanie przez scalanie, sortowanie szybkie również przyjmuje strategię dziel i rządź.
Jak już widzieliśmy, za pomocą szybkiego sortowania dzielimy listę na pod-tablice za pomocą elementu pivot. Następnie te tablice podrzędne są sortowane niezależnie. Na końcu algorytmu cała tablica jest całkowicie posortowana.
Quicksort jest szybszy i skuteczny w sortowaniu struktur danych. Quicksort to popularny algorytm sortowania, a czasami jest nawet preferowany w stosunku do algorytmu sortowania przez scalanie.
W naszym następnym samouczku omówimy szczegółowo sortowanie powłoki.
=> Obejrzyj serię prostych szkoleń C ++ tutaj.
rekomendowane lektury
- Metoda MongoDB Sort () z przykładami
- Polecenie sortowania Unix ze składnią, opcjami i przykładami
- Sortuj w C ++ z przykładami
- Sortuj na stosie w C ++ z przykładami
- Sortowanie powłoki w C ++ z przykładami
- Wybór sortowania w C ++ z przykładami
- Sortuj bąbelkowe w C ++ z przykładami
- Sortuj przez wstawianie w C ++ z przykładami
