1
\$\begingroup\$

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
\$\endgroup\$
0

1 Answer 1

1
\$\begingroup\$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.