CODEWITHSUNDEEP
pythonbubble-sort
el2e10
el2e10

Reputation: 1558

Is this a correct way to implement bubble sort?

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)

Upvotes: 0

Views: 125

Answers (2)

finomayato
finomayato

Reputation: 80

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.

Upvotes: 1

VPfB
VPfB

Reputation: 17332

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]

Upvotes: 1

Related Questions