Two simple sorting algorithms in Python

For a personal programming challenge, I wanted to try writing simple bubble sort and insertion sort functions in Python 3. I haven't looked at the standard pseudo-code, I just read about how they worked. Are these good implementations?

def bubble_sort(array):
"""
Sorts array using a bubble sort.

>>> bubble_sort([43, 10, 100, 24, 1, 6, 10, 3])
[1, 3, 6, 10, 10, 24, 43, 100]
"""
array2 = array[:] # Save a copy, so that original is not mutated
last_index = len(array) - 1 # Iterate up to this position
while last_index > 0:
for i in range(last_index):
a, b = array2[i], array2[i + 1] # Consecutive numbers in array
if a > b:
array2[i], array2[i + 1] = b, a # Swap positions
last_index -= 1 # A new number has bubbled up, no need to inspect it again
return array2

def insertion_sort(array):
"""
Sorts array using an insertion sort.

>>> insertion_sort([43, 10, 100, 24, 1, 6, 10, 3])
[1, 3, 6, 10, 10, 24, 43, 100]
"""
sorted_array = []
for a in array:
# Loop backwards through sorted_array
for i, b in reversed(list(enumerate(sorted_array))):
if a > b:
sorted_array.insert(i + 1, a) # Insert a to the right of b
break
else:
# a is less than all numbers in sorted_array
sorted_array.insert(0, a) # Add a to beginning of list
return sorted_array


The docstrings and doctests are nice. I would prefer a more explicit description of the behaviour: "Return a copy of the array, sorted using the bubble sort algorithm." Typically, if you're implementing these sorting algorithms as an exercise, you would perform the sorting in place.

In bubble_sort(), the while last_index > 0 loop would be written more idiomatically as:

for last_index in range(len(array) - 1, 0, -1):
…


In insertion_sort(), the reversed(list(enumerate(sorted_array))) would be making temporary copies of sorted_array. I would therefore consider it an improper implementation of the algorithm.

• I see the point about reversed(list(enumerate(sorted_array))) creating temporary copies. Is there a way that could be avoided? Oct 31, 2016 at 22:30
• Use a range() over the indices you want to traverse, like you did with bubble_sort(). Oct 31, 2016 at 22:31