ITECH 7603 ADVANCED PROGRAMMING SCHOOL OF ENGINEERING AND INFORMATION TECHNOLOGY FEDERATION UNIVERSITY ASSIGNMENT 1 0. Introduction. In this assignment you are required to compute the average number of element comparisons required by the Quicksort, and Mergesort algorithms to sort a nelement integer array with different elements, where n is a positive integer. Without loss of generality, you can assume that the arrays to be sorted contain only the integers 1, 2, …, n. In other words, to evaluate the performance of a sorting algorithm you need to sort all the possible permutations of the numbers 1,2,…,10 using this algorithm and count how many element comparisons it takes in total. By dividing the total number of the comparisons by the total number of the permutations you will obtain the average number of element comparisons required by the sorting method to sort an array of n elements. For example, to compute the average number of element comparisons required by Quicksort to sort a 10-element array, you need to apply the sorting algorithm to each of the 10! = 3628800 permutations of the 10 numbers to find the number of comparisons required in each case. Then you divide the total number of the comparisons by 10!. 1. Listing permutations. Task 1.1. Recursive function that allows to list all the permutations of n numbers, 1,2,…,n. (5 marks). First, you are required to develop a C++ function that allows you to list all possible sequences (permutations) of the numbers 1, 2, … , n. It should be implemented as a recursive function with the following header: bool nextPermutation(int array[], int arraySize) The function receives an integer array as an argument, which is a permutation of the integers 1, 2, … , n. If there is the "next permutation" (the meaning is explained in the algorithm description below) to the permutation represented by the array, then the function returns true and the array is changed so that it represents the "next" permutation. If there is no "next permutation", the function returns false and leaves the array unchanged. Here is a description of the recursive algorithm, RA: If (a1, a2, … , an) is an arbitrary sequence (array) of distinct integers then the "next permutation" is produced by the following procedure: (i) If the maximal element of the sequence, max, is not the first element of the sequence, say max = ai, where i > 1, then to produce the "next permutation" you swap ai and ai-1, then stop and return true. (ii) If the maximal element of the sequence is in the first position, apply the RA to the (n-1)-element sequence (a2, … , an). If RA returns false on the sequence (a2, … , an), do not change the initial sequence, stop and return false. Else go to step (iii). ITECH 7603 ADVANCED PROGRAMMING SCHOOL OF ENGINEERING AND INFORMATION TECHNOLOGY FEDERATION UNIVERSITY (iii) Append a1 to the end of the sequence of (n-1) elements obtained in the previous step, stop and return true. (*) Note that RA is a recursive algorithm, with the base being any sequence of 1 element. In this case RA does not change anything and returns false. Now, to list all the permutations of the numbers 1, 2, …, n, you start with the permutation (1, 2, …, n) and apply the above algorithm (function nextPermutation) to it to produce the "next permutation". Then again, you apply nextPermutation function to thus produced permutation to obtain the next to the "next permutation". Continue this process of applying nextPermutation to the result of the previous application while it returns true. You stop when nextPermutation returns false. This procedure will list all the n! permutations of the numbers 1, 2, …, n (if you prove this fact rigorously, by mathematical induction, you will be awarded 2 bonus marks). Although this is not important for the implementation, note that the last permutation produced in this sequence is (n, …, 2, 1). And this is the only permutation that does not have the "next" permutation to it. Example. Below is the sequence of permutations for n = 3, produced by applying nextPermutation consecutively: (1 2 3); (1 3 2); (3 1 2); (2 1 3); (2 3 1); (3 2 1) So, the nextPermutation applied to (1 , 2, 3) produces (1, 3, 2), applied to (1 , 3, 2) produces (3, 1, 2), applied to (3, 1, 2) produces (2, 1, 3), etc. Task 2.2. Iterative version (2 marks). This is a difficult task, although awarded only two marks. Based on the recursive algorithm, described in the previous section, develop an iterative function with the same functionality as the recursive nextPermutation function. Recall, that the iterative function should not contain recursive calls – it uses only looping constructs. ITECH 7603 ADVANCED PROGRAMMING SCHOOL OF ENGINEERING AND INFORMATION TECHNOLOGY FEDERATION UNIVERSITY Task 3. Adding counters to the sorting functions (4 + 4 = 8 marks ). Develop modified versions of the quickSort and mergeSort functions that incorporate integer counters to accumulate the number of the element comparisons made by each of the functions during the sorting process. Implementations of quickSort and mergeSort functions are available in the lecture slides. You only need to incorporate the counters correctly. 4. The main function (5 marks). In the main function you should compute the average numbers of comparisons required by the quickSort, and mergeSort functions to sort 10- element integer array containing elements 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. ITECH 7603 ADVANCED PROGRAMMING SCHOOL OF ENGINEERING AND INFORMATION TECHNOLOGY FEDERATION UNIVERSITY Allocated Marks: See Course Description Due Date: See Course Description Please refer to the Course Description for information relating to late assignments and special consideration. Plagiarism: Please refer to the Course Description for information regarding Plagiarism. Assignment Submission: Assignments must be submitted by the due date and your assignment should be completed according to the General Guidelines for Presentation of Academic Work (http://www.ballarat.edu.au/aasp/student/learning_support/generalguide/). The following criteria will be used when marking of your assignment: • successful compilation • successful completion the required tasks • adherence to the guidelines provided • quality of code that adheres to the programming standards for the Course; including: • comments and documentation 1* code layout 2* meaningful variable names You are required to provide the following documentation, contained in an appropriate folder: • a statement of what has been completed and acknowledgement of the names of all people (including other students and people outside of the university) who have assisted you and details on what parts of the assignment that they have assisted you with 3* a printed copy of your code (this may be included as an Appendix). Please include this because we can provide more feedback this way In addition to submitting a printed copy of your written report into your tutor's assignment box, you should also submit the following using Moodle: • an electronic copy of your code. Zip up the project itself and submit with the name .zip • a copy of your report (surnameStudentIDAssign1.doc) including program code. ITECH 7603 ADVANCED PROGRAMMING SCHOOL OF ENGINEERING AND INFORMATION TECHNOLOGY FEDERATION UNIVERSITY Student ID: ___________________ Student Name:_______________________ Marks awarded/deducted based upon considerations outlined on previous page Recursive nextPermutation function 5 marks Iterative nextPermutation function 2 marks Modified mergeSort function (along with auxiliary methods) 4 marks Modified quickSort function (along with auxiliary methods) 4 marks The main function 5 marks Bonus marks 2 marks Marks deducted for badly commented or badly written code Total 20 + (2)