Question

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

Answer 1

The implimentation of quick sort is :

the partition method shifts every element geater than the pivot element to right of pivot and every smaller element to left of pivot.

the quicksort method finds the partition element and then recursively calls itself on left and right subarray

the code is:

#include <iostream>
using namespace std;


void swap(int *x, int *y) {
  int temp = *x;
  *x = *y;
  *y = temp;
}

// Function to print eklements of an array
void print(int array[], int n) {
  int i;
  for (i = 0; i < n; i++)
    cout << array[i] << " ";
  cout << endl;
}

// Function that partitions array based on pivot
int partition(int array[], int l, int h) {
  // Selecting pivot
  int p = array[h];
  int i = (l - 1);

  // Puts smaller element than pivot to left
  // and greater elements to right of pivot
  for (int j = l; j < h; j++) {
    if (array[j] <= p) {
      i++;
      swap(&array[i], &array[j]);
    }
  }
  swap(&array[i + 1], &array[h]);
  return (i + 1);
}

void quickSort(int array[], int l, int h) {
  if (l < h) {
    // Selects ppivot and puts smaller element to left of pivot and greater elements to right of pivot
    int pi = partition(array, l, h);

    // Sorts  elements on the left of pivot
    quickSort(array, l, pi - 1);

    // Sorts elements right of pivot
    quickSort(array, pi + 1, h);
  }
}


int main() {
  int arr[] = {8, 7, 6, 1, 0, 9, 2};
  int n = sizeof(arr) / sizeof(arr[0]);
  quickSort(arr, 0, n - 1);
  cout << "Sorted array in ascending order: \n";
  print(arr, n);
}

The code for heapsort is:

using namespace std;

void heapify(int arr[], int n, int i)
{
    int largest = i; // Initially largest is root
    int left = 2*i + 1; // left child = 2*i + 1
    int right = 2*i + 2; // right child= 2*i + 2

    // If left child is greater
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // If right child is larger
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // If the larger element is not root
    if (largest != i)
    {
        swap(arr[i], arr[largest]);

        // Recursively fix the position of largest
        heapify(arr, n, largest);
    }
}

//  function to do heap sort
void heapSort(int arr[], int n)
{
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // extract an element from heap
    for (int i=n-1; i>0; i--)
    {
        // put the element to the end of heap
        swap(arr[0], arr[i]);

        heapify(arr, i, 0);
    }
}

void print(int arr[], int n)
{
    for (int i=0; i<n; ++i)
        cout << arr[i] << " ";
    cout << "\n";
}

int main()
{
    int arr[] = {8, 7, 6, 1, 0, 9, 2};
    int n = sizeof(arr)/sizeof(arr[0]);

    heapSort(arr, n);

    cout << "array in sorted order is \n";
    print(arr, n);
}