QuickSort-algoritme

Indholdsfortegnelse

Hvordan fungerer QuickSort?
Hurtig sorteringsalgoritme
Python, Java og C / C ++ eksempler
Quicksort-kompleksitet
Quicksort-applikationer

I denne vejledning lærer du, hvordan quicksort fungerer. Du finder også arbejdseksempler på quicksort i C, C ++ Python og Java.

Quicksort er en algoritme baseret på divide and conquer tilgang, hvor arrayet er opdelt i underarrays, og disse underarrays kaldes rekursivt til at sortere elementerne.

Hvordan fungerer QuickSort?

Et pivotelement vælges fra arrayet. Du kan vælge ethvert element fra arrayet som pivotelement.
Her har vi taget den længst til højre (dvs. det sidste element) i arrayet som omdrejningselementet. Vælg et drejelement
Elementerne, der er mindre end pivotelementet, er placeret til venstre og elementerne større end pivotelementet er placeret til højre. Sæt alle de mindre elementer til venstre og større til højre for drejelementet
Ovenstående arrangement opnås ved hjælp af følgende trin.
1. En markør er fastgjort ved drejelementet. Pivotelementet sammenlignes med elementerne, der begynder med det første indeks. Hvis elementet, der er større end pivotelementet, er nået, indstilles en anden markør for det element.
2. Nu sammenlignes omdrejningselementet med de andre elementer (en tredje markør). Hvis et element, der er mindre end pivotelementet, er nået, byttes det mindre element med det større element, der blev fundet tidligere. Sammenligning af drejelement med andre elementer
3. Processen fortsætter, indtil det næstsidste element er nået.
  Endelig byttes pivotelementet ud med den anden markør. Byt drejelement med den anden markør
4. Nu tages venstre og højre del af dette drejelement til yderligere behandling i nedenstående trin.
Pivotelementer vælges igen til venstre og højre underdel separat. Inden for disse underdele er drejelementerne placeret i deres rette position. Derefter gentages trin 2. Vælg drejelement i hver halvdel, og læg det på det rigtige sted ved hjælp af rekursion
Underdelene er igen opdelt i mindre underdele, indtil hver underdel er dannet af et enkelt element.
På dette tidspunkt er arrayet allerede sorteret.

Quicksort bruger rekursion til at sortere underdelene.

På baggrund af Divide and conquer tilgang kan quicksort algoritme forklares som:

Opdel
Arrayet er opdelt i underdele, der tager omdrejningspunktet som skillepunktet. Elementerne, der er mindre end drejetappen, placeres til venstre for drejetappen, og elementerne større end drejetappen placeres til højre.
Erobrer
De venstre og højre underdele er igen opdelt ved hjælp af ved at vælge drejelementer til dem. Dette kan opnås ved rekursivt at overføre delene til algoritmen.
Kombiner
Dette trin spiller ikke en væsentlig rolle i quicksort. Arrayet er allerede sorteret i slutningen af erobringstrinet.

Du kan forstå funktionen af quicksort ved hjælp af nedenstående illustrationer.

Sortering af elementerne til venstre for pivot ved hjælp af rekursion

Sortering af elementerne til højre for pivot ved hjælp af rekursion

Hurtig sorteringsalgoritme

 quickSort (array, leftmostIndex, rightmostIndex) if (leftmostIndex <rightmostIndex) pivotIndex <- partition (array, leftmostIndex, rightmostIndex) quickSort (array, leftmostIndex, pivotIndex) quickSort (array, pivotIndex + 1, rightmost ) indstil rightmostIndex som pivotIndex storeIndex <- leftmostIndex - 1 for i <- leftmostIndex + 1 til rightmostIndex hvis element (i) <pivotElement swap element (i) og element (storeIndex) storeIndex ++ swap pivotElement og element (storeIndex + 1) returner storeIndex 1

Python, Java og C / C ++ eksempler

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); )

Quicksort-kompleksitet

Tidskompleksiteter

Worst Case-kompleksitet (Big-O) : Det sker, når det valgte drejningselement er enten det største eller det mindste element. Denne tilstand fører til det tilfælde, hvor drejningselementet ligger i en ekstrem ende af det sorterede array. En undergruppe er altid tom, og en anden undergruppe indeholder elementer. Quicksort kaldes således kun til dette underarray. Imidlertid har den hurtige sorteringsalgoritme bedre ydeevne for spredte drejninger.O(n²)
n - 1
Best case-kompleksitet (Big-omega) : O(n*log n)
Det sker, når drejningselementet altid er det midterste element eller tæt på det midterste element.
Gennemsnitlig sagskompleksitet (Big-theta) : O(n*log n)
Det sker, når ovenstående forhold ikke forekommer.