Basic sort comparison

sort.py

import random


def select(seq, start):
    min_index = start

    for j in range(start + 1, len(seq)):
        if seq[min_index] > seq[j]:
            min_index = j

    return min_index


def selection_sort(seq):
    ###
    # Selection sort orders by finding the smallest item in a given list
    # and swapping it with the leftmost element, then repeating that
    # with sub-lists excluding the left 'sorted part' until the
    # entire list is ordered.
    ###
    for i in range(len(seq) - 1):
        min_index = select(seq, i)
        seq[i], seq[min_index] = seq[min_index], seq[i]


def merge(seq, start, mid, stop):
    lst = []
    i = start
    j = mid

    # merge the two lists while each has more elements
    while i < mid and j < stop:
        if seq[i] < seq[j]:
            lst.append(seq[i])
            i += 1
        else:
            lst.append(seq[j])
            j += 1

    # copy the rest of the first half sequence
    while i < mid:
        lst.append(seq[i])
        i += 1

    # this can be optimized out size the next step this work is redone.
    # while j < stop:
    #     lst.append(seq[j])
    #     j+=1

    for i in range(len(lst)):
        seq[start + i] = lst[i]


def merge_sort_recursively(seq, start, stop):
    if start >= stop - 1:
        return

    mid = (start + stop) // 2

    merge_sort_recursively(seq, start, mid)
    merge_sort_recursively(seq, mid, stop)
    merge(seq, start, mid, stop)


def merge_sort(seq):
    ###
    # Merge sort works by splitting the list in half until it has "sorted"
    # single element lists. It then, works back up the call stack and merges
    # sorted lists together until the whole list is merged
    ###
    merge_sort_recursively(seq, 0, len(seq))


def generate_list(x=None):
    lst = []
    for i in range(100):
        lst.append(random.randint(0, 100000))
    if x:
        print(f'list {x+1} generated.')
    return lst


def partition(seq, start, stop):
    pivot_index = start
    pivot = seq[pivot_index]
    i = start + 1
    j = stop - 1

    while i <= j:
        # 'close the gap' between i and j until values are found
        # that need to be swapped (e.g. something on the right that is
        # less than the pivot stops the i loop, something on the left
        # that is > pivot stops j, those two swap)
        while i <= j and not pivot < seq[i]:
            i += 1

        while i <= j and pivot < seq[j]:
            j -= 1

        if i < j:
            seq[i], seq[j] = seq[j], seq[i]
            i += 1
            j -= 1

    # everything is semi-ordered after the pivot. swap the pivot into
    # its proper location now.
    seq[pivot_index] = seq[j]
    seq[j] = pivot

    return j


def quicksort_recursive(seq, start, stop):
    if start >= stop - 1:
        return

    pivot_index = partition(seq, start, stop)

    quicksort_recursive(seq, start, pivot_index)
    quicksort_recursive(seq, pivot_index + 1, stop)


def quicksort(seq):
    """
    quicksort works by partitioning the incoming sequence into
    :param seq:
    :return:
    """
    for i in range(len(seq)):
        j = random.randint(0, len(seq)-1)
        seq[i], seq[j] = seq[j], seq[i]

    quicksort_recursive(seq, 0, len(seq))


def main():
    import time

    run_timed_tests = True
    # lst = [5, 8, 2, 6, 9, 1, 0, 7]
    # lst = generate_list()

    # selection_sort(lst)
    # merge_sort(lst)
    # quicksort(lst)

    # print(lst)

    def timed_tests():
        iter_count = 100
        test_lists = [generate_list(x) for x in range(iter_count)]

        start_time = time.time()
        for lst in test_lists:
            selection_sort(lst)
        stop_time = time.time()
        selection_sorting_time = (stop_time - start_time)
        print(f'selection sort average sort time: {selection_sorting_time / iter_count}')

        start_time = time.time()
        for lst in test_lists:
            merge_sort(lst)
        stop_time = time.time()
        merge_sorting_time = (stop_time - start_time)
        print(f'merge sort average sort time: {merge_sorting_time / iter_count}')

        start_time = time.time()
        for lst in test_lists:
            quicksort(lst)
        stop_time = time.time()
        quick_sorting_time = (stop_time - start_time)
        print(f'quick sort average sort time: {quick_sorting_time / iter_count}')


        print(f'Merge sort is {selection_sorting_time / merge_sorting_time}x faster than selection')
        print(f'Quick sort is {selection_sorting_time / quick_sorting_time}x faster than selection')

    if run_timed_tests:
        timed_tests()


if __name__ == "__main__":
    main()