joke_sorts.py

#!/usr/bin/env python2

import random
import re
import threading
import time
import sys

class JokeSorts:
 @classmethod
 def _check(cls, unsorted):
  iter(unsorted) # raises a TypeError if not iterable
  for i in unsorted:
   if not isinstance(i, (int, long)):
    raise TypeError("elements must be ints or longs")
 @classmethod
 def _is_sorted(cls, unsorted):
  cls._check(unsorted)
  n = None
  for i in unsorted:
   if n != None and i < n:
    return False
   n = i
  return True
 
 @classmethod
 def sleep(cls, unsorted):
  cls._check(unsorted)
  
  lock = [False]
  n_timers = [0]
  sorted_ = list()
  def put(i, n_timers):
   while lock[0] == True:
    time.sleep(0.1)
   lock[0] = True
   sorted_.append(i)
   n_timers[0] -= 1
   lock[0] = False
  
  for i in unsorted:
   n_timers[0] += 1
   threading.Timer(i / 100., put, args=(i, n_timers)).start()
  
  while n_timers[0] > 0:
   time.sleep(0.1)
  return sorted_
 
 @classmethod
 def bogo(cls, unsorted, efficient=False):
  cls._check(unsorted)
  sorted_ = list(unsorted[:])
  
  while not cls._is_sorted(sorted_):
   unsorted = sorted_
   sorted_ = []
   while len(unsorted) > 0:
    sorted_ += [unsorted.pop(random.randint(0, len(unsorted) - 1))]
   if efficient:
    if cls._is_sorted(reversed(sorted_)):
     sorted_.reverse()
  return sorted_
 @classmethod
 def efficient_bogo(cls, unsorted):
  return cls.bogo(unsorted, efficient=True)
 @classmethod
 def random(cls, unsorted, efficient=False):
  return cls.bogo(unsorted, efficient)
 @classmethod
 def efficient_random(cls, unsorted):
  return cls.random(unsorted, efficient=True)
 
 @classmethod
 def string(cls, unsorted, string=None, efficient=False):
  if string == None:
   string = "YOUR FACE "
  
  cls._check(unsorted)
  unsorted = list(unsorted[:])
  sorted_ = []
  negatives = []
  
  # convert everything in unsorted to strings and keep track of the negatives
  for i in range(len(unsorted)):
   negatives += [unsorted[i] < 0]
   unsorted[i] = (string + " ") * (abs(unsorted[i]) + 1)
   # Get rid of the trailing space
   if efficient:
    unsorted[i] = unsorted[i][:-1]
   else:
    unsorted[i] = unsorted[i].strip()
  
  # selection sort; we obviously don't care about efficiency :P
  sorted_ = unsorted[:]
  for i in range(len(sorted_)):
   for j in range(i + 1, len(sorted_)):
    n_i = -len(sorted_[i]) if negatives[i] else len(sorted_[i])
    n_j = -len(sorted_[j]) if negatives[j] else len(sorted_[j])
    if n_i > n_j:
     tmp = sorted_[i]
     sorted_[i] = sorted_[j]
     sorted_[j] = tmp
     tmp = negatives[i]
     negatives[i] = negatives[j]
     negatives[j] = tmp
  
  # convert strings to numbers by dividing the length of the sorted string
  # plus 1 by the length of the base string plus the space separating each
  # occurrence of the base string, then subtracting 1 from that result to
  # account for the fact that there is no trailing space at the end.  Then
  # we generate the string again using that number, compare the two strings,
  # and if they don't match, then fall back to an algorithm that works by
  # keeping a counter, building a temporary string, comparing the strings,
  # and storing the counter when the strings match.
  #
  # The end result from either algorithm is negated if necessary.
  for i in range(len(sorted_)):
   n = ((len(sorted_[i]) + 1) / len(string + " ")) - 1
   s = (string + " ") * (n + 1)
   if efficient:
    s = s[:-1]
   else:
    s = s.strip()
   if not efficient or sorted_[i] != s:
    s = string.strip() if not efficient else string
    n = 0
    while s != sorted_[i]:
     n += 1
     s += " " + (string.strip() if not efficient else string)
   sorted_[i] = n
   if negatives[i]:
    sorted_[i] = -n
 
  return sorted_
 @classmethod
 def efficient_string(cls, unsorted, string=None):
  return cls.string(unsorted, string=string, efficient=True)
 
 @classmethod
 def _main(cls, argv):
  usage = "Usage: %s {algorithm} [-e|--efficient] test|{number [...]}\n" % argv[0]
  usage += "Algorithms: sleep, bogo/random, string"
  if len(argv) < 3:
   print >> sys.stderr, usage
   return 2
  
  algorithm = argv[1].replace("-", "_")
  if algorithm.startswith("_") or not callable(getattr(cls, algorithm, None)):
   print >> sys.stderr, usage
   return 2
  sort = getattr(cls, algorithm)
  
  if argv[2] in ("-e", "--efficient"):
   nums = argv[3:]
   efficient_sort = getattr(cls, "efficient_" + algorithm, None)
   if efficient_sort:
    sort = efficient_sort
   else:
    print >> sys.stderr, "warning: no efficient implementation of %s sort" % algorithm
  else:
   nums = argv[2:]
  
  if nums[0] == "test":
   unsorted = (9,3,6,1,7,2,8,2,10,324,2432,234)
  else:
   unsorted = [(int(i) if re.match(r"^-?[0-9]+$", i) else i) for i in nums]
  
  try:
   print sort(unsorted)
  except TypeError as exc:
   print >> sys.stderr, exc
   return 2

def main(argv):
 return JokeSorts._main(argv)

if __name__ == "__main__":
 try:
  sys.exit(main(sys.argv))
 except KeyboardInterrupt:
  pass