Question

In: Computer Science

Create the following algorithms in c++ as a call to method: 1. HeapSort 2. QuickSort 3....

Create the following algorithms in c++ as a call to method:

1. HeapSort

2. QuickSort

3. MergeSort

Solutions

Expert Solution

1. HeapSort


// 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(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]);

cout << "Given array is \n";
printArray(arr, n);
  
   heapSort(arr, n);

   cout << "Sorted array is \n";
   printArray(arr, n);
}

output

2. QuickSort

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

void swap(int* ele1, int* ele2) // swapping the elements
{
int t = *ele1;
*ele1 = *ele2;
*ele2 = t;
}
  

int partition (int a[], int beg, int end) // partitioning the elements
{
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);
}
  

void quickSort(int a[], int beg, int end) // sorting the elements based on partitioning index
{
if (beg < end)
{
  
int pIndex = partition(a, beg, end);
  
quickSort(a, beg, pIndex - 1);
quickSort(a, pIndex + 1, end);
}
}
  
void display(int a[], int n) // displaying the elements of the array
{
  
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;
}

output


  

3. Mergesort

// C++ program for Merge Sort
#include<iostream>
using namespace std;

// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{
   int n1 = m - l + 1;
   int n2 = r - m;

   // Create temp arrays
   int L[n1], R[n2];

   // Copy data to temp arrays L[] and R[]
   for(int i = 0; i < n1; i++)
       L[i] = arr[l + i];
   for(int j = 0; j < n2; j++)
       R[j] = arr[m + 1 + j];

   // Merge the temp arrays back into arr[l..r]
  
   // Initial index of first subarray
   int i = 0;
  
   // Initial index of second subarray
   int j = 0;
  
   // Initial index of merged subarray
   int k = l;
  
   while (i < n1 && j < n2)
   {
       if (L[i] <= R[j])
       {
           arr[k] = L[i];
           i++;
       }
       else
       {
           arr[k] = R[j];
           j++;
       }
       k++;
   }

   // Copy the remaining elements of
   // L[], if there are any
   while (i < n1)
   {
       arr[k] = L[i];
       i++;
       k++;
   }

   // Copy the remaining elements of
   // R[], if there are any
   while (j < n2)
   {
       arr[k] = R[j];
       j++;
       k++;
   }
}

// l is for left index and r is
// right index of the sub-array
// of arr to be sorted */
void mergeSort(int arr[], int l, int r)
{
   if (l < r)
   {
      
       // Same as (l+r)/2, but avoids
       // overflow for large l and h
       int m = l + (r - l) / 2;

       // Sort first and second halves
       mergeSort(arr, l, m);
       mergeSort(arr, m + 1, r);

       merge(arr, l, m, r);
   }
}

// UTILITY FUNCTIONS
// Function to print an array
void printArray(int A[], int size)
{
   for(int i = 0; i < size; i++)
       cout << A[i] << " ";
}

// Driver code
int main()
{
   int arr[] = { 12, 11, 13, 5, 6, 7 };
   int arr_size = sizeof(arr) / sizeof(arr[0]);

   cout << "Given array is \n";
   printArray(arr, arr_size);

   mergeSort(arr, 0, arr_size - 1);

   cout << "\nSorted array is \n";
   printArray(arr, arr_size);
   return 0;
}

Output


Related Solutions

Related to HeapSort (a) Construct a heap for the following array of numbers:         8 1 2...
Related to HeapSort (a) Construct a heap for the following array of numbers:         8 1 2 3 5 6 4 7 10 9       Show the array after the insertion of each element into the heap. (b) Use your heap to sort the array. Show the resulting heap after the extraction of each maximum.
create a power series for 5/2x-3 c=-3 create a power series for 5/(2x-3)^2 c=-3
create a power series for 5/2x-3 c=-3 create a power series for 5/(2x-3)^2 c=-3
out of the following four: 1.Bubble sort 2. Insertion sort 3. Quicksort 4. Mergesort a. Which...
out of the following four: 1.Bubble sort 2. Insertion sort 3. Quicksort 4. Mergesort a. Which sorting methods perform best and worst for data sizes ≥ 25,000 when the input data is random? b. Which sorting methods perform best and worst for data sizes ≥ 25,000 when the input data is 90% sorted? c. Which sorting methods perform best and worst for data sizes ≥ 25,000 when the input data is reverse sorted? d. Which sorting methods perform best and...
out of the following four: 1.Bubble sort 2. Insertion sort 3. Quicksort 4. Mergesort a. Which...
out of the following four: 1.Bubble sort 2. Insertion sort 3. Quicksort 4. Mergesort a. Which sorting methods perform best and worst for data sizes ≥ 25,000 when the input data is random? b. Which sorting methods perform best and worst for data sizes ≥ 25,000 when the input data is 90% sorted? c. Which sorting methods perform best and worst for data sizes ≥ 25,000 when the input data is reverse sorted? d. Which sorting methods perform best and...
Let C be the following matrix: C=( 1 2 3 -2 0 1 1 -2 -1...
Let C be the following matrix: C=( 1 2 3 -2 0 1 1 -2 -1 3 2 -8 -1 -2 -3 2 ) Give a basis for the row space of Cin the format [1,2,3],[3,4,5], for example.
in C++ We are going to implement the following scheduling algorithms 1. First-Come First-Served (FCFS) 2....
in C++ We are going to implement the following scheduling algorithms 1. First-Come First-Served (FCFS) 2. Shortest Remaining Time First (SRTF) 3. Highest Response Ratio Next (HRRN) 4. Round Robin, with di_erent quantum values (RR) We are interested to compute the following metrics, for each experiment: _ The average turnaround time _ The total throughput (number of processes done per unit time) _ The CPU utilization _ The average number of processes in the ready queue The simulator needs to...
a. Using Matlab scripts create the following matrices (???1 and ???2) ???1 = [ 3 2...
a. Using Matlab scripts create the following matrices (???1 and ???2) ???1 = [ 3 2 −3 6 7 4 3 −6 7 ], ???2 = [ 2 1 7 3 3 9 −6 6 1 ]    b. Write code to add the second row of ???1 to the third row of ???2 and store results in the first row of ???1. c. Write code to add the second column of ???1 with the third column of ???2 and...
Create a flowchart using the bisection method when a=2 and b=5 and y=(x-3)3-1
Create a flowchart using the bisection method when a=2 and b=5 and y=(x-3)3-1
trace by using quicksort on the array : 4 6 5 3 2 7 1 using...
trace by using quicksort on the array : 4 6 5 3 2 7 1 using 7 as the pivot
Let x3 be the following vector: x3 <- c(0, 1, 1, 2, 2, 2, 3, 3,...
Let x3 be the following vector: x3 <- c(0, 1, 1, 2, 2, 2, 3, 3, 4) Imagine what a histogram of x3 would look like. Assume that the histogram has a bin width of 1. How many bars will the histogram have? Where will they appear? How high will each be? When you are done, plot a histogram of x3 with bin width = 1, and see if you are right. I need code help R programming
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT