Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Expected Values From Bubble Sort

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

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


1 2



77% Solution Ratio

BrehamPieEarliest, 6M ago

BrehamPieFastest, 0.0s

BrehamPieLightest, 0 B

CPSCR_PiratesShortest, 93B


Login to submit


The probability that one particular permutation will show up is 1/n!. So for smaller cases, generati...

Related Contests

Toph uses cookies. By continuing you agree to our Cookie Policy.