Programming Assignment 4 Solution

Question 1




(70 points)




In the le Sort.h all the di erent sorting algorithms that we talked about is implemented. Using q1.cpp you can see if your implementations pass the tests. The tests worked based on your implementations and we will check your algorithms too.




Complete the method isSorted. This method reads the input vector and check if it is sorted. What is the complexity of this algorithm?(10 points)



complete the method bubbleSort. Use bubble sort algorithm to sort the input vector. What is the time complexity of this algorithm?(10 points)



Complete the method selectionSort. Use selection sort algorithm to sort the input vector. What is the time complexity of this algorithm?(20 points)



Complete the method hybridSort. Write a hybrid sort that split the input into 4 parts, sort each part using quick sort and then merge all the parts together. If input vector is smaller than 16 you can use any other sort. (20 points)



In q1.cpp you have the code for measuring execution time for some sorting algorithms. Add the code to measure the time for all of sorting algorithms that are in Sort.h then draw a chart that shows time complexity of di erent algorithms based on their running time. Some algorithms with O(n2) can take a long time to nish sorting.(20 points)



Question 2




(30 points) A Min Binary Heap is a complete binary tree with every node value lower than it’s subtree node values. A complete binary tree can be represented using an array instead of creating a Node Structures with pointers using following rule -




The root element will be at arr[0].



For ith node, i.e., arr[i], the arr[(i-1)/2] is the parent node.



For ith node, i.e., arr[i], the arr[(2*i)+1] is the left child node.



For ith node, i.e., arr[i], the arr[(2*i)+2] is the right child node.



File MinHeap.h contains the class, attributes and functions of MinHeap and le q2_1.cpp is testing the code of MinHeap.h. Implement following functions in MinHeap.h le. (10 points)



void insertKey(int k) - Insert a new element in the min heap.



int extractMin() - Extract the minimum element from the min heap and re-construct the min heap.



void decreaseKey(int i, int newVal) - Decrease the element at index i to newVal and reconstruct the min heap.



void deleteKey(int i) - Delete the element at index i and reconstruct the min heap.



Sample output after executing q2_1.cpp - 2 4 1




There is no programming needed for this part. Draw the tree in your PDF le. (6.2 from the book, 5 points):



Show the result of inserting 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13, and 2, one at a time, into an initially empty binary heap.



Show the result of using the linear-time algorithm to build a binary heap using the same input.



Given an array of n integers, nd the kth smallest element from the array. In the le q2_3.cpp implement function named int kthSmallest(int arr[], int n, int k) that will return the kth smallest element from the array. (15 points)



Note: Time complexity of your algorithm should be less than O(nlog(n)). And O(nk) is greater than O(nlog(n)). Describe what is the complexity of the algorithm. Hint: Min Heap :)




Sample input/output after executing q2_3.cpp -




Enter the value of n: 5




Enter the value of k: 3




Enter n integers space separated: 5 4 3 1 2




Kth Smallest Integer: 3












































































3