Permutations & Sorting Algorithms - IT Assignment Help

Assignment Task

ASSIGNMENT 1. PERMUTATIONS & SORTING ALGORITHMS

Note: This is a programming assignment. As the programming language for this assignment, you can have to use Java

Introduction.
When a sorting algorithm sorts an array of comparable elements, it may compare some elements of the array, move them, create auxiliary arrays, etc. It is very difficult or even impossible to take into account all factors that may affect a sorting algorithm’s performance, i.e., the running time and the required memory. Therefore, to evaluate the performance of a sorting algorithm, simplified approaches are used, where only a few most important factors are taken into account.
In this assignment you are required to compute the (average) number of element comparisons performed by various sorting algorithms. This is one of the most important factors that affects the (average) running time of a sorting algorithm.
More specifically, you are required to compute the average number of element comparisons performed by Quicksort, Mergesort and Insertionsort algorithms when they sort 10-element integer arrays with different elements. Without loss of generality, we can consider only 10-element arrays that are sequences (in what follows we call them permutations) of integers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. There are exactly 10! = 3628800 (ten factorial) such permutations.
In order to compute the average number of comparisons performed by a particular sorting algorithm, you must apply the algorithm to each of 3628800 permutations of the 10 numbers, compute the number of element comparisons in each case, add up all these numbers and divide the sum by 3628800.

1.Listing all permutations of n numbers.
In this section you are required to write a Java (or C) implementation of the recursive algorithm described below. Using this algorithm, you will be able to generate, one by one, all permutations of n elements.

Task 1.1. Recursive algorithm next Permutation.
The algorithm should be implemented as a recursive function (method) named nextPermutation.
The function receives an argument, which is an array of integers that represents a permutation. The function may change the received array (to the “next permutation”) and return true (or 1 in C) or it can leave the array unchanged and return false (0 in C).

Here is the description of the recursive algorithm, next Permutation, that you are required to implement:
If (a1,…,an) is an arbitrary permutation of the numbers 1,2,…,n, then:
If the maximal element of the permutation (which is n) is not the first element of the permutation, say, n = ai, then swap ai and ai-1 and return true(1).
If the maximal element of the permutation is in the first position, i.e. n = a1, call nextPermutation algorithm for the smaller (n-1)-element permutation (a2,…,an) (this is a recursive step!) and:
if this call returns true (1), append a1 to the obtained permutation of (n-1) elements and return true (1).
else return false (0).

This algorithm will help you in the Main Task to consecutively generate all n! permutations of numbers 1,…,n, as follows:
Start with the permutation a = (1,2,…,n).
Call the function nextPermutation(a) consecutively (in a loop) while it returns true.
Stop when nextPermutation(a) returns false (0).
By the time when nextPermutation stops the variable a will have assumed one by one all possible permutations of n elements.

Example. Below is the sequence of 3! = 6 permutations for n = 3, obtained by consecutively applying nextPermutation: (1,2,3),(1,3,2),(3,1,2),(2,1,3),(2,3,1),(3,2,1).
For example, nextPermutation applied to (1,2,3) changes it to (1,3,2) and returns true, applied to (1,3,2) changes it to (3,1,2) and returns true, applied to (3,1,2) changes it to (2,1,3) and returns true, applied to (2,1,3) changes it to (2,3,1) and returns true, applied to (2,3,1) changes it to (3,2,1) and returns true, applied to (3,2,1) does not change it and returns false.
 

Task 1.2. Iterative algorithm next PermutationIter.
Using the recursive algorithm described in the previous section, develop an iterative function (method) with the same functionality as nextPermutation. Recall that the iterative function should not contain recursive calls – it uses only looping constructs.
Recommendation. Attempt this task after you have completed all other tasks.

Adding counters to Quicksort, Mergesort and Insertionsort algorithms.
You are required to modify C/Java code for Quicksort, Mergesort and Insertionsort algorithms to be able to count the number of element comparisons performed by each of them.
The original Quicksort, Mergesort and Insertionsort algorithms and their C implementations are discussed in Lecture 3.1.
Recommendation. Check that your modified sorting algorithms count element comparisons correctly by running them on small arrays of size 3 or 4, where the results can be computed by hand.

The main function (method).

In this task you are required to compute and print out the average number of element comparisons for each of the Quicksort, Mergesort and Insertionsort algorithms to sort 10-element integer arrays containing the elements 1,2,3,4,5,6,7,8,9,10.
Note. Use the recursive nextPermutation when generating the permutations.
Recommendation. In your main function, use a variable, n, for the array size instead of a hard-coded number 10. This will allow you to verify the correctness of your program on small instances, e.g., n = 3 or n = 4, where the average number of comparisons can be computed by hand.

This IT Assignment has been solved by our IT experts at My Uni Paper. Our Assignment Writing Experts are efficient to provide a fresh solution to this question. We are serving more than 10000+ Students in Australia, UK & US by helping them to score HD in their academics. Our Experts are well trained to follow all marking rubrics & referencing style.
Be it a used or new solution, the quality of the work submitted by our assignment experts remains unhampered. You may continue to expect the same or even better quality with the used and new assignment solution files respectively. There’s one thing to be noticed that you could choose one between the two and acquire an HD either way. You could choose a new assignment solution file to get yourself an exclusive, plagiarism (with free Turnitin file), expert quality assignment or order an old solution file that was considered worthy of the highest distinction.