Quicksort is a highly efficient sorting algorithm in which a list or array of elements is partitioned into smaller arrays.
A pivot(or central) element is selected in the array. The pivot element can be the first element, the last element, or any random element. The elements smaller than the pivot element are put to its left and greater elements to its right.
Steps :
Code:
// partition the A on the basis of pivot element
int partition(int A[], int start, int end) {
int pivot = A[end];
int i = (start - 1);
for (int j = start; j < end; j++) {
if (A[j] <= pivot) {
i++;
swap(&A[i], &A[j]);
}
}
printA(A, 7);
cout << "........\n";
swap(&A[i + 1], &A[end]);
return (i + 1);
}
void QuickSort(int A[], int start, int end) {
if (start < end) {
// Select pivot position and put all the elements smaller than pivot on left and greater than pivot on right
int p = partition(A, start, end);
// Sort the elements on the left of pivot
QuickSort(A, start, p - 1);
// Sort the elements on the right of pivot
QuickSort(A, p + 1, end);
}
}
O(n^2)