Quick Sort - Implementation
Use Recursion to implement Quick Sort.
We'll cover the following...
Implementation
In the Quick Sort lesson, we discussed the logic to implement the Quick Sort. So without wasting any time, let’s jump right into the code.
Press + to interact
#include <iostream>using namespace std;int partition(int *arr, int left, int right, int pivot){int leftPointer = left;int rightPointer = right;while(true) {while(arr[leftPointer] < pivot) {leftPointer++;}while(rightPointer > 0 && arr[rightPointer] > pivot) {rightPointer--;}if(leftPointer >= rightPointer)break;else{int temp = arr[leftPointer];arr[leftPointer] = arr[rightPointer];arr[rightPointer] = temp;}}int temp = arr[leftPointer];arr[leftPointer] = arr[rightPointer];arr[rightPointer] = temp;return leftPointer;}void quickSort(int *arr, int left, int right){if(right-left <= 0)return;else {int pivot = arr[right];int partitionPoint = partition(arr, left, right, pivot);quickSort(arr, left, partitionPoint-1);quickSort(arr, partitionPoint+1, right);}}int main() {int arr[7] = {4,6,3,2,1,9,7};int n = sizeof(arr)/sizeof(arr[0]);quickSort(arr, 0, n - 1);for(int i = 0; i < n; i++)cout << arr[i] << " ";}
Explanation:
- On line 4, we define our
partition()
function, which will move the pivot element to its correct position. - On line 9, we run a loop with an infinite condition.
- On lines 10 and 11, we run an inner loop, which will make the value of
leftPointer
as the index till which all the elements are smaller thanpivot
. As