Question

Implement Heap Sort and Quick Sort in different programs with the following specifications: 1. The input to the programs should be ASCII characters 2. Your program should be able to handle upper and lower case letters both 3. The sort should be done in a descending manner 4.Note: Please use array-based representation for these sorting algorithms

Please write comment n explain each step clearly as well your program should show what you are taking as input array and what your output is. This should be a user input array. Do not declare your array already in the code. The user should input n output should be according to that.

Answer 1

QUICK SORT

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

// A utility function to swap two elements
void swap(char* a, char* b)
{
        char t = *a;
        *a = *b;
        *b = t;
}

/* This function takes last element as pivot, places
the pivot element at its correct position in sorted
array, and places all smaller (smaller than pivot)
to left of pivot and all greater elements to right
of pivot */
int partition (char arr[], int low, int high)
{
        char pivot = arr[high]; // pivot
        int i = (low - 1); // Index of smaller element

        for (int j = low; j <= high - 1; j++)
        {
                // If current element is smaller than the pivot
                if (arr[j] > pivot)
                {
                        i++; // increment index of smaller element
                        swap(&arr[i], &arr[j]);
                }
        }
        swap(&arr[i + 1], &arr[high]);
        return (i + 1);
}

/* The main function that implements QuickSort
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void quickSort(char arr[], int low, int high)
{
        if (low < high)
        {
                /* pi is partitioning index, arr[p] is now
                at right place */
                int pi = partition(arr, low, high);

                // Separately sort elements before
                // partition and after partition
                quickSort(arr, low, pi - 1);
                quickSort(arr, pi + 1, high);
        }
}

/* Function to print an array */
void printArray(char arr[], int size)
{
        int i;
        for (i = 0; i < size; i++)
                cout << arr[i] << " ";
        cout << endl;
}

// Driver Code
int main()
{

        int n ;
        cout << "Enter the number of characters to be sorted: ";
        cin >> n;
        char arr[n];
        cout << "Enter the characters to be sorted: ";
        for (int i = 0; i < n; ++i) {
                cin >> arr[i];
        }
        quickSort(arr, 0, n - 1);
        cout << "Sorted array: \n";
        printArray(arr, n);
        return 0;
}

OUTPUT:

HEAP SORT

// C++ program for implementation of Heap Sort 
#include <iostream> 

using namespace std; 

// To heapify a subtree rooted with node i which is 
// an index in arr[]. n is size of heap 
void heapify(char arr[], int n, int i) 
{ 
        int largest = i; // Initialize largest as root 
        int l = 2*i + 1; // left = 2*i + 1 
        int r = 2*i + 2; // right = 2*i + 2 

        // If left child is larger than root 
        if (l < n && arr[l] < arr[largest]) 
                largest = l; 

        // If right child is larger than largest so far 
        if (r < n && arr[r] < arr[largest]) 
                largest = r; 

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

                // Recursively heapify the affected sub-tree 
                heapify(arr, n, largest); 
        } 
} 

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

        // One by one extract an element from heap 
        for (int i=n-1; i>0; i--) 
        { 
                // Move current root to end 
                swap(arr[0], arr[i]); 

                // call max heapify on the reduced heap 
                heapify(arr, i, 0); 
        } 
} 

/* A utility function to print array of size n */
void printArray(char arr[], int n) 
{ 
        for (int i=0; i<n; ++i) 
                cout << arr[i] << " "; 
        cout << "\n"; 
} 

// Driver program 
int main() 
{ 
        int n ;
        cout << "Enter the number of characters to be sorted: ";
        cin >> n;
        char arr[n];
        cout << "Enter the characters to be sorted: ";
        for (int i = 0; i < n; ++i) {
                cin >> arr[i];
        }
        heapSort(arr, n);
        cout << "Sorted array: \n";
        printArray(arr, n);
        return 0;
} 

OUTPUT: