Expected Values From Bubble Sort

TarifEzaz Criterion 2021 Round 10
Limits 1s, 512 MB

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)
        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 $\textbf N$ numbers is an ordered sequence of distinct integers from $\textbf 1$ to $\textbf N$.

Given a permutation of $\textbf N$ 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 $\textbf{N}$ $(1\leq N \leq 11)$, 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 $\textbf{1}$. The greatest common divisor of two or more integers is the greatest integer that divides each of those given integers.


1 2


Login to submit.


77% Solution Ratio
BrehamPieEarliest, Feb '21
BrehamPieFastest, 0.0s
BrehamPieLightest, 0 B
CPSCR_PiratesShortest, 93B
Toph uses cookies. By continuing you agree to our Cookie Policy.