Hi, I don\'t know how to do this sorting question. I\'d be appreciate if you can
ID: 3844826 • Letter: H
Question
Hi, I don't know how to do this sorting question. I'd be appreciate if you can help me. The instructions are shown below In this assignment, your task is to create and perform an experiment that compares the number of comparisons done by these four different sorting algorithms: 1. The standard C++ STL sort function (not the C gsort function!). of course, this sort is already pre-made, so you don't need to implement it. But you do need to find a way to count the number of comparisons it does. 2. selection sort, implemented as a priority queue based on an unordered vector. 3. Insertion sort, implemented as a priority queue based on a sorted Vector. 4. Heapsort, implemented as a priority queue based on a heap. You must implement sorts 2, 3, and 4 yourself, and they should each work like this: Pre-condition: Post-condition v is re-arran into ascending sorted order ged void sort (veetorkint 6 v) Step 1: read v into an empty priority queue Step 2: read all the elements from priority queues from smallest to biggest back into v Important: for selection sort and insertion sort, don't use a traditional implementation (which is not based on a priority queue). Use this (unusuall) priority queue implementation. You will need to incluExplanation / Answer
/* C++ Program - Selection Sort */
#include<iostream.h>
#include<conio.h>
void main()
{
clrscr();
int size, arr[50], i, j, temp;
cout<<"Enter Array Size : ";
cin>>size;
cout<<"Enter Array Elements : ";
for(i=0; i<size; i++)
{
cin>>arr[i];
}
cout<<"Sorting array using selection sort... ";
for(i=0; i<size; i++)
{
for(j=i+1; j<size; j++)
{
if(arr[i]>arr[j])
{
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
cout<<"Now the Array after sorting is : ";
for(i=0; i<size; i++)
{
cout<<arr[i]<<" ";
}
getch();
}
/* C++ Program- HeapSort */
#include <iostream>
using namespace std;
void max_heapify(int *a, int i, int n)
{
int j, temp;
temp = a[i];
j = 2*i;
while (j <= n)
{
if (j < n && a[j+1] > a[j])
j = j+1;
if (temp > a[j])
break;
else if (temp <= a[j])
{
a[j/2] = a[j];
j = 2*j;
}
}
a[j/2] = temp;
return;
}
void heapsort(int *a, int n)
{
int i, temp;
for (i = n; i >= 2; i--)
{
temp = a[i];
a[i] = a[1];
a[1] = temp;
max_heapify(a, 1, i - 1);
}
}
void build_maxheap(int *a, int n)
{
int i;
for(i = n/2; i >= 1; i--)
{
max_heapify(a, i, n);
}
}
int main()
{
int n, i, x;
cout<<"Enter no of elements of arrayn";
cin>>n;
int a[20];
for (i = 1; i <= n; i++)
{
cout<<"Enter element"<<(i)<<endl;
cin>>a[i];
}
build_maxheap(a,n);
heapsort(a, n);
cout<<"nnSorted Arrayn";
for (i = 1; i <= n; i++)
{
cout<<a[i]<<endl;
}
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.