2
\$\begingroup\$

Algorithm

Bubble sort, also known as sinking sort, is a sorting algorithm that repeatedly steps through a list, compares adjacent pairs and swaps them if they are not in the right order. The pass through the list is repeated, until the sorting is complete. The algorithm, which is a comparison sort, is named for the way smaller or larger elements "bubble" to the top of the list.


Solution 1

This is my BubbleSort function:

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

which outputs:

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

Solution 2

With some detailed advice, here is a second solution, limited to using one list comprehension:

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))]

which somewhat outputs the same:

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

Would you be so kind and review it? I'd also like to know about time/space complexities, if you possibly had time.

\$\endgroup\$
1
  • \$\begingroup\$ I don't understand what you are really asking, all of your answers are here and in Wikipedia, you pretty much tackle it already \$\endgroup\$
    – Alper
    Aug 5, 2019 at 10:53

1 Answer 1

1
\$\begingroup\$

BubbleSort is not an efficient algorithm. Talking time-complexity it runs in \$O(n^2)\$ which is okay given a very small array, but for a larger amount of numbers its almost unusable.

This is a comparison between a few sorting algorithms that i wrote in C#. As you can see the only advantage of BubbleSort over the other algorithms is that it is very easy to program. Time Complexity

Anyway - back to your code. I would your implementation is good although i find the first one way more readable. All in all if you just wanted to implement BubbleSort you did a good job, but if you really want to sort a list, you should definitely consider another algorithm that runs in \$O(log(n))\$.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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