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

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

while (size &lt; 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] &gt; list1[j+1]:
            list1[j],list1[j+1] = list1[j+1],list1[j]

print(list1)
</code></pre>

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

<pre><code>def bubble_sort(arr):
    for i in range(len(arr))[::-1]:
        for j in range(1, i + 1):
            if arr[j - 1] &gt; arr[j]:
                arr[j], arr[j-1] = arr[j-1], arr[j]
</code></pre>

<p>First loop iterating through <code>range(len(arr))</code> in reversed order (<code>[::-1]</code> - 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.</p>

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

<pre><code>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)
</code></pre>

<p>As you can see, <code>bubble_sort</code> is faster than <code>bubble_sort_2</code>.</p>

python bubble-sort