Is this a correct way to implement bubble sort?

Question

Is this a correct way to implement bubble sort? I get a sorted list, but I have a doubt that the method is correct.

# Input unsorted list
size_lis = int(input("enter the size of the list"))
size = 0
list1 = list()

while (size < size_lis):
    element = int(input("enter the element"))
    list1.append(element)
    size += 1

# Sort
for i in range(0, len(list1)):
    for j in range(0, len(list1)-1):
        if list1[j] > list1[j+1]:
            list1[j],list1[j+1] = list1[j+1],list1[j]

print(list1)

Yes it works But is it the correct way to implement the bubble sort. — el2e10, Sep 20 '16 at 15:03
What do you mean by correct? If the program does it's job, why would it be incorrect? Are you looking for a more pythonic, more succinct, more elegant solution? — Danielle M., Sep 20 '16 at 15:05
Again, what do you mean by the correct way. Please define what you mean by correct. If it works, it's correct - why is your script not correct? What's incorrect about it? — Danielle M., Sep 20 '16 at 15:14
Actually bubble sort generally use a for loop inside a while loop (with a boolean changed in the if). The advantage is that you save some iterations, since you stop as soon as it is sorted (the obvious example is if it's sorted at start, you only do one iteration). It's not about the 'correct' way, just a slightly more efficient, even if the word efficient doesn't really fit with bubble sort. — polku, Sep 20 '16 at 15:27

finomayato · Answer 1 · 2016-09-20T21:14:29.897

1

This is the correct implementation of the bubble sort algorithm. But you can prevent extra loops using this kind of implementation:

def bubble_sort(arr):
    for i in range(len(arr))[::-1]:
        for j in range(1, i + 1):
            if arr[j - 1] > arr[j]:
                arr[j], arr[j-1] = arr[j-1], arr[j]

First loop iterating through range(len(arr)) in reversed order ([::-1] - operation for reversing the list in the most efficient way). After first iteration of this loop the biggest element in your list will be placed in the end of the list. And the second loop needs to iterate only through remaining elements.

I tested yours(bubble_sort_2) and mine(bubble_sort) implementation using two identical arrays on 1000 elements. Here are the results (using cProfile):

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    1    0.215    0.215    0.215    0.215   bs.py:22(bubble_sort_2)
    1    0.128    0.128    0.128    0.128   bs.py:16(bubble_sort)

As you can see, bubble_sort is faster than bubble_sort_2.

edited Sep 20 '16 at 21:14

answered Sep 20 '16 at 15:40

finomayato

80
7

Rather than slicing your `range` to reverse it, why not just create it in the desired order in the first place? If you use `range(len(arr), 0, -1)`, you can even get rid of the `i+1` in the `range` call for `j`. (`reversed` is also an efficient way to iterate on something in reverse.) – Blckknght Sep 20 '16 at 20:21
@Blckknght, if you're talking about readability - you're right. But for further examination of this question I recommend you to read answers on this [page](http://stackoverflow.com/questions/3705670/best-way-to-create-a-reversed-list-in-python) – finomayato Sep 20 '16 at 21:13
*If* you were reversing some pre-existing list, I'd agree that the martian-smiley would probably be the fastest way to get the job done (though it's probably faster than the alternatives by an insignificant amount). However, you're creating the list right there in the `range` call, so there's no possible way that reversing it afterwards is going to be faster than just creating it in the correct order to start with. – Blckknght Sep 20 '16 at 21:52
@Blckknght, if we're talking about python-2.x yours list creation will be more effective. But in the case of python-3.x objects iterated over are lazy. (I [asked](http://stackoverflow.com/questions/39617160/reverse-the-list-while-creation) for the explanation). – finomayato Sep 21 '16 at 13:42

score 1 · Answer 2 · answered Sep 20 '16 at 16:18

In bubble sort the largest element is moved step by step to the end of list. Thus after first pass there is this one element in its final position. The second pass should sort only N-1 remaining elements, etc.

In the posted code, just adjust the inner circle like this. That'll save almost 50% of CPU time.

n = len(lst)
for i in range(n):
    for j in range(n-i-1):
        if lst[j] > lst[j+1]:
            lst[j], lst[j+1] = lst[j+1],lst[j]

Is this a correct way to implement bubble sort?

2 Answers2