QuickSort

 June 23, 2017  Leave a Comment on QuickSort  Posted in A ll Codes, Algorithm, Quicksort

Youtube Video:

Analaysis though it seems little bit tough to me:

HackerRank video:

MIT video:
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-4-quicksort-randomized-algorithms/

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:

Geeks for geeks:
http://quiz.geeksforgeeks.org/quick-sort/
http://www.practice.geeksforgeeks.org/problem-page.php?pid=700151

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:

ideone example: http://ideone.com/oWbONR
Others Code:
http://www.cc.gatech.edu/classes/cs3158_98_fall/quicksort.html
Recursive:
http://www.algolist.net/Algorithms/Sorting/Quicksort
CLRS:
http://www.bowdoin.edu/~ltoma/teaching/cs231/fall09/Lectures/5-quicksort/quicksort.pdf

Google Search Terms:
https://www.google.com/webhp?sourceid=chrome-instant&rlz=1C1PRFC_enBD706BD706&ion=1&espv=2&ie=UTF-8#q=quick+sort+pseudocode&*

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

Leave a Reply

Your email address will not be published. Required fields are marked *