*
#include<bits/stdc++.h>
using namespace std;
int partitionFunction(int array[],int left, int right, int pivot)
{
int leftPointer = left -1;
int rightPointer = right;
while(true)
{
while(array[++leftPointer] < pivot)
{
//do nothing
}
while(rightPointer > 0 && array[--rightPointer] > pivot)
{
//do nothing
}
if(leftPointer >= rightPointer)
{
break;
}
else
{
swap(array[leftPointer],array[rightPointer]);
//swapFunctionping between [leftPointer] and [rightPointer]
}
}
swap(array[leftPointer],array[right]);
return leftPointer;
}
void quickSort(int array[],int left, int right)
{
if(right-left<= 0)
{
return;
}
else
{
int pivot = array[right];
int partitionPoint = partitionFunction(array,left, right, pivot);
quickSort(array,left,partitionPoint-1);
quickSort(array,partitionPoint+1,right);
}
}
int main()
{
int n;
cout<<"Enter the size of array :\n";
cin>>n;
int array[n];
cout<<"Enter the elements into array :\n";
for(int i=0;i<n;i++)
{
cin>>array[i];
}
quickSort(array,0,n-1);
cout<<"Ater Sorting : \n";
for(int k=0;k<n;k++)
{
cout<<array[k]<<" ";
}
return 0;
}
Complexity of QuickSort:
Time: O(n2) [worstCase]
Space: O(n)
Time: O(n2) [worstCase]
Space: O(n)
Quote: