Sorting algorithms

Sorting.py

#!/usr/bin/env python3

"""
Sorting algorithms

Created By YieldNull at 4/14/16
"""


def insertion_sort(lst):
    for i in range(1, len(lst)):
        ptr = i - 1
        temp = lst[i]

        while ptr >= 0 and temp < lst[ptr]:
            lst[ptr + 1] = lst[ptr]
            ptr -= 1
        lst[ptr + 1] = temp

    return lst


def selection_sort(lst):
    def _min(start):
        value = lst[start]
        index = start
        for i in range(start + 1, len(lst)):
            if lst[i] < value:
                value = lst[i]
                index = i
        return index

    for i in range(len(lst) - 1):
        min_index = _min(i)
        if min_index != i:
            lst[i], lst[min_index] = lst[min_index], lst[i]

    return lst


def merge_sort(lst):
    last = len(lst) - 1

    def merge(left, right, count):
        temp = []
        end = right + count - 1 if right + count - 1 <= last else last

        p_left = left
        p_right = right

        while p_left < right and p_right <= end:
            if lst[p_left] <= lst[p_right]:
                temp.append(lst[p_left])
                p_left += 1
            else:
                temp.append(lst[p_right])
                p_right += 1

        if p_left <= right - 1:
            temp += lst[p_left:right]

        if p_right <= end:
            temp += lst[p_right: end + 1]

        for i in range(len(temp)):
            lst[left + i] = temp[i]

    count = 1
    while count < len(lst):
        left = 0
        right = count
        while right <= last:
            merge(left, right, count)
            left += count * 2
            right += count * 2

        count *= 2

    return lst


def heap_sort(lst):
    def heapify():
        for start in range(((len(lst) - 1) // 2), -1, -1):
            shift_down(start, len(lst) - 1)

    def shift_down(start, end):
        if start * 2 + 1 > end:
            return

        left_index = start * 2 + 1
        right_index = start * 2 + 2

        parent = lst[start]
        left = lst[left_index]
        right = lst[right_index] if right_index <= end else left - 1

        if parent < max(left, right):
            if left > right:
                lst[start], lst[left_index] = lst[left_index], lst[start]
                shift_down(left_index, end)
            else:
                lst[start], lst[right_index] = lst[right_index], lst[start]
                shift_down(right_index, end)

    heapify()

    for end in range(len(lst) - 1, 0, -1):
        lst[0], lst[end] = lst[end], lst[0]
        shift_down(0, end - 1)

    return lst


def quick_sort(lst):
    def sort(left, right):
        if left < right:
            p_left = left
            p_right = right + 1

            while p_left < p_right:
                p_left += 1
                p_right -= 1

                while p_left <= right and lst[p_left] < lst[left]:
                    p_left += 1

                while p_right >= left and lst[p_right] > lst[left]:
                    p_right -= 1

                if p_left < p_right:
                    lst[p_left], lst[p_right] = lst[p_right], lst[p_left]

            lst[left], lst[p_right] = lst[p_right], lst[left]

            sort(left, p_right - 1)
            sort(p_right + 1, right)

    sort(0, len(lst) - 1)
    return lst


def bubble_sort(lst):
    for end in range(len(lst) - 1, 0, -1):
        swapped = False
        for i in range(end):
            if lst[i] > lst[i + 1]:
                lst[i], lst[i + 1] = lst[i + 1], lst[i]
                swapped = True
        if not swapped:
            break

    return lst


def shell_sort(lst):
    gap = len(lst) // 2

    while gap >= 1:
        for start in range(gap):
            for i in range(start, len(lst), gap):
                # insertion
                ptr = i - gap
                temp = lst[i]

                while ptr >= 0 and temp < lst[ptr]:
                    lst[ptr + gap] = lst[ptr]
                    ptr -= gap
                lst[ptr + gap] = temp
        gap //= 2

    return lst


if __name__ == '__main__':
    import random

    lst = [random.randrange(1000) for i in range(100)]

    insertion = lst.copy()
    insertion = insertion_sort(insertion)

    selection = lst.copy()
    selection = selection_sort(selection)

    bubble = lst.copy()
    bubble = bubble_sort(bubble)

    merge = lst.copy()
    merge = merge_sort(merge)

    heap = lst.copy()
    heap = heap_sort(heap)

    quick = lst.copy()
    quick = quick_sort(quick)

    shell = lst.copy()
    shell = shell_sort(shell)

    out_format = '{:>16} : {}'
    print(out_format.format('origin list', lst))
    print(out_format.format('python library', sorted(lst)))

    print(out_format.format('insertion sort', insertion))
    print(out_format.format('selection sort', selection))

    print(out_format.format('bubble sort', bubble))

    print(out_format.format('merge sort', merge))
    print(out_format.format('heap sort', heap))
    print(out_format.format('quick sort', quick))

    print(out_format.format('shell sort', shell))

    print(out_format.format('identical', insertion == selection == bubble == merge == heap == quick == shell))