Question

1 Lab: Sorting
This lab will introduce you to some basic sorting algorithms. There will be three algorithms included in the
lab Quicksort, Mergesort, and Heapsort. Quicksort will already be completed for you, it is there for you to
refernce. Merge and Heap will need to be completed.
2 Lab: Assignment
Complete the functions heapify and mergesort. DO NOT change main or the function declarations. Start
with a MAXSIZE to be set to 100 (defined up top) to ensure you are sorting correctly, you can uncomment
the print statements in main. Make sure your re-comment out the print statements after you ensure you are
sorting correctly. Once you are sorting correctly increase MAXSIZE up to 100,000 and run it again.
• Mergesort is missing the RECURSIVE calls
• Mergesort also needs to put the recursive calls together
• heapify also needs RECURSIVE calls

Lab 6.cpp:

//Written by Danny Radosevich
//Code for UWYO COSC 2030
//Lab6

#include <random>
#include <ctime>
#include <cstdlib>
#include <iostream>
#include <chrono>

using namespace std;

#define MAXSIZE 100000

//sorting
//function declarations
int partition(int arr[], int low, int high);
void quickSort(int quick[],int low, int high);
void merge(int arr[], int left, int mid, int right, int size);
void mergeSort(int merge[], int left, int right, int size);
void heapSort(int heap[], int size);
void heapify(int arr[],int size, int index);

int main()
{
//for loop to get an illsorted array
int heap[MAXSIZE];
int merge[MAXSIZE];
int quick[MAXSIZE];
srand(unsigned(time(NULL)));
for(int i = 0; i<MAXSIZE;i++)
{
//set all three arrays to the same thing
int temp = rand()%(10*MAXSIZE);
heap[i] = temp;
merge[i] = temp;
quick[i] = temp;
}
//make sure the arrays are the same, so we can best test which is most efficient
/*
for(int i = 0; i<MAXSIZE;i++)
{
cout<<heap[i]<<"\t"<<merge[i]<<"\t"<<quick[i]<<endl;
}*/
//time heap sort
std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now();
heapSort(heap,MAXSIZE);
std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now();
std::chrono::duration<double> time_span = std::chrono::duration_cast<std::chrono::duration<double> >(t2 - t1);
cout << "heapSort took " << time_span.count() << " seconds."<<endl;

//time merge sort
t1 = std::chrono::high_resolution_clock::now();
mergeSort(merge,0, MAXSIZE -1, MAXSIZE);
t2 = std::chrono::high_resolution_clock::now();
time_span = std::chrono::duration_cast<std::chrono::duration<double> >(t2 - t1);
cout << "mergeSort took " << time_span.count() << " seconds."<<endl;

//time quick sorting
t1 = std::chrono::high_resolution_clock::now();
quickSort(quick, 0, MAXSIZE -1);
t2 = std::chrono::high_resolution_clock::now();
time_span = std::chrono::duration_cast<std::chrono::duration<double> >(t2 - t1);
cout << "quickSort took " << time_span.count() << " seconds."<<endl;

//print the new arrrays
/*
for(int i = 0; i<MAXSIZE;i++)
{
cout<<heap[i]<<"\t"<<merge[i]<<"\t"<<quick[i]<<endl;
}*/
return 0;
}

int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int lowIndex = (low-1);
for(int i = low; i< high; i++)
{
if(arr[i]<=pivot)
{
lowIndex++;
swap(arr[lowIndex], arr[i]);
}
}
swap(arr[lowIndex+1],arr[high]);
return (lowIndex+1);
}

void quickSort(int quick[],int low, int high)
{
if(low<high)
{
int partIndex = partition(quick,low,high);

//sort elements based on the partition
quickSort(quick,low, partIndex-1);
quickSort(quick,partIndex+1, high);
}
}

void merge(int arr[], int left, int mid, int right, int size)
{
int i, j, k = 0; //control variables for later
int sizeOne = mid -left +1; //size of left arrays
int sizeTwo = right - mid;//size of right array

//arrays for each size
//int *a = new int[variable_int];
int *leftArray = new int[sizeOne];
int *rightArray = new int[sizeTwo];

//copy the data into the arrays
for(i = 0; i<sizeOne; i++ )
{
leftArray[i] = arr[i+left];
}
for(j = 0; j<sizeTwo; j++)
{
rightArray[j] = arr[mid+1+j];
}

i = 0;
j = 0;
k = left;

while(i<sizeOne && j<sizeTwo && k<size)
{
if(leftArray[i]<=rightArray[j])
{
arr[k] = leftArray[i];
i++; //only increment when we use an element
}
else
{
arr[k] = rightArray[j];
j++;//same as above
}
k++;
}

//now we need to clear the remainder in the arrays
while(i<sizeOne && k <size)
{
arr[k] = leftArray[i];
i++;
k++;
}
while(j<sizeTwo && k <size)
{
arr[k] = rightArray[j];
j++;
k++;
}
delete[] leftArray;
delete[] rightArray;
}
void mergeSort(int toMerge[], int left,int right, int size)
{
if(left<right)
{
//find the mid point
int mid = left+(right-left)/2;

//recursivley call mergeSort
//YOUR CODE GOES HERE
//YOUR CODE GOES HERE
//but the whole thing together
//YOUR CODE GOES HERE
}
}

//Heap sort functions
void heapify(int arr[], int size, int index)
{
int largestPos = index; //set the largest as the root
int leftChildPos = 2*index+1; //get the left child with offset
int rightChildPos = 2*index+2; //get right child by offset

//check if left child in bounds and larger than root
if(leftChildPos<size && arr[leftChildPos]>arr[largestPos])
{
largestPos = leftChildPos; //we found a new largest
}
if(rightChildPos<size && arr[rightChildPos]>arr[largestPos])
{
largestPos = rightChildPos; //we found a new largest
}
//check if the largest is no longer root (we switched)
if(largestPos != index)
{
//SWAP two elements in the array
//YOUR CODE GOES HERE
// Recursively heapify the affected sub-tree
//YOUR CODE GOES HERE
}

}
void heapSort(int heap[], int size)
{
//the rearranges the array
for(int i = size/2 - 1; i>=0; i--)
{
//call heapify
heapify(heap,size,i);
}
for(int i = size-1; i>=0; i--)
{
// Move current root to end
swap(heap[0], heap[i]);
// call max heapify on the reduced heap
heapify(heap, i, 0);
}
}

Answer 1

#include <random>
#include <ctime>
#include <cstdlib>
#include <iostream>
#include <chrono>

int part(int a[], int l, int h);
void Qsort(int q[],int l, int h);
void m1(int a[], int l, int m, int r);
void m1Sort(int m1[], int l, int r);
void hSort(int h3[], int size);
void h1(int a[],int size, int t);

int main()
{
int h3[MAXSIZE]; //set array
int m1[MAXSIZE]; //set array
int q[MAXSIZE]; //set array
srand(unsigned(time(NULL))); //set array
for(int i = 0; i<MAXSIZE;i++)
{
int temp = rand()%(10*MAXSIZE); //set all three array to the same thing
h3[i] = temp; //set all three array to the same thing
m1[i] = temp; //set all three array to the same thing
q[i] = temp; //set all three array to the same thing
}
std::chrono::high_resolution_clock::time_point t1 = std::chrono::high_resolution_clock::now();
hSort(h3,MAXSIZE);
std::chrono::high_resolution_clock::time_point t2 = std::chrono::high_resolution_clock::now();//time heap sorting
std::chrono::duration<double> time_span = std::chrono::duration_cast<std::chrono::duration<double> >(t2 - t1);//time heap sorting
cout << "heapSort took " << time_span.count() << " seconds."<<endl; //time heap sorting
//time merge sort
t1 = std::chrono::high_resolution_clock::now(); //time merge sort
m1Sort(m1,0, MAXSIZE -1); //time merge sort
t2 = std::chrono::high_resolution_clock::now();//time merge sort
time_span = std::chrono::duration_cast<std::chrono::duration<double> >(t2 - t1); //time merge sort
cout << "mergeSort took " << time_span.count() << " seconds."<<endl;
t1 = std::chrono::high_resolution_clock::now(); //time merge sorting
Qsort(q, 0, MAXSIZE -1); //time quick sorting
t2 = std::chrono::high_resolution_clock::now(); //time quick sorting
time_span = std::chrono::duration_cast<std::chrono::duration<double> >(t2 - t1); //time quick sorting
cout << "Quicksort took " << time_span.count() << " seconds."<<endl; //time quick sorting
return 0;
}

int part(int a[], int l, int h)//pertition
{
int pivot = a[h];//setting the pivot element
int id = (l-1);//setting last t
for(int i = l; i< h; i++)//travel through the aay
{
if(a[i]<=pivot)//if it's less than pivot
{
id++;//move point of l of pivot one head
swap(a[id], a[i]);//swap l with current value
}
}
swap(a[id+1],a[h]);//in the end it will move pivot to it's correct location
return (id+1);//sending pivot location in the aay
}

void Qsort(int q[],int l, int h)
{
if(l<h)
{
int pid = part(q,l,h);

//sort elements based on the part
Qsort(q,l, pid-1);
Qsort(q,pid+1, h);
}
}

void m1(int a[], int l, int m, int r)
{
int size=l+r-1;
int i, j, k = 0; //control variables for later
int n1 = m -l +1; //size of l aays
int n2 = r - m;//size of r aay

//int *a = new int[variable_int];
int *laay = new int[n1]; //aays for each size
int *raay = new int[n2]; //aays for each size
for(i = 0; i<n1; i++ ) //copy the data into the aays
{
laay[i] = a[i+l];
}
for(j = 0; j<n2; j++) //copy the data into the aays
{
raay[j] = a[m+1+j];
}
i = 0;
j = 0;
k = l;

while(i<n1 && j<n2 && k<size)//iterate until one of the aay is traversal full
{
if(laay[i]<=raay[j])
{
a[k] = laay[i];
i++; //only increment when we use an element
}
else
{
a[k] = raay[j];
j++;//same as above
}
k++;
}
while(i<n1 && k <size) //now we need to clear the remainder in the aays
{
a[k] = laay[i];
i++;
k++;
}
while(j<n2 && k <size)
{
a[k] = raay[j];
j++;
k++;
}
delete[] laay;
delete[] raay;
}
void m1Sort(int tom1[], int l,int r)
{
if(l<r)
{
int m = (l + r) / 2; // Find the middle point
m1Sort(tom1, l, m); // Sort first and second halves
m1Sort(tom1, m + 1, r); // Sort first and second halves
m1(tom1, l, m, r);// m1 the sorted halves
}
}
void h1(int a[], int size, int t){//h3 sort functions
int largestPos = t; //set the largest as the root
int lChildPos = 2*t+1; //get the l child with offset
int rChildPos = 2*t+2; //get r child by offset
if(lChildPos<size && a[lChildPos]>a[largestPos])//check if l child in bounds and larger than root
{
largestPos = lChildPos; //we found a new largest
}
if(rChildPos<size && a[rChildPos]>a[largestPos])
{
largestPos = rChildPos; //we found a new largest
}
if(largestPos != t) //check if the largest is no longer root
{
swap(a[t], a[largestPos]);
h1(a, size, largestPos); // Recursively h1 the affected sub-tree
}
}
void hSort(int h3[], int size)
{
for(int i = size/2 - 1; i>=0; i--) //the reaanges the aay
{
h1(h3,size,i);//call h1
}
for(int i = size-1; i>=0; i--)
{
swap(h3[0], h3[i]);// Move current root to end
h1(h3, i, 0); // call max h1 on the reduced h3
}
}

If you found this answer helpful please give a thumbs up.