Bubble sort and swapping algorithm related questions I actually think SE is more apt than stackoverflow for this question, but let me know if you disagree in the comments.
It would help to know what bubble sort is.
Question 1: Given a list of the first n integers, scrambled order, figure out the least amount of adjacent swaps (and what those swaps are in the correct order) so that the list ends up in numerical order.
Question 2: Same as question 1 but the swaps need not be adjacent.
$$$$
Example for Question 1:
Start with: $ 4 \quad 2 \quad 3  \quad 1.\quad$ Swap $4 \leftrightarrow 2$ to get:
$ 2 \quad 4 \quad 3  \quad 1.\quad$ Swap $3 \leftrightarrow 1:$
$ 2 \quad 4 \quad 1  \quad 3.\quad$ Swap $4 \leftrightarrow 1:$
$ 2 \quad 1 \quad 4  \quad 3.\quad$ Swap $2 \leftrightarrow 1:$
$ 1 \quad 2 \quad 4  \quad 3.\quad$ Swap $4 \leftrightarrow 3:$
$ 1 \quad 2 \quad 3  \quad 4 ,\quad$ and we are done.
I think this is the way with the least swaps, but there might be quicker, not sure. This has 5 steps - the same as bubble sort itself. So can we never do better than the number of steps bubble sort takes if we do the swaps different to bubble sort? Maybe that's the case for this example, but for all examples is it true? If so why?
Example for Question 2:
Start with: $ 4 \quad 2 \quad 3  \quad 1.\quad$ Swap $4 \leftrightarrow 1$ to get:
$ 1 \quad 2 \quad 3  \quad 4 ,\quad$ and we are done.
This shows that Method 2 is at least as quick as method 1. But this example for method 2 was very easy of course. What if we were given:
$ 7 \quad 0 \quad 5 \quad 1 \quad 3 \quad 8 \quad 9 \quad 2 \quad 6 \quad 4$.
We see that for a list length $n$, we can sort using the second method in at most $n-1$ swaps. But is there a nice way to figure out if we can do better than (i.e. less than) $n-1$ swaps?
 A: The answer to question 2 can be computed very efficiently using cycle notation. Once your permutation is expressed as a product of $k$ disjoint cycles (including 1-cycles), the value you seek is $n - k$. Your first example $4\ 3\ 2\ 1$ would be written as:
$$(1 4)(2)(3)$$
There are three cycles: $(1 4)$, $(2)$, and $(3)$, so the number of swaps necessary is $n - k = 4 - 3 = 1$.
The cycle decomposition for your second example is:
$$(0\ 7\ 2\ 5\ 8\ 6\ 9\ 4\ 3\ 1)$$
which has only one cycle, so the number of swaps is $n - k = 10 - 1 = 9$. In fact, the cycle encodes a recipe for ordering them, but I will leave that as an exercise.
Question 1 is a bit trickier. The number of adjacent swaps required is equal to the number of pairs of indices such that the values at those locations are in reverse order. This can be up to $n(n-1)/2$. Some of the details are here, including some connections to bubble sort.
The great challenge of real-world sorting, though, is that we are rarely trying to sort a permutation of $\{1, \dots, n\}$. Many sets can't be totally ordered. Some may have duplicate elements. When sorting a permutation of $\{1, \dots, n\}$, the list IS the permutation, so it is easy to compute the transpositions (swaps) that undo it.
On the other hand, even a slightly more general list is more challenging:
$$3, -2, 1, -1, 4.$$
We can't divine the true order without doing all the comparisons needed to actually sort the list. The work involved to compute an efficient sequence of transpositions is essentially the same as the work to just sort the thing. So, in the end, we don't usually bother with the permutation and simply sort the list using just about any algorithm that isn't a variant of bubble sort.
