Simple Sorts in Python

sorts.py

TEST_ARRAY1 = [2,5,1,3,4]

def bubblesort(unordered_list):
    """
    Bubble the largest element to the right

    Complexity:
    - Best Case = O(n)
    - Worst Case = O(n^2)
    """
    end = len(unordered_list) - 1
    performed_a_swap = True
    while performed_a_swap:
        performed_a_swap = False
        for i in xrange(end):
            if unordered_list[i] > unordered_list[i+1]:
                # bubble the larger one towards the end
                unordered_list[i], unordered_list[i+1] = unordered_list[i+1], unordered_list[i]
                performed_a_swap = True
        end -= 1
    return unordered_list # now ordered

bubblesort(TEST_ARRAY1)


def selection_sort(unordered_list):
    """
    Select the smallest element, and swap it to the front

    Complexity:
    - Best Case = O(n^2)
    - Worst Case = O(n^2)
    """
    list_len = len(unordered_list)
    for i in xrange(list_len):
        min_val = unordered_list[i]
        min_index = i
        for j in xrange(i+1,list_len):
            if unordered_list[j] < min_val:
                min_val = unordered_list[j]
                min_index = j

        unordered_list[i], unordered_list[min_index] = min_val, unordered_list[i]
    return unordered_list

selection_sort(TEST_ARRAY1)


def quicksort(unordered_list):
    """
    Pick a pivot, and move everything less than it to one side, and everything
    greater than it to the other. Quicksort the two sides.

    Complexity:
    - Best Case = O(nlogn)
    - Average Case = O(nlogn)
    - Worst Case = O(n^2)
    """
    if len(unordered_list) < 2:
        return unordered_list

    pivot, rest_of_list = unordered_list[0], unordered_list[1:]
    lt_pivot = [el for el in rest_of_list if el < pivot]
    gte_pivot = [el for el in rest_of_list if el >= pivot]
    return quicksort(lt_pivot) + [pivot] + quicksort(gte_pivot)

quicksort(TEST_ARRAY1)


def merge(sorted_list_a, sorted_list_b):
    result = []
    a_i = b_i = 0

    while a_i < len(sorted_list_a) or b_i < len(sorted_list_b):
        if sorted_list_a[a_i] < sorted_list_b[b_i]:
            result.append(sorted_list_a[a_i])
            a_i += 1
        else:
            result.append(sorted_list_b[b_i])
            b_i += 1

        # short circuit if one of the lists is done
        if a_i >= len(sorted_list_a):
            # done with list a
            result.extend(sorted_list_b[b_i:])
            b_i = len(sorted_list_b)
        elif b_i >= len(sorted_list_b):
            # done with list b
            result.extend(sorted_list_a[a_i:])
            a_i = len(sorted_list_a)

    return result

def mergesort(unordered_list):
    """
    Break the list into sublists, sort the sublists, and merge the sorted lists
    back together.

    Complexity:
    - Best Case = O(nlogn)
    - Average Case = O(nlogn)
    - Worst Case = O(nlogn)
    """
    if len(unordered_list) < 2:
        return unordered_list

    middle = len(unordered_list) / 2
    sorted_half1 = mergesort(unordered_list[:middle])
    sorted_half2 = mergesort(unordered_list[middle:])
    return merge(sorted_half1, sorted_half2)

mergesort(TEST_ARRAY1)

Add:

• Radix Sort
• In place quicksort
• real tests