Bubble sort is a sorting algorithm that can sort an array of numbers in increasing order. In each of its iterations, it starts at the first element of the array and compares it with the adjacent element. If two adjacent elements are not in increasing order, they get swapped. The iteration continues from the first element to the second last element. The iteration ends when the last element is reached. A new iteration begins only if there was at least one swapping in the last iteration. The pseudocode is as follows:
procedure bubbleSort(A : list of sortable items) n := length(A) repeat swapped := false for i := 1 to n-1 inclusive do /* if this pair is out of order */ if A[i-1] > A[i] then /* swap them and remember something changed */ swap(A[i-1], A[i]) swapped := true end if end for until not swapped end procedure
Pseudocode source: Wikipedia
A permutation of numbers is an ordered sequence of distinct integers from to .
Given a permutation of integers, where any particular permutation is equally likely, what is the expected number of swaps that will be required to sort that permutation in increasing order using Bubble sort?
The only line of the input will have an integer , the size of the array.
Output two integers, the numerator and denominator of the answer so that the greatest common divisor of numerator and denominator is . The greatest common divisor of two or more integers is the greatest integer that divides each of those given integers.
Login to submit
The probability that one particular permutation will show up is 1/n!. So for smaller cases, generati...