Bubbling of Sorts

Bubble Sort

A given sequence $r_1, r_2, \dots, r_n$ of distinct real numbers can be put in ascending order by means of one or more "bubble passes". A bubble pass through a given sequence consists of comparing the second term with the first term, and exchanging them if and only if the second term is smaller, then comparing the third term with the second term and exchanging them if and only if the third term is smaller, and so on in order, through comparing the last term, $r_n$, with its current predecessor and exchanging them if and only if the last term is smaller.

The example below shows how the sequence $1,$ $9,$ $8,$ $7$ is transformed into the sequence $1,$ $8,$ $7,$ $9$ by one bubble pass. The numbers compared at each step are underlined.

$\underline{1 \quad 9} \quad 8 \quad 7\\ 1 \quad {}\underline{9 \quad 8} \quad 7\\ 1 \quad 8 \quad \underline{9 \quad 7}\\ 1 \quad 8 \quad 7 \quad 9$

Problem

Bubbling of Sorts

Solution 1, Question 1

Not to be pulled down a number needs to be larger the ones preceding it; to be drawn up it also needs to be larger than some following it. To get into position $\#30$ a number needs to be larger than the previous $29$ terms while smaller than the $31^{th}$ term. If we denote the two numbers $r_{30}$ and $r_{31},$ then this means that $r_{31}$ is the largest of the $31$ numbers and $r_{30}$ is the next largest. There are $31!$ permutations of $31$ numbers and $29!$ permutations that fix two numbers out of $31.$ The probability is thus $\displaystyle P=\frac{29!}{31!}=\frac{1}{30\cdot 31}=\frac{1}{930}.$

Solution 2, Question 1

To get into position $\#30$ a number needs to be larger than the previous $29$ terms while smaller than the $31^{th}$ term. But nothing makes $r_{20}$ especially remarkable. The largest of the first $30$ numbers could have been in any position, not necessarily the $20^{th}.$ Thus, the probability that $r_{20}$ is the largest among the first $30$ numbers is $\displaystyle \frac{1}{30}.$ Similarly, The number in the thirty first place that stopped the advancement of $r_{20}$ is the largest among the first $31,$ while the probability of the largest number among $31$ to be in the position $\#31$ is $\displaystyle \frac{1}{31}.$ The two events being independent, the probability of both happening is $\displaystyle \frac{1}{30\cdot 31}=\frac{1}{930}.$

Solution, Question 2

On the first pass, as the advancement of $r_{20}$ was stopped by $r_{31},$ the latter could have been up on the next step so as to bring into the position $\#31$ a number smaller than $r_{20}$ (the one that is in the position $\#30$ after the first pass.) For this not to happen, the number $r_{32}$ needs to be larger than $r_{20}.$ Thus the sample space consists of $32!$ sequences in which one position is fixed and two are interchangeable, making the probability for the second question $\displaystyle P=\frac{29!\cdot 2}{32!}=\frac{2}{30\cdot 31\cdot 32}=\frac{1}{14880}.$

Solution, Question 3

For $n$ bubble passes, $r_{20}$ in order to stay in the position $\#30$ needs protection of $n$ numbers, each larger than $r_{20}.$ These are located in positions $31,32,\ldots,30+n.$ Their order is inconsequential. Which gives the probability $\displaystyle P=\frac{29!\cdot n!}{(30+n)!}.$

After $10$ passes (or less) the terms in positions $31-40$ will be correctly ordered. If the same is true (which is not assured) for positions $1-29,$ the algorithm will stop. If it does not, it will continue re-order the terms in those lower positions with affecting $r_{20}$ in position $\#30.$

Extra question

Assume the first question was never asked. Then what is the probability that the number that begins as $r_{20}$ will end up in the $30^{\mbox{th}}$ place after $n\le 10$ bubble passes?

We might as well ignore positions $33-40$. Relabel $1-32$ for convenience. $30$ in spot $20$ and either $31$ or $32$ in spot $32.$ Bubbling small numbers backward from the end helps perspective. Answer: $\displaystyle \frac{2}{32\cdot 31}.$

Acknowledgment

This is an extension of problem 13 from the 1987 AIME. The problem itself was discussed in R. Honsberger's From Erdös To Kiev (MAA, 1996, 21-22).

Christopher D. Long initiated a discussion of the general case (Question 3) and produced the formula for its solution.

Antonio Catalano has observed that, as it was stated, the second question is not automatically conditioned on the first. If just posed by itself, it leads to an answer entirely different from the above. The answer was given by Mathew Crawford and was very close to Antonio's simulation.

 

|Contact| |Front page| |Contents| |Probability|

Copyright © 1996-2018 Alexander Bogomolny
[an error occurred while processing this directive]
[an error occurred while processing this directive]