Bubble sorting with one list comprehension

Question

I'd like to see if it would be possible to convert a BubbleSort function, such as:

def BubbleSort(l):
    for i in range(len(l)-1):
        for j in range(len(l)-1-i):
            if (l[j]>l[j+1]):
                l[j],l[j+1]=l[j+1],l[j]
    return l

to a one-liner list comprehension, maybe similar to:

def BubbleSort(l):
    return [something_goes_here for i in range(len(l)-1) for j in range(len(l)-1-i) if (l[j]>l[j+1])]

Sample Input:

print(BubbleSort([1,5,-5,0,10,100]))

Sample Output

[-5, 0, 1, 5, 10, 100]

Answer 1

A solution based on side-effects looks like this:

def bubblesort(l):
    [l.append(l.pop(0) if i == len(l) - 1 or l[0] < l[1] else l.pop(1)) for j in range(0, len(l)) for i in range(0, len(l))]
    return l

This will sort the list l in-place.

The basic idea is to treat l as both the input and output-list. Swaps can then be emulated by either moving the first or the second element of l to the end. The last element must be moved to the end without any comparison to get a new list list. A visual example of one iteration ([l.append(l.pop(0) if i == len(l) - 1 or l[0] < l[1] else l.pop(1)) for i in range(0, len(l))]):

1 3 2 6 5 4 |
  3 2 6 5 4 | 1
    3 6 5 4 | 1 2
      6 5 4 | 1 2 3
        6 4 | 1 2 3 5
          6 | 1 2 3 5 4
            | 1 2 3 5 4 6

In this example | denotes the separator between the last element of the original list and the first element that was already appended. Repeating this process len(l) times guarantees that the entire list is sorted.

Note that while this example does perform a bubblesort, it's runtime is O(n^3), since we need to remove the first or second element from the list in each step, which runs in O(n).

EDIT:
It becomes more easy to see that this is actually bubblesort from the above algorithm, if we rewrite the sample-iteration as such:

| 1 3 2 6 5 4
1 | 3 2 6 5 4
1 2 | 3 6 5 4
1 2 3 | 6 5 4
1 2 3 5 | 6 4
1 2 3 5 4 | 6
1 2 3 5 4 6 |

Here the separator denotes the end of the list and a circular view of the list is used.

EDIT 2:
Found a more efficient way to solve this that uses slice-assignment:

def bubblesort(l):
    [l.__setitem__(slice(i, i + 2), (l[i:i + 2] if l[i] < l[i + 1] else l[i +  1:i - 1:-1])) for j in range(0, len(l)) for i in range(0, len(l) - 1)]
    return l