python_sorts.py

import random
import threading
import time

# Credits to Martmists (Martmists#3740) for counting sort, slow sort, pigeonhole sort, and radix sort code.

def bubble_sort(seq):
  for i in range(len(seq)):
    for j in range(len(seq)-i-1):
      if seq[j] > seq[j+1]:
        seq[j], seq[j+1] = seq[j+1], seq[j]
  return seq

def insertion_sort(seq):
  for i in range(1, len(seq)):
    j = i-1
    while j >= 0 and seq[j] > seq[i]:
      j -= 1
    seq.insert(j+1, seq.pop(i))
  return seq

def selection_sort(seq):
  for i in range(len(seq)):
    min_idx = i
    for j in range(min_idx, len(seq)):
      if seq[j] < seq[min_idx]:
        min_idx = j
    seq[i], seq[min_idx] = seq[min_idx], seq[i]
  return seq

def merge_sort(seq):
  if len(seq) < 2:
    return seq
  middle = len(seq)//2
  first, second = seq[:middle], seq[middle:]
  return merge(merge_sort(first), merge_sort(second))

def merge(first, second):
  res = []
  i, j = 0, 0
  while len(res) < len(first) + len(second):
    if i == len(first) or j == len(second):
      res.extend(first[i:] or second[j:])
      break
    if first[i] < second[j]:
      res.append(first[i])
      i += 1
    else:
      res.append(second[j])
      j += 1
  return res

def quicksort(seq, start=0, end=None):
  if end is None:
    end = len(seq) - 1
  if start < end:
    idx = partition(seq, start, end)
    quicksort(seq, start, idx-1)
    quicksort(seq, idx+1, end)
    return seq
    
def partition(seq, start, end):
  pivot = end
  i = start
  for j in range(start, end+1):
    if seq[pivot] >= seq[j]:
      seq[i], seq[j] = seq[j], seq[i]
      i += 1
  return i-1

def bogosort(seq):
  if not is_sorted(seq):
    random.shuffle(seq)
    bogosort(seq)
  return seq

def is_sorted(seq):
  for i in range(len(seq)-1):
    if seq[i] > seq[i+1]:
      return False
  return True

def slow_sort(seq, start=0, end=None):
  if end is None:
    end = len(seq) - 1
  if start < end:
    middle = (start+end) // 2
    slow_sort(seq, start, middle)
    slow_sort(seq, middle+1, end)
    if seq[end] < seq[middle]:
      seq[end], seq[middle] = seq[middle], seq[end]
    slow_sort(seq, start, end-1)
  return seq

def counting_sort(seq):
  c = {i: 0 for i in range(min(seq), max(seq)+1)}
  for i in seq:
    c[i] += 1
  res = []
  for k, v in c.items():
    res += [k] * v
  return res

def stooge_sort(seq, start=0, end=None):
  if end is None:
    end = len(seq) - 1
  if seq[start] > seq[end]:
    seq[start], seq[end] = seq[end], seq[start]
  if (end - start + 1) > 2:
    third = (end - start + 1) // 3
    stooge_sort(seq, start, end-third)
    stooge_sort(seq, start+third, end)
    stooge_sort(seq, start, end-third)
  return seq

def sleep_adder(item, seq):
  time.sleep(item)
  seq.append(item)

def sleep_sort(seq):
  res = []
  threads = [threading.Thread(target=sleep_adder, args=(i, res)) for i in seq]
  for thread in threads:
    thread.start()
  for thread in threads:
    thread.join()
  return res

def radix_sort(data, base=10, place=1):
  maximum = max(data)
  while (maximum // place) > 0:
    data = companion_radix_sort(place, data, base)
    place *= base
  return data

def companion_radix_sort(place, data, base):
  result = [0] * len(data)
  counter = [0] * base
  for item in data:
    d = (item // place) % base
    counter[d] += 1
  for i in range(1, len(counter)):
    counter[i] += counter[i-1]
  for item in data[::-1]:
    d = (item // place) % base
    result[counter[d] - 1] = item
    counter[d] -= 1
  return result

def pigeonhole_sort(data):
  minimum = min(data)
  size = max(data) - minimum + 1
  holes = [0] * size
  for item in data:
    holes[item - minimum] += 1
  i = 0
  for count in range(size):
    while holes[count] > 0:
      holes[count] -= 1
      data[i] = count + minimum
      i += 1
  return data