Algoritam brzog sortiranja

U ovom vodiču naučit ćete kako funkcionira brzi sortiranje. Također ćete naći radne primjere brzog sortiranja u C, C ++ Python i Java.

Quicksort je algoritam zasnovan na pristupu podijeli i vladaj u kojem je niz podijeljen na podnizove i ti se podrelovi rekurzivno pozivaju za sortiranje elemenata.

Kako QuickSort djeluje?

  1. Iz polja se bira pivot element. Kao stožerni element možete odabrati bilo koji element iz niza.
    Ovdje smo uzeli krajnji desni (tj. Posljednji element) niza kao pivot element. Odaberite pivot element
  2. Elementi manji od pivot elementa stavljaju se s lijeve strane, a elementi veći od pivot elementa s desne strane. Stavite sve manje elemente s lijeve, a veće s desne strane zakretnog elementa
    Gornji raspored postiže se sljedećim koracima.
    1. Pokazivač je fiksiran na pivot elementu. Pivot element uspoređuje se s elementima koji počinju od prvog indeksa. Ako se dosegne element veći od pivot elementa, postavlja se drugi pokazivač za taj element.
    2. Sada se pivot element uspoređuje s ostalim elementima (treći pokazivač). Ako se postigne element manji od stožernog elementa, manji se element zamijeni većim već pronađenim elementom. Usporedba stožernog elementa s ostalim elementima
    3. Proces traje dok se ne postigne drugi posljednji element.
      Napokon, element zakretanja zamjenjuje se drugim pokazivačem. Zamijenite pivot element s drugim pokazivačem
    4. Sada su lijeva i desna poddio ovog pivot elementa za daljnju obradu u sljedećim koracima.
  3. Elementi zakretanja ponovno su odabrani za lijevi i desni poddijel odvojeno. Unutar ovih poddijelova, zakretni elementi postavljeni su u pravi položaj. Zatim se ponavlja korak 2. Odaberite pivot element iz svake polovice i stavite na točno mjesto pomoću rekurzije
  4. Poddijelovi su ponovno podijeljeni na manje dijelove sve dok svaki poddio nije oblikovan od jednog elementa.
  5. U ovom je trenutku niz već sortiran.

Quicksort za sortiranje poddijelova koristi rekurziju.

Na temelju pristupa podijeli i osvoji, algoritam brzog sortiranja može se objasniti kao:

  • Podijeli
    Niz je podijeljen na poddjelove koji uzimaju pivot kao točku particioniranja. Elementi manji od pivota smješteni su lijevo od pivota, a elementi veći od pivota desno.
  • Osvoji
    Lijeva i desna poddjela ponovno se podijele pomoću odabira elemenata zakretanja za njih. To se može postići rekurzivnim prosljeđivanjem poddjelova u algoritam.
  • Kombiniraj
    Ovaj korak ne igra značajnu ulogu u brzom sortiranju. Niz je već sortiran na kraju koraka osvajanja.

Rad brzog sortiranja možete razumjeti uz pomoć ilustracija u nastavku.

Sortiranje elemenata na lijevoj strani pivota pomoću rekurzije Sortiranje elemenata na desnoj strani pivota pomoću rekurzije

Algoritam brzog sortiranja

 quickSort (array, leftmostIndex, rightmostIndex) ako je (leftmostIndex <rightmostIndex) pivotIndex <- particija (array, leftmostIndex, rightmostIndex) quickSort (array, leftmostIndex, pivotIndex) quickSort (array, pivotIndex, leftmostmostIndex, ArmostmostIndex, arterija, pivotIndex, arterija najkraćeg desnog indeksa, most ) postavi rightmostIndex kao pivotIndex storeIndex <- leftmostIndex - 1 za i <- leftmostIndex + 1 na rightmostIndex if element (i) <pivotElement swap element (i) i element (storeIndex) storeIndex ++ swap pivotElement i element (storeIndex + 1) return storeIndex + 1

Primjeri Pythona, Java i C / C ++

Python Java C 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); )

Složenost brzog sortiranja

Složenost vremena

  • Najgora složenost slučaja (Big-O) : Događa se kada je odabrani element zakretanja ili najveći ili najmanji element. Ovo stanje dovodi do slučaja u kojem se pivot element nalazi na krajnjem kraju razvrstanog niza. Jedan je pod-niz uvijek prazan, a drugi pod-niz sadrži elemente. Dakle, brzi sortiranje poziva se samo na ovom podnizu. Međutim, algoritam brzog sortiranja ima bolje performanse za raspršene pivote.O(n2)
    n - 1

  • Složenost najboljeg slučaja (Big-omega) : O(n*log n)
    Događa se kada je stožerni element uvijek srednji element ili blizu srednjeg elementa.
  • Prosječna složenost slučaja (Big-theta) : O(n*log n)
    Događa se kada se ne pojave gore navedeni uvjeti.

Složenost prostora

Složenost prostora za brzi sorti je O(log n).

Quicksort aplikacije

Quicksort se provodi kada

  • programski jezik je dobar za rekurziju
  • složenost vremena je bitna
  • složenost prostora je bitna

Zanimljivi članci...