QuickSort-algoritme

Innholdsfortegnelse

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

I denne veiledningen vil du lære hvordan quicksort fungerer. Du finner også arbeidseksempler på quicksort i C, C ++ Python og Java.

Quicksort er en algoritme basert på deling og erobringstilnærming der matrisen er delt inn i underarrays og disse underarrayene kalles rekursivt for å sortere elementene.

Hvordan fungerer QuickSort?

Et pivotelement velges fra matrisen. Du kan velge hvilket som helst element fra matrisen som pivotelement.
Her har vi tatt den høyre (dvs. det siste elementet) av matrisen som dreieelement. Velg et dreieelement
Elementene som er mindre enn pivotelementet, er satt til venstre og elementene som er større enn pivotelementet, er plassert til høyre. Sett alle de mindre elementene til venstre og større på høyre side av dreieelementet
. Arrangementet ovenfor oppnås ved å følge trinnene nedenfor.
1. En peker er festet ved dreieelementet. Svingelementet sammenlignes med elementene som begynner fra den første indeksen. Hvis elementet som er større enn pivotelementet er nådd, settes en andre peker for det elementet.
2. Nå blir pivotelementet sammenlignet med de andre elementene (en tredje peker). Hvis et element som er mindre enn pivotelementet er nådd, byttes det mindre elementet ut med det større elementet som ble funnet tidligere. Sammenligning av dreieelement med andre elementer
3. Prosessen fortsetter til det nest siste elementet er nådd.
  Til slutt byttes svingelementet ut med den andre pekeren. Bytt pivotelement med den andre pekeren
4. Nå er venstre og høyre del av dette dreieelementet tatt for videre behandling i trinnene nedenfor.
Dreieelementer velges igjen for venstre og høyre underdel separat. Innenfor disse underdelene er dreieelementene plassert i riktig posisjon. Deretter gjentas trinn 2. Velg dreieelement i hver halvdel og sett på riktig sted ved hjelp av rekursjon
Underdelene er igjen delt inn i mindre underdeler til hver underdel er dannet av et enkelt element.
På dette punktet er matrisen allerede sortert.

Quicksort bruker rekursjon for å sortere underdelene.

På bakgrunn av Divide and conquer-tilnærmingen kan quicksort-algoritmen forklares som:

Del
Matrisen er delt inn i underdeler som tar ledd som partisjoneringspunktet. Elementene som er mindre enn pivoten er plassert til venstre for pivoten, og elementene som er større enn pivot er plassert til høyre.
Conquer
Venstre og høyre del er partisjonert igjen ved hjelp av ved å velge dreieelementer for dem. Dette kan oppnås ved å rekursivt overføre delene til algoritmen.
Kombinere
Dette trinnet spiller ikke en vesentlig rolle i kviksort. Matrisen er allerede sortert på slutten av erobringstrinnet.

Du kan forstå hvordan quicksort fungerer ved hjelp av illustrasjonene nedenfor.

Sortere elementene til venstre for pivot ved hjelp av rekursjon

Sortere elementene til høyre for pivot ved hjelp av rekursjon

Rask sorteringsalgoritme

 quickSort (array, leftmostIndex, rightmostIndex) if (leftmostIndex <rightmostIndex) pivotIndex <- partition (array, leftmostIndex, rightmostIndex) quickSort (array, leftmostIndex, pivotIndex) quickSort (array, pivotIndexdex, ) sett rightmostIndex som pivotIndex storeIndex <- leftmostIndex - 1 for i <- leftmostIndex + 1 to rightmostIndex if element (i) <pivotElement swap element (i) and element (storeIndex) storeIndex ++ swap pivotElement and element (storeIndex + 1) return store 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 Complexity (Big-O) : Det oppstår når det valgte pivotelementet er enten det største eller det minste elementet. Denne tilstanden fører til tilfelle der svingelementet ligger i en ekstrem ende av den sorterte matrisen. En undergruppe er alltid tom, og en annen undergruppe inneholder elementer. Dermed kalles kviksort kun på denne undergruppen. Imidlertid har den raske sorteringsalgoritmen bedre ytelse for spredte pivoter.O(n²)
n - 1
Best case-kompleksitet (Big-omega) : O(n*log n)
Det oppstår når dreieelementet alltid er midtelementet eller nær midtelementet.
Gjennomsnittlig sakskompleksitet (Big-theta) : O(n*log n)
Det oppstår når forholdene ovenfor ikke oppstår.