'''
Testing code for Computer Science 1, Lecture 20 on sorting. This
assumes that the sort functions are all in file sorts.py, each taking
one list as its only argument, and that their names are ins_sort
and merge_sort

All tests are based on random permutations of integers.

- In most of our tests, these permutations are completely random,
  meaning that a value is equally likely to end up anywhere in the
  list.

- In the final test we will explore the implications of working
  with lists that are "almost sorted" by only moving values a small
  distance from the correct location.  You can see that insertion sort
  is very fast in this case by removing the # char in front of
  generate_local_perm

'''

import sorts_sol
import time
import random


def run_and_time(name, sort_fcn, v, known_v):
    '''
    Run the function passed as sort_fcn, timing its performance and
    double-checking if it correct.  The correctness check is probably
    not necessary.
    '''
    print "Testing " + name
    t0 = time.time()
    sort_fcn(v)
    t1 = time.time()
    print "Time: %.4f seconds" %(t1-t0)
    print "Is correct?", v==known_v
    print


def run_and_time_python_sort(v):
    '''
    Run and time the Python list sort function on the list.
    '''
    print "Running Python's list sort function"
    t0 = time.time()
    v.sort()
    t1 = time.time()
    print "Time: %.4f seconds" %(t1-t0)
    print



####################################################

if __name__ == '__main__':
    n = int(raw_input("Enter the number of values ==> "))
    print "----------"
    print "Running on %d values" %n
    print "----------"

    v = range(n)
    v1 = v[:]
    random.shuffle(v1)

    v2 = v1[:]
    v3 = v1[:]
    v4 = v1[:]

    run_and_time("selection sort", sorts_sol.ins_sort, v1, v )
    run_and_time("merge sort", sorts_sol.merge_sort, v3, v )   # passing functions as an arg to a fcn
    run_and_time_python_sort(v4 )