Python Sorts

sorts_n2.py

import random

def selection_sort(a: list):
    length = len(a)
    for i in range(length):
        current_min_i = i
        current_min = a[i]
        for j in range(i + 1, length):
            if a[j] < current_min:
                current_min = a[j]
                current_min_i = j
        a[i], a[current_min_i] = current_min, a[i]

def bubble_sort(a: list):
    length = len(a)
    for i in range(length):
        for j in range(i, length):
            if a[j] < a[i]:
                a[i], a[j] = a[j], a[i]

def shaker_sort(a: list):
    left = 0
    right = len(a) - 1
    while left <= right:
        for i in range(left, right):
            if a[i] > a[i + 1]:
                a[i], a[i + 1] = a[i + 1], a[i]
        right -= 1
        for i in range(right, left, -1):
            if a[i] < a[i - 1]:
                a[i], a[i - 1] = a[i - 1], a[i]
        left += 1

def gnome_sort(a: list):
    length = len(a)
    for i in range(1, length):
        j = i
        while j >= 1 and a[j] < a[j-1]:
            a[j], a[j-1] = a[j-1], a[j]
            j -= 1

sorts_nlogn.py

import random

def qsort(a: list):
    if len(a) < 2:
        return a
    pivot = random.choice(a)
    less = [n for n in a if n < pivot]
    equal = [n for n in a if n == pivot]
    great = [n for n in a if n > pivot]
    return qsort(less) + equal + qsort(great)

def qsort1(a: list):
    length = len(a)
    result = qsort(a)
    for i in range(length):
        a[i] = result[i]

def merge(a: list, b: list):
    a_len = len(a)
    b_len = len(b)
    result = [0] * (a_len + b_len)
    a_idx = 0
    b_idx = 0
    result_idx = 0
    while a_idx < a_len and b_idx < b_len:
      if a[a_idx] <= b[b_idx]:
        result[result_idx] = a[a_idx]
        a_idx += 1
      else:
        result[result_idx] = b[b_idx]
        b_idx += 1
      result_idx += 1
    while a_idx < a_len:
      result[result_idx] = a[a_idx]
      a_idx += 1
      result_idx += 1
    while b_idx < b_len:
      result[result_idx] = b[b_idx]
      b_idx += 1
      result_idx += 1
    return result

def merge_sort(a: list):
    length = len(a)
    if length < 2:
      return a
    middle_idx = length // 2
    left_part = a[:middle_idx]
    right_part = a[middle_idx:]
    merge_sort(left_part)
    merge_sort(right_part)
    result = merge(left_part, right_part)
    for i in range(length):
      a[i] = result[i]

sorts_test.py

from timeit import default_timer as timer
from matplotlib import pyplot as plt
import sorts_n2
import sorts_nlogn
import random
import gc

colors = ('b', 'g', 'r', 'c', 'm', 'y', 'k', 'w')
color_i = 0

def test(sort_m, color_i):
    results = [0] * 1001
    for _ in range(50):
        for i in range(1001):
            sorted_list = [random.randint(0, 9) for n in range(i)]
            #chk = sorted(sorted_list)
            start = timer()
            sort_m(sorted_list)
            stop = timer()
            #if sorted_list != chk:
            #    raise ValueError(sort_m.__name__ + ' bad sort with '
            #                     + str(i-1) + 'elements')
            results[i] += stop - start
    for i in range(1001):
        results[i] /= 50
    plt.plot(results, colors[color_i], alpha=0.5, label=sort_m.__name__)

sorted_methods = [
    sorts_n2.selection_sort,
    sorts_n2.bubble_sort,
    sorts_n2.shaker_sort,
    sorts_n2.gnome_sort,
    sorts_nlogn.merge_sort
                ]
gc.disable()
for sorted_method in sorted_methods:
    test(sorted_method, color_i)
    color_i += 1
    gc.collect()
plt.title('Sorts')
plt.legend(loc='upper left')
plt.xlabel('n')
plt.ylabel('sort time')
plt.show()