Skip to content

Instantly share code, notes, and snippets.

@adampalay
Created May 4, 2018 16:02
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save adampalay/8779fb88fc0c206e64358c6b12e85337 to your computer and use it in GitHub Desktop.
Save adampalay/8779fb88fc0c206e64358c6b12e85337 to your computer and use it in GitHub Desktop.
Quicksort in Python
import unittest
from hypothesis import given
from hypothesis import strategies as st
def quicksort(numbers):
if len(numbers) == 0:
return numbers
else:
first = numbers[0]
remaining = numbers[1:]
sorted_remaining = quicksort(remaining)
less_than = [number for number in sorted_remaining if number <= first]
greater_than = [number for number in sorted_remaining if number > first]
return less_than + [first] + greater_than
class TestSort(unittest.TestCase):
def test_empty(self):
self.assertEqual(quicksort([]), [])
def test_sorted(self):
self.assertEqual(quicksort([1,2,3]), [1,2,3])
def test_unsorted(self):
self.assertEqual(quicksort([1,4,3,2]), [1,2,3,4])
@given(numbers=st.lists(st.integers()))
def test_same_length(self, numbers):
self.assertEqual(len(quicksort(numbers)), len(numbers))
if __name__ == '__main__':
unittest.main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment