In this tutorial, you'll find out how Quicksort Algorithm works. Also, you'll find working samples of Quicksort Algorithm in C, C++ Python, and Java.
Quicksortis an algorithm supported divide and conquer approach during which the array is split into subarrays and these sub-arrays is recursively called to sort the weather.
How the QuickSort Algorithm Works?
A pivot element is chosen from the array. you'll choose any element from the array because of the pivot element. Here, we've taken the rightmost (ie. the last element) of the array because of the pivot element.
Select a pivot element in Quicksort
The elements smaller than the pivot element are placed on the left and therefore the elements greater than the pivot element are placed on the proper.
put the greater element in right and other in left
The above arrangement is achieved by the subsequent steps.
A pointer is fixed at the pivot element. The pivot element is compared with the weather beginning from the primary index. If the element greater than the pivot element is reached, a second pointer is about for that element.
Now, the pivot element is compared with the opposite elements (a third pointer). If a component smaller than the pivot element is reached, the smaller element is swapped with the greater element found earlier.
compare the element for the quicksort sorting algorithm
The process goes on until the second last element is reached.
After following the process, the pivot element in Quicksort Algorithm is swapped with the second pointer.
Swap pivot element with the second pointer for sorting algorithm
Now the left and right subparts of this pivot element are taken for further processing within the steps below.
Pivot elements are again chosen for the left and therefore the right sub-parts separately. With the help of these sub-parts, the chosen pivot elements are placed in their right position. Then, step 2 is repeated.
Select pivot element in Quicksort algorithm of in each half and put at the correct place using recursion
The sub-parts are again divided into smaller sub-parts until each subpart is made of one element.
At now, the array is already sorted.
Check For Quick Sort Algorithm:-
Check For Quick Sort Algorithm
Quicksort algorithm Program In C
#include <stdio.h>
// check out the Function to swap position of elements in quicksort algorithm
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
// Function to partition for the quick sort algorithm array on the basis of pivot element
int partition(int array[], int low, int high) {
// Now Select the pivot element
int pivot = array[high];
int i = (low - 1);
// comparison for element Put the elements smaller than pivot on the left
// and put the greater element 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) {
int pi = partition(array, low, high);
// Sort the elements on the left of the 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 in quicksort
void printArray(int array[], int size) {
for (int i = 0; i < size; ++i) {
printf("%d ", array[i]);
}
printf("\n");
}
// 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: \n");
printArray(data, n);
}
Quicksort Algorithm uses recursion for sorting the sub-parts.
On the idea of Divide and conquer approach, the quicksort algorithm is often explained as:
Divide
The array is split into subparts taking pivot because of the partitioning point. the weather smaller than the pivot is placed to the left of the pivot and therefore the elements greater than the pivot are placed to the proper.
Conquer
The left and therefore the right subparts are again partitioned using the by selecting pivot elements for them. this will be achieved by recursively passing the subparts into the QuickSorting algorithm.
Combine
This step doesn't play a big role in quicksort. The array is already sorted at the top of the conquer step.
You can understand the working of quicksort with the assistance of the illustrations below.
Sorting the left side elements by recursion
Sorting the right side elements by recursion
Complexity For Quicksort Algorithm
Time Complexities
Worst Case Complexity [Big-O]: O(n2)
It occurs when the pivot element picked is either the best or the littlest element. This condition results in the case during which the pivot element lies in an extreme end of the sorted array. One sub-array is usually empty and another sub-array contains n - 1 element. Thus, the quicksort Algorithm is named only on this sub-array. However, the Quicksort algorithm in C and for any other languages has better performance for scattered pivots. Best Case Complexity [Big-omega]: O(n*log n) It occurs when the pivot element is usually the central element or almost the center element. Average Case Complexity [Big-theta]: O(n*log n)
