Lab 3 = Quick

#include<iostream>
#include <cstdlib>

using namespace std;

class student
{
public:
    int id;
    string name;
    float cgpa;
    int phn;

    void input()
    {
        cin>>id>>name>>cgpa>>phn;
    }
    void output()
    {
        cout<<"\t"<<id;
        cout<<"\t"<<name;
        cout<<"\t"<<cgpa;
        cout<<"\t"<<phn;
        cout<<endl;
    }
};
int partition1(student a[],int p,int r)
{
    student x;
    student temp;
    int i,j;
    x=a[p];
    i=r+1;
    for(j=r; j>=p+1; j--)
    {
        if(a[j].cgpa>=x.cgpa)
        {
            i=i-1;
            temp=a[j];
            a[j]=a[i];
            a[i]=temp;
        }
    }

    temp=a[i-1];
    a[i-1]=a[p];
    a[p]=temp;

    return i-1;
}
void quicksort1(student a[],int p,int r)
{
    int q;
    if(p<r)
    {
        q=partition1(a,p,r);
        quicksort1(a,p,q-1);
        quicksort1(a,q+1,r);

    }
}

int partition2(student a[],int p,int r)
{
    student x;
    student temp;
    int i,j;
    x=a[r];
    i=p-1;
    for(j=p; j<=r-1; j++)
    {
        if(a[j].cgpa<=x.cgpa)
        {
            i=i+1;
            temp=a[j];
            a[j]=a[i];
            a[i]=temp;
        }
    }

    temp=a[i+1];
    a[i+1]=a[r];
    a[r]=temp;

    return i+1;
}
void quicksort2(student a[],int p,int r)
{
    int q;
    if(p<r)
    {
        q=partition2(a,p,r);
        quicksort2(a,p,q-1);
        quicksort2(a,q+1,r);

    }
}

int partition3(student a[],int p,int r)
{
    student x;
    student temp;
    int random;
    random = p + rand() % (r - p);
    swap(a[random],a[r]);
    int i,j;
    x=a[r];
    i=p-1;
    for(j=p; j<=r-1; j++)
    {
        if(a[j].cgpa<=x.cgpa)
        {
            i=i+1;
            temp=a[j];
            a[j]=a[i];
            a[i]=temp;
        }

    }
    temp=a[r];
    a[r]=a[i+1];
    a[i+1]=temp;
    return i+1;

}
void quicksort3(student a[],int p,int r)
{
    int q;
    if(p<r)
    {
        q=partition3(a,p,r);
        quicksort3(a,p,q-1);
        quicksort3(a,q+1,r);
    }
}

int main()
{
    student s[100];
    int n,i,choice;

    cout<<"Enter the number of student:";
    cin>>n;
    cout<<"\nStudent information\n";
    for(i=1; i<=n; i++)
    {
        s[i].input();
    }

    cout<<"\n1. First Pivot QuickSort";
    cout<<"\n2. Last Pivot QuickSort";
    cout<<"\n3. Randomized QuickSort";
    cout<<"\n4. Exit";


    while(1)
    {
        cout<<"\nEnter your choice:";
        cin>>choice;

        if(choice==1)
        {
            quicksort1(s,1,n);
        }
        else if(choice==2)
        {
            quicksort2(s,1,n);
        }
        else if(choice==3)
        {
            quicksort3(s,1,n);
        }
        else if(choice==4)
        {
            break;
        }
        cout<<"\nStudent Sorted Information\n";
        for(i=1; i<=n; i++)
        {
            s[i].output();
        }
    }
    return 0;
}