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
– el2e10, Commented Sep 20, 2016 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.
– Danielle M., Commented Sep 20, 2016 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.
– Danielle M., Commented Sep 20, 2016 at 15:14

VPfB · Accepted Answer · 2016-09-20 16:18:20Z

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]

finomayato · Accepted Answer · 2016-09-20 21:14:29Z

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.

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, 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
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, 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 for the explanation).

Collectives™ on Stack Overflow

Is this a correct way to implement bubble sort?

2 Answers 2

Comments

4 Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

4 Comments

Linked

Related