# Software testing exercise: Hoare's FIND
#
# ** Requirements
#
# Debian/Ubuntu:
# $ sudo aptitude install python-hypothesis python-pytest python-pytest-cov
#
# You may also install the equivalent packages using pip or another
# package manager; the names will slightly vary.
#
# ** Reminder on how to run
#
# Running your program should NOT run tests:
# $ python ./find.py
#
# Tests should be executed using pytest:
# $ pytest find.py
# $ pytest --hypothesis-show-statistics find.py 
# $ pytest --cov=. find.py
#
# FYI here's how to obtain a coverage report for the
# normal execution of your file:
# $ python-coverage run find.py
# $ python-coverage html
#
# ** Instructions
#
# Implement the functions partition and sort below. Each one must
# be unit-tested, with at least one randomized test using hypothesis.
# The test coverage should be complete (all lines except __main__).
# Warning: do not roll your own testing system !
# Use pytest and hypothesis in a standard way, otherwise you'll likely
# violate one of the key ideas explained during the lecture...

import hypothesis
from hypothesis import given
from hypothesis.strategies import integers, lists

# The function partition(a,mid) takes an array a and a mid-value mid
# and permutes the elements of a to put
#  * first the elements strictly smaller than mid,
#  * then the elements equal to it,
#  * and finally the strictly larger elements.
#
# This permutation can be operated in place, or a new array can be returned.
#
# The function should also return two indices indicating the boundaries
# of the three zones. The precise semantics of these indices is left up to
# you.
#
# The implementation should proceed in a single traversal of the array
# (a priori maintaining three indices during that traversal, and swapping
# elements of the array). An implementation using filter(), map() and
# array concatenation() is forbidden, as it would kill the exercise.
def partition(a,mid):
    # TODO
    assert False

# Implement sorting by recursively calling the above partition function.
# The choice of mid-value is not specified. A naive choice (e.g. the
# first element of the array) is accepted.
def sort(a):
    # TODO
    assert False

if __name__ == "__main__":
    print "Hello, and goodbye."