# QuickSort

Analaysis though it seems little bit tough to me:

HackerRank video:

Pseudo Code from upper Youtube vid:

```QuickSort(A, start, end)
{
if(start<end)
pIndex=Partition(A,start,end);
Quicksort(A,start,index-1);
Quicksort(A,pIndex+1,end);
}

Partition(A,start,end)
{
pivot=A[end];
pIndex=start;
for i=start to end-1
{
if(A[i]<=pivot)
{
swap(A[i],A[pIndex])
pIndex=pIndex+1
}
}
swap(A[pIndex],A[end])
return pIndex
}```

Implementation:

```#include<iostream>
using namespace std;
int Partition(int *A,int start,int ends){
int pivot=A[ends];
int pIndex=start;
for(int i=start; i<ends; i++){
if(A[i]<=pivot)
{
//swap(A[i],A[pIndex]);
int z=A[i];
A[i]=A[pIndex];
A[pIndex]=z;
pIndex=pIndex+1;
}
}
//swap(A[pIndex],A[ends]);
int k=A[pIndex];
A[pIndex]=A[ends];
A[ends]=k;
return pIndex;
}

void Quicksort(int *A,int start,int ends)
{
if(start<ends){
int pIndex=Partition(A,start,ends);
Quicksort(A,start,pIndex-1);
Quicksort(A,pIndex+1,ends);
}
}

int main()
{
int A[]={3,4,1,4,0,9,6,5};
Quicksort(A,0,7);
for(int i=0;i<8;i++)
{
cout<<A[i]<<" ";
}
return 0;
}```

Slightly edited in *A to A[]:

```#include<iostream>
using namespace std;
int Partition(int A[],int start,int ends){
int pivot=A[ends];
int pIndex=start;
for(int i=start; i<ends; i++){
if(A[i]<=pivot)
{
//swap(A[i],A[pIndex]);
int z=A[i];
A[i]=A[pIndex];
A[pIndex]=z;
pIndex=pIndex+1;
}
}
//swap(A[pIndex],A[ends]);
int k=A[pIndex];
A[pIndex]=A[ends];
A[ends]=k;
return pIndex;
}

void Quicksort(int A[],int start,int ends)
{
if(start<ends){
int pIndex=Partition(A,start,ends);
Quicksort(A,start,pIndex-1);
Quicksort(A,pIndex+1,ends);
}
}

int main()
{
int A[]={3,4,1,4,0,9,6,5};
Quicksort(A,0,7);
for(int i=0;i<8;i++)
{
cout<<A[i]<<" ";
}
return 0;
}
```

Some change with before and after show:

```#include<iostream>
using namespace std;
int Partition(int A[],int start,int ends){
int pivot=A[ends];
int pIndex=start;
for(int i=start; i<ends; i++){
if(A[i]<=pivot)
{
//swap(A[i],A[pIndex]);
int z=A[i];
A[i]=A[pIndex];
A[pIndex]=z;
pIndex=pIndex+1;
}
}
//swap(A[pIndex],A[ends]);
int k=A[pIndex];
A[pIndex]=A[ends];
A[ends]=k;
return pIndex;
}

void Quicksort(int A[],int start,int ends)
{
if(start<ends){
int pIndex=Partition(A,start,ends);
Quicksort(A,start,pIndex-1);
Quicksort(A,pIndex+1,ends);
}
}

int main()
{
int A[]={3,4,1,4,0,9,6,5};
int sizes=sizeof(A)/sizeof(A[0]);
cout<<"Before Sorting: ";
for(int i=0; i<sizes; i++)
{
cout<<A[i]<<" ";
}
Quicksort(A,0,7);
cout<<endl;
cout<<"After Sorting: ";
for(int i=0;i<8;i++)
{
cout<<A[i]<<" ";
}
return 0;
}```

Complete Quicksort Implementation and taking user input:

```#include<iostream>
using namespace std;
int Partition(int A[],int start,int ends)
{
int pivot=A[ends];
int pIndex=start;
for(int i=start; i<ends; i++)
{
if(A[i]<=pivot)
{
//swap(A[i],A[pIndex]);
int z=A[i];
A[i]=A[pIndex];
A[pIndex]=z;
pIndex=pIndex+1;
}
}
//swap(A[pIndex],A[ends]);
int k=A[pIndex];
A[pIndex]=A[ends];
A[ends]=k;
return pIndex;
}

void Quicksort(int A[],int start,int ends)
{
if(start<ends)
{
int pIndex=Partition(A,start,ends);
Quicksort(A,start,pIndex-1);
Quicksort(A,pIndex+1,ends);
}
}

int main()
{
int sizes;
int A[1000];
cout<<"How many value will you add ? ";
cin>>sizes;
for(int k=0; k<=sizes-1; k++)
{
cin>>A[k];
}
//int sizes=sizeof(A)/sizeof(A[0]);
cout<<"Before Sorting: ";
for(int i=0; i<=sizes-1; i++)
{
cout<<A[i]<<" ";
}
Quicksort(A,0,sizes-1);
cout<<endl;

cout<<"After Sorting: ";
for(int i=0; i<=sizes-1; i++)
{
cout<<A[i]<<" ";
}
return 0;
}```

Output from the above code:

From geeks for geeks but may be there might be some problems there

```#include<iostream>
using namespace std;
//*arr eitype likha mane arrayta sudhu value/content ta send korbe ekhane pointer diye value tene antese
void swaps(int *a,int *b){
int z=*a;
*b=*a;
*a=z;
}

int partitions(int arr[],int low,int high){
int    pivot=arr[high];
int    i=(low-1);
for(int j=low;j<=high-1;j++){
if(arr[j]<=pivot)
{
i++;
swaps(&arr[i],&arr[j]);
}
}
swaps(&arr[i+1],&arr[high]);
return(i+1);
}

void quicksort(int arr[],int low,int high){
if(low<high){
int    pi=partitions(arr,low,high);
quicksort(arr,low,pi-1);
quicksort(arr,pi+1,high);
}
}
void printArray(int arr[],int n){
for(int i=0;i<n;i++){
cout<<arr[i]<<" ";
}
}

int main()
{
//int arr[]={10,7,8,9,1,5};
//int sizes=sizeof(arr)/sizeof(arr[0]);
//cout<<"Unsorted array: ";
//for(int i=0;i<sizes;i++){
//cout<<arr[i]<<" ";
//}
//cout<<endl;
int arr[] = {10, 7, 8, 9, 1, 5};
int n = sizeof(arr)/sizeof(arr[0]);
quicksort(arr, 0, n-1);
cout<<"Sorted array: ";
printArray(arr, n);
return 0;
}
```

Another good one for understanding(I think it’s the best one):

Pseudocode available in the above video:

implemented code:

```#include<bits/stdc++.h>
using namespace std;
int Partition(int A[],int p,int r)
{
int x=A[r];
int i=p-1;
for(int j=p; j<=r-1; j++)
{
if(A[j]<=x)
{
i=i+1;
//swap(A[i],A[j]);
//swapping
int z=A[j];
A[j]=A[i];
A[i]=z;
}
}
//swap(A[i+1],A[r]);
//swapping
int m=A[r];
A[r]=A[i+1];
A[i+1]=m;
return (i+1); //sending the pivot value to the actual caller function QuickSort
}
int QuickSort(int A[],int p,int r)
{
if(p<r)
{
int q=Partition(A,p,r);
QuickSort(A,p,q-1);
QuickSort(A,q+1,r);
}
}
int main()
{
//int A[]= {2,1,3,4,10,5,8};
int A[]={10,5,8,2,4,3,1};
QuickSort(A,0,6);
for(int i=0; i<7; i++)
{
cout<<A[i]<<" ";
}

return 0;
}```

```#include<bits/stdc++.h>
using namespace std;
void swaps(int *p,int *q)
{
int temp=*q;
*q=*p;
*p=temp;
}
int Partition(int A[],int p,int r)
{
int x=A[r];
int i=p-1;
for(int j=p; j<=r-1; j++)
{
if(A[j]<=x)
{
i=i+1;
//swap(A[i],A[j]);
//swapping
swaps(&A[i],&A[j]);
//            int z=A[j];
//            A[j]=A[i];
//            A[i]=z;
}
}
//swap(A[i+1],A[r]);
//swapping
//    int m=A[r];
//    A[r]=A[i+1];
//    A[i+1]=m;
swaps(&A[i+1],&A[r]);
return (i+1); //sending the pivot value to the actual caller function QuickSort
}
int QuickSort(int A[],int p,int r)
{
if(p<r)
{
int q=Partition(A,p,r);
QuickSort(A,p,q-1);
QuickSort(A,q+1,r);
}
}
int main()
{
//int A[]= {2,1,3,4,10,5,8};
int A[]={10,5,8,2,4,3,1};
QuickSort(A,0,6);
for(int i=0; i<7; i++)
{
cout<<A[i]<<" ";
}

return 0;
}```

Quick Sorting in Process

Time and Space complexity: Best Case : omega(nlogn)
Worst case: O(n^2)

See this video to clear up the skills:

It would be a great help, if you support by sharing :)
Author: zakilive