My implementation of bubble sort using Python

Question

I just started studying algorithms and since I'm most familiar with Python decided to use it to actually put the algorithms I've been learning to use. How is my implementation of Bubble Sort? Does it make sense, is it efficient, too many variables, can you understand it without comments, any other tips for me?

"""
Bubble sort algorithm.
"""
import random
ls = []
max_length = 10
while len(ls) < max_length:
 ls.append(random.randint(1,101))
print ls
def bubble_sort(items_to_sort):
 right_item = -1 
 left_item = -2
 item_len = len(items_to_sort)
 number_of_passes = 0
 temp_item = 0
 max_checks = len(items_to_sort)
 if item_len > 1:
 while (number_of_passes < item_len) and (max_checks > 0):
 if items_to_sort[right_item] < items_to_sort[left_item]:
 temp_item = items_to_sort[right_item] 
 items_to_sort[right_item] = items_to_sort[left_item] 
 items_to_sort[left_item] = temp_item 
 right_item += -1
 left_item += -1
 number_of_passes += 1
 if left_item < -(item_len):
 right_item = -1
 left_item = -2
 number_of_passes = 0
 max_checks -= 1
 return items_to_sort 
print bubble_sort(ls)

• terratunaz: Just found a bug in my code. Before the while statement I need to check if the length of the array is greater than 1 and if it is precede with my code and if not there is no need to sort so just return the list object. Will update my code to reflect the change.
• Gareth Rees: See this answer for some ideas that might be helpful.
• outis: Is it just me, or does it feel wrong seeing "efficient" applied to "bubble sort"?

Answer 1

Your bubble sort algorithm has way too many variables. You don't need to keep track of the right and left item. All you need to do is compare two values, and swap if one is bigger than the other.

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

After benchmarking, this code is substantially faster than your original code.

Benchmarks:

Array size bubble_sort_op 3000 1.87206s
Array size bubble_sort 3000 0.67218s
Array size bubble_sort_op 3200 2.24581s
Array size bubble_sort 3200 0.78276s
Array size bubble_sort_op 3400 2.41464s
Array size bubble_sort 3400 0.87018s
Array size bubble_sort_op 3600 2.69006s
Array size bubble_sort 3600 0.96319s
Array size bubble_sort_op 3800 2.99190s
Array size bubble_sort 3800 1.09713s
Array size bubble_sort_op 4000 3.48652s
Array size bubble_sort 4000 1.24830s