1

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]
Emma
  • 27,428
  • 11
  • 44
  • 69
  • 1
    Well since you use a *nested* `for` loop, your list will contain *n^2+n/2* (on average the filtering will retain a certain part of these values), hence it will not print such list (unfortunately Python does not really implement a list monad, since that would make it easier). – Willem Van Onsem Aug 04 '19 at 21:40
  • 1
    @ScotHunter: that is correct, but eventually it will boil down to the number of "swaps" if we iterate over the lists like we would do with bubble sort. Worst case, bubble sort does not only require *O(n^2)* comparisons, but *O(n^2)* swaps as well (a swapped list would require that). – Willem Van Onsem Aug 04 '19 at 21:44
  • 3
    We could however convert selection sort to a "list comprehension" equivalent, although that will be inefficient as well. – Willem Van Onsem Aug 04 '19 at 21:45
  • 2
    Let's also emphasize that list comprehensions were intended to make new lists, and this is not a good use case for them, just to emphasize what you may already know but someone coming to this question with a fresh pair of eyes may not. – Paritosh Singh Aug 04 '19 at 21:47
  • 1
    @ParitoshSingh: correct, it would require at least something with side-effects. Even if that is possible, it is not good from a software design point of view. – Willem Van Onsem Aug 04 '19 at 21:48
  • 1
    Not quite a duplicate, but certainly of interest: [python-list-comprehension-access-last-created-element](https://stackoverflow.com/questions/794774/python-list-comprehension-access-last-created-element). –  Aug 04 '19 at 22:48
  • 1
    Don't want to post it as an answer, since it's ugly as hell, but here's an inplace solution: `[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))]`. After executing this, `l` will be sorted. –  Aug 05 '19 at 00:23
  • 1
    @Emma sorting the list is a sideeffect of the list-comprehension. The list-comprehension itself is only a list of as many `None` as comparisons are made. It can be used [this way](https://ideone.com/wwU06V). I've tried to put a working list-comprehension together that produces the sorted list without side-effects, but that turned into pretty much the darkest hack I've ever pulled of in python before I got even close to a solution. –  Aug 05 '19 at 01:10
  • 1
    Might give a "pure" solution another shot tomorrow. I somehow fell in love with this problem. –  Aug 05 '19 at 01:16

3 Answers3

2

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
  • How is it still bubble sort if it has O(n^3) time complexity? – גלעד ברקן Aug 05 '19 at 16:25
  • 1
    @גלעדברקן why shouldn't it be? The additional multiplicator of `n` comes from the underlying datastructure, which is fairly suboptimal, not the actual algorithm. You could do pretty much the same with any other algorithm by increasing the cost of a single array-access from `O(1)` to `O(n)`. It would still be the same algorithm, but more expensive. –  Aug 05 '19 at 16:42
  • 1
    @גלעדברקן I've added an explanation that makes it more easy to see that this is actually bubblesort –  Aug 05 '19 at 16:59
1

Using a list comprehension to hide a for loop is kind of cheating given that the result produced by the comprehension is not the sorted list. But if you're going to do that, you might want to avoid building a list of None elements by performing the swaps in the condition rather than as the output value.

For example:

a = [1, 3, 2, 6, 5, 4]
[_ for n in range(len(a),1,-1) for i in range(n-1) if a[i]>a[i+1] and a.__setitem__(slice(i,i+2),a[i:i+2][::-1])]

Isolating the element swapping part, this would give:

swap = lambda(a,i):a.__setitem__(slice(i,i+2),a[i:i+2][::-1])
[_ for n in range(len(a),1,-1) for i in range(n-1) if a[i]>a[i+1] and swap(a,i)]

Which is no different from:

for n in range(len(a),1,-1):
    for i in range(n-1):
        if a[i]>a[i+1]: 
           swap(a,i)     # same as a[i],a[i+1] = a[i+1],a[i]

The list comprehension is merely a different way to write the for loop and is not actually returning the sorted result.

What would be more in the spirit of a list comprehension is to actually return the sorted result without affecting the original list. You can do this using a temporary list within the comprehension to perform the element swapping and progressively return the position that is guaranteed to be at the right sorted index:

a = [1, 3, 2, 6, 5, 4]
s = [ b.pop(-1) for b in [list(a)] for n in range(len(a),0,-1) if not [_ for i in range(n-1) if b[i]<b[i+1] and b.__setitem__(slice(i,i+2),b[i:i+2][::-1])] ]
print(s) # [1, 2, 3, 4, 5, 6]

The approach is the same as before except that b is used internally to manage swapping and return the sorted values. Because the guaranteed sorted position is always the last one in b, the swapping condition was reversed so that internally b is sorted in descending order which produces the output in ascending order when taking the last item at each iteration.

Note that all these solutions fail to implement the early exit condition that allows bubble sort to be very efficient on already sorted lists and lists where elements are near their sorted position (i.e. stop when no swaps in a pass). The number of iterations will always be N*(N+1)/2 no matter the original order of elements giving a time complexity of O(N^2) all the time instead of worst case.

Alain T.
  • 40,517
  • 4
  • 31
  • 51
0
def bubblesort(l):
    [[l.insert(j+1, l.pop(j)) for j in range(i) if l[j] > l[j+1]] for i in range(len(l)-1,0,-1)]
    return l

I use the l.insert(j+1, l.pop(j)) to swap the elements in the list. The rest are just the nested loops.

PCM
  • 2,881
  • 2
  • 8
  • 30
Alfware
  • 1