2
$\begingroup$

I am working on a problem where you're given $n$ distinct numbers, and you want to find the number of permutations such that it takes bubble sort at most 1 pass to complete.

e.g., if n=3, then the following permutations would only require 1 pass

1 2 3 
1 3 2 
3 1 2 
2 1 3 

But

3 2 1 
2 3 1

would require more than 1 pass. Apparently the answer is $2^{n - 1}$, but I am not sure how to prove this for the general $n$ case.

My question is, what are the general constraints for a sequence to allow for it to be sorted with 1 pass of bubble sort?

It is difficult for me to come up with a generic formula to generate the permutations for larger $n$.

$\endgroup$
3
  • $\begingroup$ Hint: let the position of the maximum element to be $i$. What can you say about elements to the left of $i$ and to the right of $i$? Find the number of such permutations for all possible $i$. You'll get the recurrent formula, for which it would be easy to show the answer by induction. $\endgroup$ – user114966 Oct 6 '20 at 2:21
  • $\begingroup$ @Dmitry Doesn't both the elements to the left and right of $i$ have to be less than the element at $i$? $\endgroup$ – student010101 Oct 6 '20 at 2:34
  • $\begingroup$ Welcome to COMPUTER SCIENCE @SE. I think that to depend on the termination condition of the bubble sort you argue about: please specify in the question. $\endgroup$ – greybeard Oct 6 '20 at 6:38
2
$\begingroup$

I'm assuming that a pass of bubble sort on the array $A[1],\ldots,A[n]$ proceeds as follows:

  • If $A[1] > A[2]$ then swap $A[1]$ and $A[2]$.
  • If $A[2] > A[3]$ then swap $A[2]$ and $A[3]$.
  • ...
  • If $A[n-1] > A[n]$ then swap $A[n-1]$ and $A[n]$.

Bubble sort halts after a pass in which no swaps were made.

As is evident, if bubble sort halts after one pass, then the array must have been sorted.

When does bubble sort halt after two passes? If after the first pass, the array is sorted. In this case, if we know which swaps were made, then we can recover the input permutation. Furthermore, different sets of swaps correspond to different initial permutations. It follows that there are $2^{n-1}-1$ permutations that cause bubble sort to halt after exactly two passes. Together with the identity permutation, it follows that there are $2^{n-1}$ permutations that cause bubble sort to halt within two passes.

How do these permutations look like? Suppose that the first $k$ swaps are made, and then the following swap isn't made. Since the first $k$ swaps are made but the following one isn't made, at the end of the pass the first $k+1$ elements of the array will be $A[2],\ldots,A[k+1],A[1]$, which must correspond to the permutation $1,\ldots,k+1$. Hence the original permutation started $k+1,1,\ldots,k$.

From here, it's not too difficult to describe all $2^{n-1}$ permutations. Starting with the identity permutation, partition it in an arbitrary way, and rotate each part one step to the right. For example, when $n = 3$ we get:

  • $1|2|3 \to 1|2|3$.
  • $1|23 \to 1|32$.
  • $12|3 \to 21|3$.
  • $123 \to 312$.

Each division in the partition corresponds to a step in the pass during which there was no swap.


Here is another way of describing these permutations: they avoid the patterns $231$ and $321$. This means that for any $i<j<k$, it cannot be that $A[k] < A[i],A[j]$. To prove this, we show that any permutation above satisfies this constraint, and then prove the converse.

Consider any of the $2^{n-1}$ permutations above, and let $i<j<k$. Since each element in a part is smaller than each element in a subsequent part, $A[k] < A[i]$ is only possible if $i,j,k$ are all in the same part. Moreover, $A[k] < A[j]$ for indices $j<k$ in the same part only if $j$ is the first element in the part, which is impossible since $j>i$.

Suppose now that we are given a $(231,321)$-avoiding permutation. Let $i$ be any index such that $A[i] > i$. All elements in $i,\ldots,A[i]-1$ must appear before all elements in $A[i]+1,\ldots,n$, since otherwise there will be a copy of $231$. Furthermore, the former must appear in increasing order, since otherwise there will be a copy of $321$. Therefore the part of the array that follows $A[i]$ is $A[i],i,i+1,\ldots,A[i]-1$.

Imagine now scanning the array in the order $A[1],A[2],\ldots$. The first time that $A[i] \neq i$, necessarily $A[i] > i$ (since we've already seen all smaller elements), and so the following elements are $i,\ldots,A[i]-1$. When we continue the scan, again the first time that $A[i] \neq i$ we must have $A[i] > i$ (since we've already seen all smaller elements), and so on. Therefore the array is of the form above.

$\endgroup$
6
  • $\begingroup$ I'm looking at your partition graphic for the $n = 3$ example. From this, I'm inducing that the number of permutation is equal to the number of possible unique partitioning of an $n$ sized array. Is this correct? For $n = 4$, we have the following $$ 1\ 2 \ 3\ 4 \\ 1 | 2 | 3| 4 \\ 1 \ 2 | 3| 4 \\ 1\ 2 | 3 \ 4 \\ 1 \ 2 \ 3| 4 \\ 1 | 2 \ 3 \ 4 \\ 1 | 2 | 3 \ 4 \\ 1 | 2 \ 3 | 4 \\ $$ $\endgroup$ – student010101 Oct 6 '20 at 13:05
  • $\begingroup$ Right. It's also easy to prove combinatorially by noting that each of the internal $n-1$ positions could contain or not contain a bar. $\endgroup$ – Yuval Filmus Oct 6 '20 at 14:11
  • $\begingroup$ Ahhh yes, that was exactly what I was looking for that "each of the internal......could or could not contain a bar." I knew there was an easy way to see this, but I couldn't figure it out. Also btw, do you know if there's a way to see this from a recurrence approach? Specifically, I was initially viewing this problem from the perspective that we have $n$ numbers, and now we add 1 more number, how many additional valid permutations does this additional number provide us with? I couldn't figure out a good way to think about this. $\endgroup$ – student010101 Oct 6 '20 at 14:22
  • $\begingroup$ There might be a way to write a recurrence, but a recurrence is not the only way to count things. $\endgroup$ – Yuval Filmus Oct 6 '20 at 14:23
  • $\begingroup$ To prove $i < j < k$ and $A[k] < A[i], A[j]$, isn't this also clear from the fact that an element in the unsorted array can only move one space to the left max for each pass, so if you have an element in the unsorted array in which there are two elements before it that are larger, then it is not possible to sort this array in one pass? $\endgroup$ – student010101 Oct 7 '20 at 22:14
1
$\begingroup$

Bubble sort isn’t completed when the array is sorted - it is completed when we know the array is sorted.

Take the case 1-3-2. We have x-y-z and bubblesort figures out in the first pass that x is less than y and y is greater than z. It doesn’t know how x and z are related and therefore doesn’t know whether the array is sorted after one pass or not, therefore bubblesort is not complete at this point

If you change the question to “how many passes until the array is sorted”, that’s a different question. But to answer the question: If the number of array elements is zero or one, then bubble sort completes with zero passes. Otherwise, if either the array is sorted or the array has two elements then bubble sort complets with one pass. Otherwise, two or more passes are needed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.