[Math] Bubble Sort vs Shuttle Sort

algorithmssorting

When sorting a list of items, shuttle sort (the one taught in the A-Level Maths unit D1 by OCR, NOT Cocktail sort – see below) does no more than as many comparisons as bubble sort (they always do equal swaps, which is due to the nature of these algorithms). I wanted to know whether or not bubble sort could ever sort a list with fewer comparisons than shuttle sort.

I attempted to write a computer program to do it, but after getting both sorting algorithms to work but not an auto run through of inputs lists, I had to manually enter them…

The Shuttle sort I'm referring to is described as follows (laid out how the exam board lays it out):

1st pass: Compare the 1st and 2nd numbers in the list and swap if needed

2nd pass: Compare the 2nd and 3rd numbers in the list and swap if needed. If swapped, compare 1st and 2nd and swap if needed.

3rd pass: Compare 3rd and 4th number in the list and swap if needed. If swapped, compare 2nd and 3rd, swap if needed. If swapped, compare 1st and 2nd, swap if needed.

This process continues throughout the entire list.

Best Answer

To get the largest element in it's right place we need do perform $n-1$ comparisons so the total number of comparisons of a bubble sort is

$$B_n = n-1 + n-2 + \ldots + 2 + 1 = \frac{(n-1)n}{2}$$

Shuttle sort does a bubble sort on the first two elements, then on the first three elements and so on. When we are sorting in the $(k+1)$'th element $a_{k+1}$ we know that the first $k$ elements are already sorted so we can stop comparing elements when we hit an element that is equal to or smaller than $a_{k+1}$. This means that we only need at most one full pass through the list each time we add in another element giving us

$$S_n \leq 1 + 2 + 3 + \ldots + n-1 = B_n$$

The number of swaps will be the same in both cases.

Related Solutions

Average swaps needed for a random bubble sort algorithm

Let $S(n)$ be the symmetric group of the set $\{1,2,\dots, n\}$.

It acts on "words" of length $n$ with the letters $1,2,\dots$ taken each exactly once by permuting corresponding places. A permutation will be identified with its action / its result on the "first word" $12\dots n$. There are $n!$ such words, each is an anagram of the first word.

This answer computes explicitly and exactly for small values of $\bf n$ the mean time to reach the permutation $e=()=12\dots n$, which is the neutral element written in alternative notations, when performing a random walk starting from a random element in $S(n)$ / from an anagram. The steps of the random walk correspond to switching two adjacent places in the word.

For very small values, the structure is described, and computations are done easily by hand. However for bigger values, there is no chance. So a computer aided answer is given for those cases, so that we have exact answers from the linear systems extracted from the Markovian structure. My choice of a computer algebra system is sage, since open source and object oriented.

Here are some general conventions first, we try to use standard terminology. The group $S(n)$ is a Weyl group of type $A_{n-1}$, its simple reflections are $$ s_j = s(j) = (j, j+1)\ ,\qquad 1\le j< n\ . $$ (There are $(n-1)$ such reflections, this is also the index in the type.) Depending on the context, the notation $s(j)$ may be better (instead of $s_j$), because the index $j$ is the main feature, so it is not a good idea to show it smaller. Each permutation has a writing as a product of minimal length of these generators taken in a specific order. (There may be one or more such writings.) In case a (non-commutative) "word" $w\in S(n)$ (with alphabet having letters among the simple reflection) is $$ w = s_is_j\dots s_k\ , $$ we will alternatively write it as $$ w = s(i,j,\dots,k)\ , $$ and even - in case of no possible confusion - as $s(ij\dots k)$. In case we use this notation, minimal product representations should be used. (So $s(11)$ is not what we want to write.)

Note the (braid) relations $s(121)=s(212)$, $s(232)=s(323)$, and so on.

Computations will be done in sage. Sage has its own convention(s) to write permutations and work with them. Since below we use code to write down examples, i will use also these conventions. For instance, consider the permutation $p$ that brings the ordered list $(1,2,3,4,5,6,7,8,9)$ into the list $(1,2,3,8,5,6,7,4,9)$. Then we will use for $p$ also this representation as word, $p=123856749$.

On it we can action by the simple reflections from the left. For instance:

sage: W = SymmetricGroup(9)
sage: p = Permutation([1,2,3,8,5,6,7,4,9])
sage: W(p)
(4,8)
sage: s1 = W.simple_reflections()[1]
sage: s2 = W.simple_reflections()[2]
sage: s3 = W.simple_reflections()[3]
sage: s3 * W(p)
(3,8,4)
sage: (s3 * W(p)).tuple()
(1, 2, 8, 3, 5, 6, 7, 4, 9)
sage: # so 1 -> 1, 2 -> 2, 3 -> 8, 4 -> 3, 5 -> 5, 6 -> 6, 7 -> 7, 8 -> 4, 9 -> 9
sage: (s2*(s3 * W(p))).tuple()
(1, 8, 2, 3, 5, 6, 7, 4, 9)
sage: ((s2*s3) * W(p)).tuple()
(1, 8, 2, 3, 5, 6, 7, 4, 9)

sage: s7 = W.simple_reflections()[7]
sage: (s7*W(p)).tuple()
(1, 2, 3, 8, 5, 6, 4, 7, 9)

So this is a left action on "places". For this action, the composition is a composition of fuctions acting on places.
In order to make this convention work, note that $s_2s_3=(23)(34)$ is $(2,4,3)$.

There is an other convention, also the one i like, where the permutations are function, and their composition is a composition of functions. However, this is not what we want here. To have it explicitly:

sage: s2, s3, s2*s3
((2,3), (3,4), (2,4,3))

sage: s2(s3(4))
2
sage: (s2*s3)(4)
3

On $W=S(n)$ we have a (weak) Bruhat order. See also the Wiki page on the Bruhat order(s).

It is the order given by writing words $w\in W$ in terms of the simple reflection generators. For a simple reflection $s$ and a word $w$ the elements $w$ and $sw$ are in relation. If $w$ has a (i.e. at least one) minimal writing that starts with $s$, then we set $$ sw \prec w\ . $$ Else, prepending $s$ makes each writing "longer" and we define $$ w \prec sw\ . $$ Let $\le$ be the relation obtained by closing the relation $\prec$ to an order relation, the (weak left) Bruhat order we are working with. (We add transitivity, and reflexivity.)

With respect to this order, we have an oriented graph, the (oriented) Bruhat graph. Its vertices are the elements of $W=S(n)$, its edges are corresponding to the simple relations $sw\prec w$ or $w\prec sw$ (only one holds) from above. Its unoriented version is the graph we consider in the problem, so the Bruhat graph is this one below. Its edges have natural labels $s$, simple reflections, in order to move from one vertex to the other one one multiplies from the right with $s$. The "word length" either increases or decreases by one, $l(sw)=l(w)\pm 1$.

There are standard properties of this order. For instance, taking final subwords of a minimal word lead to Bruhat-smaller words.

Our problem is related to a random walk on this graph, each step having length one. The question asks for the expected time needed to entry the set $\{e\}$ consisting of the neutral element only.

Although simple, let us consider first the case $n=3$ in detail to illustrate the structural situation in other cases, where propositions are not so simple.

n = $\bf 3$

There are $6=3!$ elements in $S(3)$. We denote the two transpositions or simple reflections $(12)=213$ and $(23)=132$ by $s_1=s(1)$, and respectively $s_2=s(2)$. Each element can then be written in a minimal (length) fashion as a product of $s_1,s_2$. Explicitly: $$ \begin{aligned} () &= 123 = e = s()\ , \\ (12) &= 213 = s_1=s(1)\ , \\ (23) &= 132 = s_2=s(2)\ , \\ (132) &= 312 = (12)(23) = s_1s_2=s(1,2)=s(12)\ , \\ (123) &= 213 = (23)(12) = s_2s_1=s(2,1)=s(21)\ , \\ (13) &= 321 = s_1s_2s_1=s_2s_1s_2=s(1,2,1)=s(2,1,2)=s(121)=s(212)\ . \end{aligned} $$ (Some of the above lines have the meaning of an implicit notation.)

The corresponding Bruhat graph is:

        s()
       /   \
     2/     \1
     /       \ 
  s(2)       s(1)
   |           |
  1|           |2
   |           |
  s(12)      s(21)
    \         /
    2\       /1
      \     /
      s(121)

Let $N_w$ or $N(I)=N_w$ if $w=s(I)$, be the expected number of steps to go from the permutation $w$ to the neutral element $e$. Here, if $I$ is a multiindex choice of simple reflections, $I=(i,j,\dots,k)$ we denote by $s(I)=s_is_j\dots s_k$. Then we have the following system of equations to solve: $$ \left\{ \begin{aligned} N_e = N() &= 0\ ,\\ N(1) &= 1 + \frac 12N() + \frac 12 N(12)\ ,\\ N(2) &= 1 + \frac 12N() + \frac 12 N(21)\ ,\\ N(12) &= 1 + \frac 12N(1) + \frac 12 N(121)\ ,\\ N(21) &= 1 + \frac 12N(2) + \frac 12 N(121)\ ,\\ N(121) &= 1 + \frac 12N(12) + \frac 12 N(21)\ . \end{aligned} \right. $$ (In fact, we do not need to solve this system explicitly, we need only the value $\displaystyle \frac 1{3!}(\ N()+N(1)+N(2)+N(12)+N(21)+N(121)\ )$.)

var('x,x1,x2,x12,x21,x121');
solve( [x == 0, x1 == 1 + (x + x12)/2, x2 == 1 + (x + x21)/2,
        x12 == 1 + (x1 + x121)/2, x21 == 1 + (x2 + x121)/2, 
        x121 == 1 + (x12 + x21)/2, ],
        [x, x1, x2, x12, x21, x121] )

The solution is:

    [[x == 0, x1 == 5, x2 == 5, x12 == 8, x21 == 8, x121 == 9]]

And we build the sum $0+(5+5)+(8+8)+9=35$, so the expected mean is $\displaystyle\frac {35}6\approx 5.8333\dots$ .

From the above we want to extract only the "cellular" structure, there are four cells, coincidently corresponding here to the four possible lengths of a word. The cells and the transitions between them are as follows:

    s()

    A |
1/2 | | 1
    | V
    
s(1), s(2)

    A |
1/2 | | 1/2
    | V

s(12), s(21)

    A |
  1 | | 1/2
    | V

  s(121)

So we have to solve a simpler system, using $M_l$ for the cell with words of length $l$: $$ \left\{ \begin{aligned} N_0 &= 0\ ,\\ N_1 &= 1 + \frac 12 N_0 +\frac 12 N_2\ ,\\ N_2 &= 1 + \frac 12 N_1 +\frac 12 N_3\ ,\\ N_3 &= 1 + N_2\ . \end{aligned} \right. $$ Its solution is of course the "same" one, $N_0=0$, $N_1=5$, $N_2=8$, $N_3=9$, so counting each cell weighted corresponding to the number of its elements,

The next case is slightly more complicated.

n = $\bf 4$

There are $24=4!$ elements in $S(4)$. We have three simple reflections. The elements have the following representations (code and results):

sage: W = WeylGroup('A3')
sage: elements = list(W)
sage: elements.sort(key=lambda w: w.length())
sage: for w in elements:
....:     print(' = '.join([''.join([str(j) for j in word]) for word in w.reduced_words()]))
....: 

3
2
1
32
23
21
31 = 13
12
321
232 = 323
231 = 213
132 = 312
123
121 = 212
2321 = 3213 = 3231
2312 = 2132
1321 = 3212 = 3121
3123 = 1323 = 1232
1213 = 1231 = 2123
32132 = 21321 = 23121 = 23212 = 32312
12321 = 31231 = 13231 = 31213 = 13213 = 32123
12132 = 21323 = 23123 = 12312 = 21232
312312 = 213213 = 321232 = 312132 = 132132 = 323123 = 231213 = 212321 = 121321 = 321323 = 123212 = 123121 = 213231 = 231231 = 232123 = 132312

(The first empty line stays for the neutral element.) The "cells" are now harder to be isolated and shown. At the beginning there is no problem.

    ()
    
    A|
  1 || 1
    |V
    
  1, 2, 3

But now we have to separate

 1_________  __2__  _________3
 |         \/     \/         |
2|        1/\3   1/\3        |2
 V        /  \   /  \        V
21     12   13=31    32      23

The entry $13=31$ is not "like the other" length two entries, since it has two possible beginnings. From here, we know that each of the entries $21$, $12$; $23$, $32$ is connected to two words of lenght three, while $13=31$ connects to only one such entry in the Bruhat graph.

In length $3$ we have a similar separation. We show only how the entries connect to lower and higher length levels.

1\     /2 2\     /3      |3         |1      1\     /3      |2
  \   /     \   /        |          |         \   /        |
   \ /       \ /         |          |          \ /         |
   121       232        321        123         132        213
  =212      =323        / \        / \        =312       =231     
    |         |        /   \      /   \         |         / \      
    |         |      1/     \2  2/     \3       |        /   \    
    |3        |1                                |2     1/     \3

It is not easy to draw the graph. We have only a symmetry corresponding to $s_1\leftrightarrow s_3$ that we can use. Doing this, we still obtain some graph that can be traced back humanly. Each entry has now representatives shown in a single writing. Only some vertices are drawn.

         ____e____
        /         \
       /           \
      /             \
  1, 3___            2
   |     \           |
   |      \          |
   |       \         |
 21, 23     13  ____12, 32
   |  \      \ /       |
   |   \ _____X        |
   |    X      \       |
   |   / \      \      |
  121,/   123, 213    132
  323     321   |      |
   |     /  \   |      |
   |    /    \  |      |
   |   /      \ |      |
   1321,     1213,    2132
   1323      2321     /
    \         \ _____/
     \     ____X 
      \   /     \
     12132,    12321
     23212       /
        \       /
         \     /
          121321

This leads to a system with $15$ unknowns to be solved. I will solve the system with all $24$ equations using code. But it is good to see that the solutions respect this and only this symmetry! The code is as follows:

def expected_steps(n):
    W = WeylGroup(['A', n-1])
    w_list = list(W)
    w_list.sort(key=lambda w: w.length())
    
    for w in w_list:
        exec("var('x{}')".format(''.join([str(j) for j in w.reduced_word()])))
    
    class WE(object):
        """Associate to each w in W an instance with some more needed structure.
        WE is a short cut for Weyl element.
        """
        def __init__(self, w):
            self.w = w
            self.varname = 'x' + (''.join([str(j) for j in w.reduced_word()]))
            self.var = eval(self.varname)
    
    vars = [WE(w).var for w in w_list]
    eqs  = [ WE(W.one()).var == 0 ] \
           + [ WE(w).var == 1 + 1/(n-1) * sum([WE(s*w).var for s in W.simple_reflections()])
               for w in w_list if w != W.one()]
    
    sol = solve(eqs, vars, solution_dict=True)[0]
    return sol

Then sol = expected_steps(4) gives:

sage: sol
    {x: 0,
     x3: 625/28,
     x2: 341/14,
     x1: 625/28,
     x32: 981/28,
     x23: 981/28,
     x21: 981/28,
     x31: 405/14,
     x12: 981/28,
     x321: 1153/28,
     x232: 1081/28,
     x231: 274/7,
     x312: 274/7,
     x123: 1153/28,
     x121: 1081/28,
     x2321: 171/4,
     x2312: 621/14,
     x3121: 171/4,
     x1232: 171/4,
     x1231: 171/4,
     x23121: 1273/28,
     x12321: 629/14,
     x12312: 1273/28,
     x123121: 324/7}

So the expected number of steps needed to reach $e$ starting from a random element is:

sage: sum(sol.values())/factorial(4)
1019/28

The next case is more complicated, although the same code leads to a quick solution.

n = $\bf 5$

We get:

sage: 
sage: sol = expected_steps(5)
sage: sol
{x: 0,
 x3: 3860770457/31585785,
 x2: 3860770457/31585785,
 x4: 3656646373/31585785,
 x1: 3656646373/31585785,
 x32: 10793324539/63171570,
 x34: 1486245371/9024510,
 x23: 10793324539/63171570,

::::::::::::::::::::::::::::::

 x1234312: 6637368586/31585785,
 x23412312: 13606936667/63171570,
 x23423121: 13500639197/63171570,
 x23412321: 1355491084/6317157,
 x12342312: 1355491084/6317157,
 x12341231: 13500639197/63171570,
 x34123121: 13500639197/63171570,
 x12342321: 13419193339/63171570,
 x12343121: 13419193339/63171570,
 x12341232: 13500639197/63171570,
 x234123121: 6825812773/31585785,
 x123412312: 6825812773/31585785,
 x123423121: 88342141/410205,
 x123412321: 88342141/410205,
 x1234123121: 15737160/72611}
sage:

I see no way to organize combinatorially the values obtained without a deep (group-theoretical) insight. For instance, the common denominator is:

sage: lcm([val.denominator() for val in sol.values() if val])
63171570
sage: ZZ(_).factor()
2 * 3 * 5 * 7 * 11 * 23 * 29 * 41

The mean expectation is:

sage: sum(sol.values())/120
73483980061/379029420

One observation we make is that the expected number of steps to go from $w$ to $e$ is the same as when we go from $w^{-1}$ to $e$.

n = $\bf 6$

The case is even more complicated from the combinatorial point of view. However the linear algebra exercise is still easy for the computer.

sage: sol = expected_steps(6)
sage: sum(sol.values()) / factorial(6)
1105216051055620235300660929/1023883272960409990968840

sage: _.n()
1079.43559607146

We can still hope to see some structure from the factorization of the denominator. But...

sage: QQ(sum(sol.values()) / factorial(6)).denominator()
1023883272960409990968840
sage: QQ(sum(sol.values()) / factorial(6)).denominator().factor()
2^3 * 3^3 * 5 * 7 * 11 * 13 * 19 * 23 * 29 * 41 * 61 * 67 * 71 * 1931 * 3253

There was an observation in case $n=5$, that the expected number of steps steps to go from $w$ to $e$ is the same as when going from $w^{-1}$ to $e$. Let us verify it here.

W = WeylGroup('A5')
w_list = list(W)
w_list.sort(key=lambda w: w.length())

ok = True
for w in w_list:
    we1, we2 = WE(w), WE(w^-1)
    if we1.varname < we2.varname:
        if sol[we1.var] == sol[we2.var]:
            print('OK :: same value {} for {} and the inverse {}'
                  .format(sol[we1.var], we1.varname, we2.varname))
        else:
            ok = False
            print('*** DIFFERENT VALUES :: {} = {} and {} = {}'
                  .format(we1.var, sol[we1.var], we2.var, sol[we2.var]))

This gives a lot of confirmation lines and finally ok remains True:

sage: ok
True

A way to argument is as follows. Each path of adjacent flips to get from $w$ to $e$ corresponds to exactly one path from $w^{-1}$ to $e$, apply them in reversed order. This symmetry and the symmetry of the Dynkin diagram, i.e. exchanging simple reflections in the ordered list $(s_1,s_2,s_3,s_4,s_5)$ so that we get them in reversed order, $(s_5,s_4,s_3,s_1,s_1)$, seem to be the only symmetries in the structure.

Here are some explicit values calculated above:

sage: [ (WE(w).var, sol[WE(w).var]) for w in w_list if w.length() < 3 ]
[(x, 0),
 (x3, 409694003392678411334887/562573226901324170862),
 (x2, 74514494034185062222904137/102388327296040999096884),
 (x4, 74514494034185062222904137/102388327296040999096884),
 (x1, 18061592492928724555567534/25597081824010249774221),
 (x5, 18061592492928724555567534/25597081824010249774221),
 (x32, 97237251774773889429499579/102388327296040999096884),
 (x34, 97237251774773889429499579/102388327296040999096884),
 (x23, 97237251774773889429499579/102388327296040999096884),
 (x21, 7932055083392903915602457/8532360608003416591407),
 (x43, 97237251774773889429499579/102388327296040999096884),
 (x42, 22612046194800912089196392/25597081824010249774221),
 (x45, 7932055083392903915602457/8532360608003416591407),
 (x31, 22229387237663671307532949/25597081824010249774221),
 (x12, 7932055083392903915602457/8532360608003416591407),
 (x41, 219680864482149559964339/252187998266110835214),
 (x53, 22229387237663671307532949/25597081824010249774221),
 (x52, 219680864482149559964339/252187998266110835214),
 (x54, 7932055083392903915602457/8532360608003416591407),
 (x51, 43713633645486016276491673/51194163648020499548442)]
sage: max([w.length() for w in W])
15
sage: [ (WE(w).var, sol[WE(w).var]) for w in w_list if w.length() > 13 ]
[(x12345123412312, 4107915597637259266379722/3656725974858607110603),
 (x23451234123121, 4107915597637259266379722/3656725974858607110603),
 (x12345123423121, 1473205929421015577091523/1312670862769756398678),
 (x12345123412321, 114943156003573670133682777/102388327296040999096884),
 (x12345234123121, 114943156003573670133682777/102388327296040999096884),
 (x123451234123121, 136181060295340/121172438079)]

n = $\bf 7$

This case is somehow too big for the pedestrian way of solving systems above. (There was some handy notation for the variables, which has its merits, but in this case this is too expensive.) So we really have to implement the linear system by building its matrix.

def mean_number_of_steps(n, print_A=False, print_x=False):
    W = WeylGroup(['A', n-1])
    w_list = list(W)
    w_list.sort(key=lambda w: w.length())

    w_cells = []
    w_used_values = []
    for w in w_list:
        if w in w_used_values:
            continue
        if w == W.one():
            w_cells.append( [w] )
            w_used_values.append(w)
            continue
        cell = [w, w^-1] 
        word = w.reduced_word()            
        u = W.from_reduced_word([n-j for j in word])
        cell = tuple(set([w, w^-1, u, u^-1]))
        w_cells.append(cell)
        w_used_values.extend(list(cell))

    def get_cell_index(w):
        return [ w_cells.index(cell) for cell in w_cells if w in cell ][0]

    class WA(object):
        """Associate to each w in W an instance with some more needed structure.
        """
        def __init__(self, w):
            self.w = w
            self.index = get_cell_index(w)
            if w == W.one():
                self.neighbours = []
            else:
                self.neighbours = [ get_cell_index(s*w)
                                    for s in W.simple_reflections() ]

    f, c = factorial(n), len(w_cells)
    A = matrix(QQ, c, c)
    for cell in w_cells:
        w = cell[0]    # pick a representative of the cell
        wa = WA(w)
        A[wa.index, wa.index] = 1
        for j in wa.neighbours:
            A[wa.index, j] += -1 / (n-1)
            # print(A)

    if print_A:
        print("The matrix of the system is:")
        print(A)
    b = vector(QQ, c, [1 if j != 0 else 0 for j in range(c)])
    x = A.solve_right(b)

    if print_x:
        print("The solution of the system is:")
        print(x)

    return sum([ x[j] * QQ(len(w_cells[j])) for j in range(c) ]) / f

Using this code, the prints

for n in [2..8]:
    print(f'\nn = {n}')
    M = mean_number_of_steps(n, print_A=(n < 5), print_x=(n < 5))
    print(f'\nMean number of steps is:\n  {M}\n  so approximatively {M.n()}')

are delivering

n = 2
The matrix of the system is:
[ 1  0]
[-1  1]
The solution of the system is:
(0, 1)

Mean number of steps is:
  1/2
  so approximatively 0.500000000000000

and

n = 3
The matrix of the system is:
[   1    0    0    0]
[-1/2    1 -1/2    0]
[   0 -1/2    1 -1/2]
[   0    0   -1    1]
The solution of the system is:
(0, 5, 8, 9)

Mean number of steps is:
  35/6
  so approximatively 5.83333333333333

and

n = 4
The matrix of the system is:
[   1    0    0    0    0    0    0    0    0    0    0    0    0]
[-1/3    1    0 -1/3 -1/3    0    0    0    0    0    0    0    0]
[-1/3    0    1 -2/3    0    0    0    0    0    0    0    0    0]
[   0 -1/3    0    1    0 -1/3 -1/3    0    0    0    0    0    0]
[   0 -2/3    0    0    1    0    0 -1/3    0    0    0    0    0]
[   0    0    0 -1/3    0    1    0    0 -2/3    0    0    0    0]
[   0    0    0 -2/3    0    0    1    0 -1/3    0    0    0    0]
[   0    0    0    0 -1/3    0    0    1 -2/3    0    0    0    0]
[   0    0    0    0    0 -1/3 -1/3    0    1    0 -1/3    0    0]
[   0    0    0    0    0    0    0 -1/3    0    1 -2/3    0    0]
[   0    0    0    0    0    0    0    0 -1/3 -1/3    1    0 -1/3]
[   0    0    0    0    0    0    0    0 -2/3    0    0    1 -1/3]
[   0    0    0    0    0    0    0    0    0    0 -2/3 -1/3    1]
The solution of the system is:
(0, 625/28, 341/14, 981/28, 405/14, 1153/28, 1081/28, 274/7, 171/4, 621/14, 1273/28, 629/14, 324/7)

Mean number of steps is:
  1019/28
  so approximatively 36.3928571428571

and

n = 5

Mean number of steps is:
  73483980061/379029420
  so approximatively 193.874079909153

and

n = 6

Mean number of steps is:
  1105216051055620235300660929/1023883272960409990968840
  so approximatively 1079.43559607146

and

n = 7

Mean number of steps is:
  214998640399563504565106261781990833196638436647758234442887215473549887803722305593765999513740842990149079
  /
  31218641703910975710483919230896568944120659862343614701479235239401027577533129044990591113216494809020
  so approximatively 6886.86722627747

(with a manually rearranged fraction...) and

n = 8

(... still working ...)

I have to stop here, this was a hard day's night, and the next similar day has started...

Best Answer

Related Solutions

Average swaps needed for a random bubble sort algorithm

Related Question