Question

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

FULL PROGRAMM BOTH THE QUICK SORT AND HEAP SORT IN THE SAME PROGRAM

PS: YOU ARE ANSEWRING THE SAME PROGRAMS I WANT DIFFERENT ONE PLEASE , THANK YOU .

BECAUSE THE ONE WERE POSTING DOESNT WORKING !!

Answer 1

#include <bits/stdc++.h>
using namespace std;

//QUICK SORT
int partition (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++;
           swap(arr[i],arr[j]);
       }
   }
   swap(arr[i + 1],arr[high]);
   return (i + 1);
}
void quickSort(int arr[], int low, int high)
{
   if (low < high)
   {
       int pi = partition(arr, low, high);
       quickSort(arr, low, pi - 1);
       quickSort(arr, pi + 1, high);
   }
}

//HEAP SORT
void heapify(int arr[], int n, int i)
{
int largest = i;
int l = 2*i + 1;
int r = 2*i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i)
{
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i=n-1; i>0; i--)
{
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}

int main()
{
   cout<<"Enter the no of elements-\n";
   int n;
   cin>>n;
   cout<<"Enter the array's elements-\n";
   int arr[n+1];
   for(int i=0;i<n;i++)
{
cin>>arr[i];
}
cout<<"Press 1 for quick sort or 2 for heap sort-\n";
int ch;
cin>>ch;
if(ch==1)
{
quickSort(arr, 0, n - 1);
cout << "Sorted array after applying quick sort is: \n";
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
}
   else if(ch==2)
{
heapSort(arr, n);
cout << "Sorted array after applying heap sort is: \n";
for(int i=0;i<n;i++)
cout<<arr[i]<<" ";
}
else
cout<<"Invalid choice";
   return 0;
}

OUTPUT -