Algorytm QuickSort

W tym samouczku dowiesz się, jak działa quicksort. Znajdziesz również działające przykłady szybkiego sortowania w C, C ++ Pythonie i Javie.

Quicksort to algorytm oparty na podejściu dziel i zwyciężaj, w którym tablica jest dzielona na podtablice, a te tablice są rekurencyjnie wywoływane w celu sortowania elementów.

Jak działa QuickSort?

  1. Z tablicy wybierany jest element przestawny. Możesz wybrać dowolny element z tablicy jako element przestawny.
    Tutaj, jako element przestawny, wzięliśmy skrajny prawy (tj. Ostatni element) tablicy. Wybierz element obrotowy
  2. Elementy mniejsze od elementu obrotowego są umieszczane po lewej stronie, a elementy większe od elementu obrotowego po prawej stronie. Wszystkie mniejsze elementy należy umieścić po lewej stronie, a większe po prawej stronie elementu obrotowego
    . Powyższe ułożenie uzyskuje się wykonując następujące kroki.
    1. Wskaźnik jest zamocowany na elemencie obrotowym. Element pivot jest porównywany z elementami zaczynającymi się od pierwszego indeksu. Jeśli zostanie osiągnięty element większy niż element przestawny, ustawiany jest drugi wskaźnik dla tego elementu.
    2. Teraz element pivot jest porównywany z innymi elementami (trzeci wskaźnik). Jeśli zostanie osiągnięty element mniejszy niż element obrotowy, mniejszy element jest zamieniany na większy, znaleziony wcześniej. Porównanie elementu obrotowego z innymi elementami
    3. Proces trwa aż do osiągnięcia przedostatniego elementu.
      Na koniec element pivot jest zamieniany drugim wskaźnikiem. Zamień element obrotowy na drugi wskaźnik
    4. Teraz lewa i prawa część podrzędna tego elementu obrotowego są brane do dalszego przetwarzania w poniższych krokach.
  3. Elementy obrotowe są ponownie wybierane oddzielnie dla lewej i prawej części podrzędnej. W tych częściach podrzędnych elementy obrotowe są umieszczone we właściwych miejscach. Następnie powtarza się krok 2. Wybierz element obrotowy w każdej połowie i umieść go w odpowiednim miejscu za pomocą rekursji
  4. Podczęści są ponownie podzielone na mniejsze części, aż każda podczęść zostanie utworzona z pojedynczego elementu.
  5. W tym momencie tablica jest już posortowana.

Quicksort używa rekurencji do sortowania części podrzędnych.

Bazując na podejściu Dziel i rządź, algorytm szybkiego sortowania można wyjaśnić następująco:

  • Dzielenie
    Tablica jest podzielona na części podrzędne, przyjmując pivot jako punkt podziału. Elementy mniejsze niż czop są umieszczane po lewej stronie osi, a elementy większe niż czop są umieszczane po prawej stronie.
  • Podbij
    Lewa i prawa część podrzędna są ponownie podzielone na partycje za pomocą elementu, wybierając dla nich elementy przestawne. Można to osiągnąć poprzez rekurencyjne przekazywanie części podrzędnych do algorytmu.
  • Połącz
    Ten krok nie odgrywa znaczącej roli w przypadku szybkiego sortowania. Tablica jest już posortowana na końcu kroku zdobywania.

Możesz zrozumieć działanie quicksort za pomocą poniższych ilustracji.

Sortowanie elementów po lewej stronie przestawienia za pomocą rekursji Sortowanie elementów po prawej stronie przestawienia przy użyciu rekursji

Algorytm szybkiego sortowania

 quickSort (array, leftmostIndex, rightmostIndex) if (leftmostIndex <rightmostIndex) pivotIndex <- partition (array, leftmostIndex, rightmostIndex) quickSort (array, leftmostIndex, pivotIndex) quickSort (array, pivotIndex + 1, rightexmostIndex, rightmostIndex) quickSort (array, leftmostIndex, pivotIndex) quickSort (array, pivotIndex + 1, rightexmostIndex, arrayIndex) ) ustaw rightmostIndex jako pivotIndex storeIndex <- leftmostIndex - 1 for i <- leftmostIndex + 1 to rightmostIndex if element (i) <pivotElement swap element (i) i element (storeIndex) storeIndex ++ swap pivotElement and element (storeIndex + 1) + return storeIndex 1

Przykłady w Pythonie, Javie i C / C ++

Python Java C + 
 # Quick sort in Python # Function to partition the array on the basis of pivot element def partition(array, low, high): # Select the pivot element pivot = array(high) i = low - 1 # Put the elements smaller than pivot on the left and greater #than pivot on the right of pivot for j in range(low, high): if array(j) <= pivot: i = i + 1 (array(i), array(j)) = (array(j), array(i)) (array(i + 1), array(high)) = (array(high), array(i + 1)) return i + 1 def quickSort(array, low, high): if low < high: # Select pivot position and put all the elements smaller # than pivot on left and greater than pivot on right pi = partition(array, low, high) # Sort the elements on the left of pivot quickSort(array, low, pi - 1) # Sort the elements on the right of pivot quickSort(array, pi + 1, high) data = (8, 7, 2, 1, 0, 9, 6) size = len(data) quickSort(data, 0, size - 1) print('Sorted Array in Ascending Order:') print(data)
 // Quick sort in Java import java.util.Arrays; class QuickSort ( // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left and // greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; int temp = array(i); array(i) = array(j); array(j) = temp; ) ) int temp = array(i + 1); array(i + 1) = array(high); array(high) = temp; return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Driver code public static void main(String args()) ( int() data = ( 8, 7, 2, 1, 0, 9, 6 ); int size = data.length; QuickSort qs = new QuickSort(); qs.quickSort(data, 0, size - 1); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )
 // Quick sort in C #include // Function to swap position of elements void swap(int *a, int *b) ( int t = *a; *a = *b; *b = t; ) // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left // and greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; swap(&array(i), &array(j)); ) ) swap(&array(i + 1), &array(high)); return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Function to print eklements of an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int data() = (8, 7, 2, 1, 0, 9, 6); int n = sizeof(data) / sizeof(data(0)); quickSort(data, 0, n - 1); printf("Sorted array in ascending order: "); printArray(data, n); )
 // Quick sort in C++ #include using namespace std; // Function to swap position of elements void swap(int *a, int *b) ( int t = *a; *a = *b; *b = t; ) // Function to print eklements of an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left // and greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; swap(&array(i), &array(j)); ) ) printArray(array, 7); cout << "… "; swap(&array(i + 1), &array(high)); return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Driver code int main() ( int data() = (8, 7, 6, 1, 0, 9, 2); int n = sizeof(data) / sizeof(data(0)); quickSort(data, 0, n - 1); cout << "Sorted array in ascending order: "; printArray(data, n); )

Złożoność szybkiego sortowania

Złożoność czasowa

  • Złożoność najgorszego przypadku (duże-O) : występuje, gdy wybrany element obrotowy jest albo największym, albo najmniejszym elementem. Ten stan prowadzi do przypadku, w którym element obrotowy znajduje się na skrajnym końcu posortowanej tablicy. Jedna tablica podrzędna jest zawsze pusta, a inna tablica podrzędna zawiera elementy. Zatem quicksort jest wywoływany tylko w tej podtablicy. Jednak algorytm szybkiego sortowania ma lepszą wydajność dla rozproszonych osi.O(n2)
    n - 1

  • Złożoność najlepszego przypadku (duża-omega) : O(n*log n)
    Występuje, gdy element obrotu jest zawsze środkowym elementem lub blisko środkowego elementu.
  • Średnia złożoność przypadku (Big-theta) : O(n*log n)
    Występuje, gdy powyższe warunki nie występują.

Złożoność przestrzeni

Złożoność przestrzeni dla szybkiego sortowania wynosi O(log n).

Aplikacje Quicksort

Quicksort jest implementowany, gdy

  • język programowania jest dobry do rekurencji
  • złożoność czasowa ma znaczenie
  • złożoność przestrzeni ma znaczenie

Interesujące artykuły...