Timeline for What is the requirement for bubble sort to complete in 1 pass?
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 7, 2020 at 22:41 | comment | added | Yuval Filmus | Yes, multiple proofs are possible. | |
| Oct 7, 2020 at 22:14 | comment | added | student010101 | 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? | |
| Oct 6, 2020 at 14:23 | comment | added | Yuval Filmus | There might be a way to write a recurrence, but a recurrence is not the only way to count things. | |
| Oct 6, 2020 at 14:22 | comment | added | student010101 | 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. | |
| Oct 6, 2020 at 14:20 | vote | accept | student010101 | ||
| Oct 6, 2020 at 14:11 | comment | added | Yuval Filmus | 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. | |
| Oct 6, 2020 at 13:05 | comment | added | student010101 | 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 \\ $$ | |
| Oct 6, 2020 at 8:21 | history | answered | Yuval Filmus | CC BY-SA 4.0 |