1. Introduction.

In this assignment, you are required to compute the average number of comparisons required by Bubble sort, Selection sort, Insertion sort, Quick sort, and Merge sort algorithms to sort arbitrary10-element integer arrays with different elements. Obviously, you can consider only the arrays that are permutations of numbers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 only.

For example, to compute the average number of comparisons required by Bubble sort, you need to apply the sorting algorithm to each of 10! = 3628800 permutations of 10 numbers to find the number of comparisons required in each case. Then you need to find the sum of all these numbers, and to divide the sum by 10.

2. Listing permutations.

Task 1. Recursive function.

This is a "hurdle" task. If you fail to complete it successfully you will get 0 marks for the whole assignment.

In this task you are required to write a C++ implementation of the recursive algorithm described below. The algorithm allows you to list one by one all permutations of the numbers 1, 2, ..., n (n is a positive integer).

The algorithm should be implemented as a recursive function with the following header:

bool nextPermutation(int array[], int arraySize)

The function receives an integer array argument which is a permutation of integers 1, 2, ..., n. If there is a "next" permutation 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 does not change the array.

Here is a description of the recursive algorithm you need to implement:

1. The first permutation is the permutation represented by the sequence (1, 2, ..., n).

2. The last permutation is the permutation represented by the sequence (n, ..., 2, 1).

3. If a₁ ,...,a_n is an arbitrary permutation, then the "next" permutation is produced by the following procedure:

(i) If the maximal element of the array (which is n) is not in the first position of the array, say n = a where i > 1 , then swap a_i and a_i-1. This will give you the "next" permutation in this case.

(ii) If the maximal element of the array is in the first position, so n = a₁ , then to find the "next" permutation to the permutation

(a₁,...,a_n), first find the "next" permutation to

(a₂,...,a_n), and then add a₁ to the end of thus obtained array of (n-1) elements.

(iii) Consecutively applying this algorithm to permutations starting from (1, 2, ..., n), you will eventually list all n! possible permutations. The last one will be (n, ..., 2, 1).

For example, below is the sequence of permutations for n = 3, listed by the described algorithm:

(0 1 2) ; (0 2 1) ; (2 0 1) ; (1 0 2) ; (1 2 0) ; (2 1 0)

Task 2. Iterative version

Using the recursive algorithm, described in the previous section, develop an iterative method having the same functionality as the recursive nextPermutation method.

Task 3. Adding counters to the sorting functions.

Create a class SortingFunctions. This class should contain modified versions of the bubbleSort, insertionSort, selectionSort, quickSort, and mergeSort functions discussed in the lectures.

The modification means adding counters to the sorting methods that count the number of comparisons made by each of the functions during sorting.

Task 4. The main function

In the main function you should compute the average numbers of comparisons required by bubbleSort, insertionSort, selectionSort, quickSort, and mergeSort functions to sort 10-element integer array containing elements 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.