Question

Implementation of Quick sort and heap sorting algorithms in C++

FULL PROGRAMM

BOTH THE QUICK SORT AND HEAP SORT IN THE SAME PROGRAMM

Answer 1

Implementation of Quick sort and heap sorting algorithms in C++--->

#include <iostream>
#define ll long long
using namespace std;
void swap(int *x, int *y) 
{ 
        int* t; 
        t=x; 
        x=y; 
        y=t; 
} 
int part(int *A,int start,int end) 
{ 
    /* function  to partition array and return true position of
    pivot element in array*/
        int pivot,pindex,i; 
         
        pivot=A[end]; 
        pindex=start; 
         
        for(i=start;i<end;i++) 
        { 
                if(A[i]<=pivot) 
                {        
                        swap(A[i],A[pindex]); 
                        pindex++; 
                } 
        } 
         
        swap(A[pindex],A[end]); 
         
        return pindex; 
} 

void quicksort(int *A,int start,int end) //complexity nlogn average case n^2 in worst case
{ 
        if(start<end) 
        { 
       /* pindex is partitioning index*/
                int pindex=part(A,start,end); 
                quicksort(A,start,pindex-1);  //recursive calling left
                quicksort(A,pindex+1,end); //recursive calling right
    }
}
void MaxHeap(int A[],int i,int n) //code to heapify or create maxheap
{ 
        int large=i; // initialize large with root index
        int lf=2*i; 
        int rf=2*i+1; 
        if(lf<n && A[lf]>A[large]) //if left child value > root value
                large=lf; 
        if(rf<n && A[rf]>A[large]) //if right child value > root value
                large=rf; 

        if(i!=large) 
        { 
                int s=A[large]; 
                A[large]=A[i]; 
                A[i]=s; 
        /*recursively heapify*/
                MaxHeap(A,large,n); 
        } 
} 

void heapSort(int arr[], int n) //complexity O(nlogn)
{ 
        int i; 
    /*creating heap*/
        for (i = n / 2 - 1; i >= 0; i--) 
                MaxHeap(arr,i,n);   
        for (i=n-1; i>=0; i--) 
        {   
        /* in each iteration 1 element is extracted*/
                int s=arr[0]; 
                arr[0]= arr[i]; 
                arr[i]=s;   
                MaxHeap(arr,0,i); 
        } 
} 

int main()
{
    /** taking input of size and sorting using quicksort*/
    int n;
    cin>>n;
   int a[n];
   for(int i=0;i<n;i++)
   cin>>a[i];
   quicksort(a,0,n-1);
   for(int i=0;i<n;i++)
   cout<<a[i]<<" ";

/*sort using heapsort*/
   int m;
   cin>>m;
   int b[m];
   for(int i=0;i<m;i++)
   cin>>b[i];
   heapSort(b,m);
   for(int i=0;i<m;i++)
   cout<<b[i]<<" ";
}

output