Question

In: Computer Science

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

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

Solutions

Expert Solution

Quick sort :

#include <bits/stdc++.h> 
using namespace std;  
  
// A utility function to swap two elements  
void swap(int* a, int* b)  
{  
    int 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 (int arr[], int low, int high)  
{  
    int 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(int 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(int arr[], int size)  
{  
    int i;  
    for (i = 0; i < size; i++)  
        cout << arr[i] << " ";  
    cout << endl;  
}  
  
// Driver Code 
int main()  
{  
    int arr[] = {10, 7, 8, 9, 1, 5};  
    int n = sizeof(arr) / sizeof(arr[0]);  
    quickSort(arr, 0, n - 1);  
    cout << "Sorted array: \n";  
    printArray(arr, n);  
    return 0;  
}  

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(int 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(int 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(int arr[], int n) 
{ 
    for (int i = 0; i < n; ++i) 
        cout << arr[i] << " "; 
    cout << "\n"; 
} 
  
// Driver program 
int main() 
{ 
    int arr[] = { 12, 11, 13, 5, 6, 7 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 
  
    heapSort(arr, n); 
  
    cout << "Sorted array is \n"; 
    printArray(arr, n); 
}

Please do give a like thanks..!!


Related Solutions

Implementation of Quick sort and heap sorting algorithms in C++ FULL PROGRAMM BOTH THE QUICK SORT...
Implementation of Quick sort and heap sorting algorithms in C++ FULL PROGRAMM BOTH THE QUICK SORT AND HEAP SORT IN THE SAME PROGRAMM
Implementation of Quick sort and heap sorting algorithms in C++ FULL PROGRAMM BOTH THE QUICK SORT...
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 !!
Which of the following sorting algorithms are stable: insertion sort, selection sort, merge sort and quick...
Which of the following sorting algorithms are stable: insertion sort, selection sort, merge sort and quick sort? Give a simple scheme that makes any sorting algorithm stable. How much additional time and space does your scheme entail?
C++ Question- Write function templates for 5 sort algorithms: - Quick Sort Apply these algorithms to...
C++ Question- Write function templates for 5 sort algorithms: - Quick Sort Apply these algorithms to 10 different arrays of integers. Each array has 100 integer elements. The arrays are filled with random integer numbers.
Comparing (Sort Algorithms) Both of the two sorting algorithms will do "sort" on arrays which would...
Comparing (Sort Algorithms) Both of the two sorting algorithms will do "sort" on arrays which would contain x randomly generated integers where the value of x would be 10000, 20000, 40000 and 80000 (inputs). The parts of the program should be followed as..... 1. Set x = 10000, randomly generate x integers. Call qsort function to sort these integers and get the execution time. 2. Randomly generate another x integers. Call your own sorting algorithm and get the execution time....
Implement Heap Sort and Quick Sort in different programs with the following specifications: 1. The input...
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...
Write a MIPS program that uses an implementation of quick sort to sort an array of...
Write a MIPS program that uses an implementation of quick sort to sort an array of numbers (Translate the following code into (Mars Assembly language). Quicksort Implementation - C int partition(int arr [] , int left , int right) { int i=left, j=right; int tmp; int pivot = arr[(left + right) / 2]; while (i <= j) { while (arr [ i ] < pivot) i ++; while (arr [ j ] > pivot) j −−; if (i <= j)...
Implement heap sort by using the bottom-up insertion method. Add this sort to your sorting framework....
Implement heap sort by using the bottom-up insertion method. Add this sort to your sorting framework. Evaluate its performance in terms of the numbers of comparisons and exchanges, and compare it to the performance of the two advanced sorting methods that you have previously implemented. Submit your report with detailed empirical results and a thorough explanation of these results. Which of the three advanced sorting method is the best choice for a) ordered data, b) data in reverse order, and...
Import a data set (txt file) then do the sorting algorithm using quick sort, shell sort,...
Import a data set (txt file) then do the sorting algorithm using quick sort, shell sort, and selection sort. It must show how long it took and how many movements occurred. Please write codes in C++ Here's data set (should be stored in txt file) 7426 4524 4737 9436 3997 2757 6288 5414 9590 5968 6638 3199 9514 1541 9866 2144 6731 911 2171 6135 6437 912 9417 2662 6606 6349 707 2890 5386 9718 3492 5068 9674 8578 8323...
In this project you will implement and experiment with three different sorting algorithms: Insertion Sort, Selection...
In this project you will implement and experiment with three different sorting algorithms: Insertion Sort, Selection sort and Bubble Sort. The objective of this project is to understand the relation between the theoretical asymptotic complexities (Big-O) computed in class and the actual running times for different kinds of input. The enclosed source file main.cpp contains a program that reads two inputs: a letter specifying which sorting algorithm to use (I for InsertionSort , S for SelectionSort and B for BubbleSort),...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT