274 lines
8.8 KiB
Python
274 lines
8.8 KiB
Python
"""
|
|
Test cases for Quicksort implementation.
|
|
"""
|
|
|
|
import unittest
|
|
import random
|
|
from typing import List
|
|
|
|
from src.quicksort import quicksort, randomized_quicksort, quicksort_3way
|
|
|
|
|
|
class TestQuicksort(unittest.TestCase):
|
|
"""Test cases for deterministic Quicksort."""
|
|
|
|
def test_empty_array(self):
|
|
"""Test sorting an empty array."""
|
|
arr = []
|
|
quicksort(arr)
|
|
self.assertEqual(arr, [])
|
|
|
|
result = quicksort([], in_place=False)
|
|
self.assertEqual(result, [])
|
|
|
|
def test_single_element(self):
|
|
"""Test sorting an array with a single element."""
|
|
arr = [42]
|
|
quicksort(arr)
|
|
self.assertEqual(arr, [42])
|
|
|
|
result = quicksort([42], in_place=False)
|
|
self.assertEqual(result, [42])
|
|
|
|
def test_two_elements(self):
|
|
"""Test sorting an array with two elements."""
|
|
arr = [2, 1]
|
|
quicksort(arr)
|
|
self.assertEqual(arr, [1, 2])
|
|
|
|
arr = [1, 2]
|
|
quicksort(arr)
|
|
self.assertEqual(arr, [1, 2])
|
|
|
|
def test_already_sorted(self):
|
|
"""Test sorting an already sorted array."""
|
|
arr = [1, 2, 3, 4, 5]
|
|
quicksort(arr)
|
|
self.assertEqual(arr, [1, 2, 3, 4, 5])
|
|
|
|
def test_reverse_sorted(self):
|
|
"""Test sorting a reverse-sorted array."""
|
|
arr = [5, 4, 3, 2, 1]
|
|
quicksort(arr)
|
|
self.assertEqual(arr, [1, 2, 3, 4, 5])
|
|
|
|
def test_random_array(self):
|
|
"""Test sorting a random array."""
|
|
arr = [3, 6, 8, 10, 1, 2, 1]
|
|
quicksort(arr)
|
|
self.assertEqual(arr, [1, 1, 2, 3, 6, 8, 10])
|
|
|
|
def test_duplicate_elements(self):
|
|
"""Test sorting an array with duplicate elements."""
|
|
arr = [5, 2, 8, 2, 9, 1, 5, 5]
|
|
quicksort(arr)
|
|
self.assertEqual(arr, [1, 2, 2, 5, 5, 5, 8, 9])
|
|
|
|
def test_negative_numbers(self):
|
|
"""Test sorting an array with negative numbers."""
|
|
arr = [-3, 5, -1, 0, -5, 2]
|
|
quicksort(arr)
|
|
self.assertEqual(arr, [-5, -3, -1, 0, 2, 5])
|
|
|
|
def test_large_array(self):
|
|
"""Test sorting a large array."""
|
|
import random
|
|
# Use random array to avoid worst-case recursion depth
|
|
arr = list(range(1, 501))
|
|
random.shuffle(arr)
|
|
quicksort(arr)
|
|
self.assertEqual(arr, list(range(1, 501)))
|
|
|
|
def test_in_place_sorting(self):
|
|
"""Test that in-place sorting modifies the original array."""
|
|
arr = [5, 2, 8, 1, 9]
|
|
original_id = id(arr)
|
|
result = quicksort(arr, in_place=True)
|
|
|
|
self.assertIsNone(result)
|
|
self.assertEqual(id(arr), original_id)
|
|
self.assertEqual(arr, [1, 2, 5, 8, 9])
|
|
|
|
def test_non_in_place_sorting(self):
|
|
"""Test that non-in-place sorting doesn't modify the original."""
|
|
arr = [5, 2, 8, 1, 9]
|
|
original = arr.copy()
|
|
result = quicksort(arr, in_place=False)
|
|
|
|
self.assertEqual(arr, original)
|
|
self.assertEqual(result, [1, 2, 5, 8, 9])
|
|
self.assertIsNotNone(result)
|
|
|
|
def test_custom_key_function(self):
|
|
"""Test sorting with a custom key function."""
|
|
arr = [{'value': 3}, {'value': 1}, {'value': 2}]
|
|
quicksort(arr, key=lambda x: x['value'])
|
|
self.assertEqual([x['value'] for x in arr], [1, 2, 3])
|
|
|
|
# Test with tuples
|
|
arr = [(2, 'b'), (1, 'a'), (3, 'c')]
|
|
quicksort(arr, key=lambda x: x[0])
|
|
self.assertEqual([x[0] for x in arr], [1, 2, 3])
|
|
|
|
|
|
class TestRandomizedQuicksort(unittest.TestCase):
|
|
"""Test cases for Randomized Quicksort."""
|
|
|
|
def test_empty_array(self):
|
|
"""Test sorting an empty array."""
|
|
arr = []
|
|
randomized_quicksort(arr, seed=42)
|
|
self.assertEqual(arr, [])
|
|
|
|
def test_single_element(self):
|
|
"""Test sorting an array with a single element."""
|
|
arr = [42]
|
|
randomized_quicksort(arr, seed=42)
|
|
self.assertEqual(arr, [42])
|
|
|
|
def test_random_array(self):
|
|
"""Test sorting a random array."""
|
|
arr = [3, 6, 8, 10, 1, 2, 1]
|
|
randomized_quicksort(arr, seed=42)
|
|
self.assertEqual(arr, [1, 1, 2, 3, 6, 8, 10])
|
|
|
|
def test_sorted_array(self):
|
|
"""Test sorting an already sorted array."""
|
|
arr = [1, 2, 3, 4, 5]
|
|
randomized_quicksort(arr, seed=42)
|
|
self.assertEqual(arr, [1, 2, 3, 4, 5])
|
|
|
|
def test_reverse_sorted_array(self):
|
|
"""Test sorting a reverse-sorted array."""
|
|
arr = [5, 4, 3, 2, 1]
|
|
randomized_quicksort(arr, seed=42)
|
|
self.assertEqual(arr, [1, 2, 3, 4, 5])
|
|
|
|
def test_reproducibility_with_seed(self):
|
|
"""Test that same seed produces same results."""
|
|
arr1 = [5, 2, 8, 1, 9, 3, 7, 4, 6]
|
|
arr2 = arr1.copy()
|
|
|
|
randomized_quicksort(arr1, seed=42)
|
|
randomized_quicksort(arr2, seed=42)
|
|
|
|
self.assertEqual(arr1, arr2)
|
|
self.assertEqual(arr1, [1, 2, 3, 4, 5, 6, 7, 8, 9])
|
|
|
|
def test_large_array(self):
|
|
"""Test sorting a large array."""
|
|
import random
|
|
# Use random array to avoid worst-case recursion depth
|
|
arr = list(range(1, 501))
|
|
random.shuffle(arr)
|
|
randomized_quicksort(arr, seed=42)
|
|
self.assertEqual(arr, list(range(1, 501)))
|
|
|
|
def test_in_place_sorting(self):
|
|
"""Test that in-place sorting modifies the original array."""
|
|
arr = [5, 2, 8, 1, 9]
|
|
original_id = id(arr)
|
|
result = randomized_quicksort(arr, in_place=True, seed=42)
|
|
|
|
self.assertIsNone(result)
|
|
self.assertEqual(id(arr), original_id)
|
|
self.assertEqual(arr, [1, 2, 5, 8, 9])
|
|
|
|
def test_non_in_place_sorting(self):
|
|
"""Test that non-in-place sorting doesn't modify the original."""
|
|
arr = [5, 2, 8, 1, 9]
|
|
original = arr.copy()
|
|
result = randomized_quicksort(arr, in_place=False, seed=42)
|
|
|
|
self.assertEqual(arr, original)
|
|
self.assertEqual(result, [1, 2, 5, 8, 9])
|
|
|
|
|
|
class TestQuicksort3Way(unittest.TestCase):
|
|
"""Test cases for Three-way Quicksort."""
|
|
|
|
def test_empty_array(self):
|
|
"""Test sorting an empty array."""
|
|
arr = []
|
|
quicksort_3way(arr)
|
|
self.assertEqual(arr, [])
|
|
|
|
def test_single_element(self):
|
|
"""Test sorting an array with a single element."""
|
|
arr = [42]
|
|
quicksort_3way(arr)
|
|
self.assertEqual(arr, [42])
|
|
|
|
def test_all_duplicates(self):
|
|
"""Test sorting an array with all duplicate elements."""
|
|
arr = [5, 5, 5, 5, 5]
|
|
quicksort_3way(arr)
|
|
self.assertEqual(arr, [5, 5, 5, 5, 5])
|
|
|
|
def test_many_duplicates(self):
|
|
"""Test sorting an array with many duplicate elements."""
|
|
arr = [3, 2, 3, 1, 3, 2, 1, 3, 2]
|
|
quicksort_3way(arr)
|
|
self.assertEqual(arr, [1, 1, 2, 2, 2, 3, 3, 3, 3])
|
|
|
|
def test_random_array(self):
|
|
"""Test sorting a random array."""
|
|
arr = [3, 6, 8, 10, 1, 2, 1]
|
|
quicksort_3way(arr)
|
|
self.assertEqual(arr, [1, 1, 2, 3, 6, 8, 10])
|
|
|
|
def test_sorted_array(self):
|
|
"""Test sorting an already sorted array."""
|
|
arr = [1, 2, 3, 4, 5]
|
|
quicksort_3way(arr)
|
|
self.assertEqual(arr, [1, 2, 3, 4, 5])
|
|
|
|
def test_large_array_with_duplicates(self):
|
|
"""Test sorting a large array with many duplicates."""
|
|
arr = [random.randint(0, 10) for _ in range(1000)]
|
|
expected = sorted(arr)
|
|
quicksort_3way(arr)
|
|
self.assertEqual(arr, expected)
|
|
|
|
|
|
class TestQuicksortEdgeCases(unittest.TestCase):
|
|
"""Test edge cases and special scenarios."""
|
|
|
|
def test_all_same_elements(self):
|
|
"""Test sorting an array where all elements are the same."""
|
|
arr = [7, 7, 7, 7, 7]
|
|
quicksort(arr)
|
|
self.assertEqual(arr, [7, 7, 7, 7, 7])
|
|
|
|
randomized_quicksort(arr, seed=42)
|
|
self.assertEqual(arr, [7, 7, 7, 7, 7])
|
|
|
|
def test_alternating_pattern(self):
|
|
"""Test sorting an array with alternating pattern."""
|
|
arr = [1, 5, 2, 4, 3]
|
|
quicksort(arr)
|
|
self.assertEqual(arr, [1, 2, 3, 4, 5])
|
|
|
|
def test_floating_point_numbers(self):
|
|
"""Test sorting an array with floating point numbers."""
|
|
arr = [3.5, 1.2, 4.8, 2.1, 5.9]
|
|
quicksort(arr)
|
|
self.assertEqual(arr, [1.2, 2.1, 3.5, 4.8, 5.9])
|
|
|
|
def test_strings(self):
|
|
"""Test sorting an array of strings."""
|
|
arr = ['banana', 'apple', 'cherry', 'date']
|
|
quicksort(arr)
|
|
self.assertEqual(arr, ['apple', 'banana', 'cherry', 'date'])
|
|
|
|
def test_mixed_types_with_key(self):
|
|
"""Test sorting with key function to handle mixed types."""
|
|
arr = [('b', 2), ('a', 1), ('c', 3)]
|
|
quicksort(arr, key=lambda x: x[1])
|
|
self.assertEqual([x[1] for x in arr], [1, 2, 3])
|
|
|
|
|
|
if __name__ == '__main__':
|
|
unittest.main()
|
|
|