Assignment 2 ## Task 1

# Assignment 2

## Task 1

Computing the execution time of functions is not a very effective method to compare the efficiency of algorithm, but it can provide some insight about the time efficiency of different algorithms. The following link provides some methods to calculate the execution time of a function or part of a code: https://www.geeksforgeeks.org/measure-execution-time-function-cpp/Links to an external site.

In this question, you are asked to implement the following sorting methods and calculate their execution time for some test cases.

Sorting Methods:

Modified Bubble Sort (sorting stops as soon as there is no swapping in one pass)

Selection Sort

Insertion Sort

Merge Sort

Quick Sort (with random pivot)

Heap Sort

Balanced Binary Search Tree (where you create a balanced BST)

Radix Sort (with counting sort as the subroutine)

Test your sorting methods for an integer array (or vector) of size 20000 according the following test cases:

Array is filled with random numbers between 0 and RAND_MAX (use rand() function).

An already sorted array

An array that is reversely sorted

Array is filled with random number between 0 to 5 (use rand()%6)

Provide the implementation for all the sort functions and their testing. Compare the execution time of each sorting method for each test case and show them in a table.

## Task 2

Please read the descriptions in the given link and implement your code (all the parts are required):

https://www2.cs.sfu.ca/~mitchell/cmpt-225/2016-Fall/assigns/3-heaps/3-heaps.html

## Task 3

Please read the descriptions in the given link and implement your code (all the parts are required):

https://www2.cs.sfu.ca/~mori/courses/cmpt225/assignments/assignment-4.html

For the assignment submission, put all your codes in a word or pdf file and just submit one file. Your codes should be commented with proper pre- and post-conditions. Use exception wherever necessary. Make sure to provide sub-headings for each part of the assignment in your submission for easier marking. For Questions 2 and 3 you should separate your classes into cpp and h files. Each Question should be done in a separate project.