Question

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

Answer 1

QUICKSORT ALGORITHM IS IMPLEMENTED IN C++

#include <iostream> 
using namespace std;  

// for swapping of the element 
void swap(int* first, int* second) 
{  
    int temp = *first;  
    *first= *second;  
    *second = temp;  
}  
  
//here, the partitioning of the elements is taking place
int partition (int a[], int beg, int end)
{  
    int pivot = a[end]; 
    int i = (beg - 1); 
  
    for (int j = beg; j <= end - 1; j++)  
    {  
      
        if (a[j] < pivot)  
        {  
            i++; 
            swap(&a[i], &a[j]);  
        }  
    }  
    swap(&a[i + 1], &a[end]);  
    return (i + 1);  
}  
  
// implementing the quicksort algorithm and sorting is based on partiotional index

void quickSort(int a[], int beg, int end)  
{  
    if (beg < end)  
    {  
        
        int pIndex = partition(a, beg, end);  
  
        quickSort(a, beg, pIndex - 1);  
        quickSort(a, pIndex + 1, end);  
    }  
}  

// displaying the elements of the array
void display(int a[], int n)
{  
  
    for (int i = 0; i < n; i++)  
        cout << a[i] << " ";  
    cout << endl;  
}  
  
int main()  
{  
    int a[] = {10, 7, 8, 9, 1, 5};  
    int n = sizeof(a) / sizeof(a[0]);
    cout << "Elements of array before sorting: \n";  
    display(a, n);
    quickSort(a, 0, n - 1);  
    cout << "Elements of array after sorting: \n";  
    display(a, n);  
    return 0;  
} 

HEAPSORT ALGORITHM IMPLEMENTED IN C++

  #include <iostream>
  using namespace std;
  //swapping the element by finding the maximum among the root, left and right child
  void heapify(int arr[], int n, int i) {
    int max = i;
    int leftChild = 2 * i + 1;
    int rightChild = 2 * i + 2;
  
    if (leftChild < n && arr[leftChild] > arr[max])
      max = leftChild;
  
    if (rightChild < n && arr[rightChild] > arr[max])
      max = rightChild;
  
    if (max != i) {
      swap(arr[i], arr[max]);
      heapify(arr, n, max);
    }
  }
  //sorting the array
  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);
    }
  }
  //displaying the array
  void display(int arr[], int n) {
    for (int i = 0; i < n; ++i)
      cout << arr[i] << " ";
    cout << "\n";
  }
  
  int main() {
    int arr[] = {11, 34, 9, 5, 16, 10};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Original array:\n";
    display(arr, n);
    heapSort(arr, n);
  
    cout << "Sorted array:\n";
    display(arr, n);
  }