10570af981
- Implement Merge Sort and Quick Sort algorithms with instrumentation - Add Quick Sort pivot strategies: first, last, median_of_three, random - Create dataset generators for 5 dataset types (sorted, reverse, random, nearly_sorted, duplicates_heavy) - Build comprehensive benchmarking CLI with metrics collection - Add performance measurement (time, memory, comparisons, swaps) - Configure logging with rotating file handlers - Generate plots for time and memory vs size - Include comprehensive test suite with pytest - Add full documentation in README.md
162 lines
5.9 KiB
Python
162 lines
5.9 KiB
Python
"""Tests for sorting algorithms."""
|
|
import pytest
|
|
from typing import List
|
|
import random
|
|
|
|
from src.algorithms.merge_sort import merge_sort
|
|
from src.algorithms.quick_sort import quick_sort, PivotStrategy
|
|
|
|
|
|
class TestMergeSort:
|
|
"""Tests for merge sort algorithm."""
|
|
|
|
def test_empty_array(self) -> None:
|
|
"""Test sorting empty array."""
|
|
assert merge_sort([]) == []
|
|
|
|
def test_single_element(self) -> None:
|
|
"""Test sorting array with single element."""
|
|
assert merge_sort([42]) == [42]
|
|
|
|
def test_already_sorted(self) -> None:
|
|
"""Test sorting already sorted array."""
|
|
arr = [1, 2, 3, 4, 5]
|
|
assert merge_sort(arr) == [1, 2, 3, 4, 5]
|
|
# Original should not be modified
|
|
assert arr == [1, 2, 3, 4, 5]
|
|
|
|
def test_reverse_sorted(self) -> None:
|
|
"""Test sorting reverse sorted array."""
|
|
arr = [5, 4, 3, 2, 1]
|
|
assert merge_sort(arr) == [1, 2, 3, 4, 5]
|
|
|
|
def test_random_array(self) -> None:
|
|
"""Test sorting random array."""
|
|
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5]
|
|
assert merge_sort(arr) == [1, 1, 2, 3, 4, 5, 5, 6, 9]
|
|
|
|
def test_duplicates(self) -> None:
|
|
"""Test sorting array with duplicates."""
|
|
arr = [5, 5, 5, 3, 3, 1]
|
|
assert merge_sort(arr) == [1, 3, 3, 5, 5, 5]
|
|
|
|
def test_large_array(self) -> None:
|
|
"""Test sorting large array."""
|
|
arr = list(range(1000, 0, -1))
|
|
result = merge_sort(arr)
|
|
assert result == list(range(1, 1001))
|
|
|
|
def test_instrumentation(self) -> None:
|
|
"""Test instrumentation callback."""
|
|
counters: dict = {"comparison": 0, "swap": 0}
|
|
|
|
def instrument(op: str) -> None:
|
|
if op in counters:
|
|
counters[op] += 1
|
|
|
|
arr = [3, 1, 4, 1, 5]
|
|
result = merge_sort(arr, instrument=instrument)
|
|
|
|
assert result == [1, 1, 3, 4, 5]
|
|
assert counters["comparison"] > 0
|
|
# Merge sort doesn't do swaps in traditional sense
|
|
assert counters["swap"] == 0
|
|
|
|
|
|
class TestQuickSort:
|
|
"""Tests for quick sort algorithm."""
|
|
|
|
@pytest.mark.parametrize("pivot", ["first", "last", "median_of_three", "random"])
|
|
def test_empty_array(self, pivot: PivotStrategy) -> None:
|
|
"""Test sorting empty array."""
|
|
assert quick_sort([], pivot_strategy=pivot) == []
|
|
|
|
@pytest.mark.parametrize("pivot", ["first", "last", "median_of_three", "random"])
|
|
def test_single_element(self, pivot: PivotStrategy) -> None:
|
|
"""Test sorting array with single element."""
|
|
assert quick_sort([42], pivot_strategy=pivot) == [42]
|
|
|
|
@pytest.mark.parametrize("pivot", ["first", "last", "median_of_three", "random"])
|
|
def test_already_sorted(self, pivot: PivotStrategy) -> None:
|
|
"""Test sorting already sorted array."""
|
|
arr = [1, 2, 3, 4, 5]
|
|
result = quick_sort(arr, pivot_strategy=pivot, seed=42)
|
|
assert result == [1, 2, 3, 4, 5]
|
|
# Original should not be modified
|
|
assert arr == [1, 2, 3, 4, 5]
|
|
|
|
@pytest.mark.parametrize("pivot", ["first", "last", "median_of_three", "random"])
|
|
def test_reverse_sorted(self, pivot: PivotStrategy) -> None:
|
|
"""Test sorting reverse sorted array."""
|
|
arr = [5, 4, 3, 2, 1]
|
|
result = quick_sort(arr, pivot_strategy=pivot, seed=42)
|
|
assert result == [1, 2, 3, 4, 5]
|
|
|
|
@pytest.mark.parametrize("pivot", ["first", "last", "median_of_three", "random"])
|
|
def test_random_array(self, pivot: PivotStrategy) -> None:
|
|
"""Test sorting random array."""
|
|
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5]
|
|
result = quick_sort(arr, pivot_strategy=pivot, seed=42)
|
|
assert result == [1, 1, 2, 3, 4, 5, 5, 6, 9]
|
|
|
|
@pytest.mark.parametrize("pivot", ["first", "last", "median_of_three", "random"])
|
|
def test_duplicates(self, pivot: PivotStrategy) -> None:
|
|
"""Test sorting array with duplicates."""
|
|
arr = [5, 5, 5, 3, 3, 1]
|
|
result = quick_sort(arr, pivot_strategy=pivot, seed=42)
|
|
assert result == [1, 3, 3, 5, 5, 5]
|
|
|
|
@pytest.mark.parametrize("pivot", ["first", "last", "median_of_three", "random"])
|
|
def test_large_array(self, pivot: PivotStrategy) -> None:
|
|
"""Test sorting large array."""
|
|
arr = list(range(1000, 0, -1))
|
|
result = quick_sort(arr, pivot_strategy=pivot, seed=42)
|
|
assert result == list(range(1, 1001))
|
|
|
|
def test_instrumentation(self) -> None:
|
|
"""Test instrumentation callback."""
|
|
counters: dict = {"comparison": 0, "swap": 0}
|
|
|
|
def instrument(op: str) -> None:
|
|
if op in counters:
|
|
counters[op] += 1
|
|
|
|
arr = [3, 1, 4, 1, 5]
|
|
result = quick_sort(arr, pivot_strategy="first", instrument=instrument, seed=42)
|
|
|
|
assert result == [1, 1, 3, 4, 5]
|
|
assert counters["comparison"] > 0
|
|
assert counters["swap"] > 0
|
|
|
|
|
|
class TestPropertyTests:
|
|
"""Property-based tests comparing to Python's sorted()."""
|
|
|
|
@pytest.mark.parametrize("size", [10, 100, 1000])
|
|
def test_merge_sort_property(self, size: int) -> None:
|
|
"""Property test: merge_sort should match sorted() for random arrays."""
|
|
random.seed(42)
|
|
arr = [random.randint(-1000, 1000) for _ in range(size)]
|
|
|
|
result = merge_sort(arr)
|
|
expected = sorted(arr)
|
|
|
|
assert result == expected
|
|
|
|
@pytest.mark.parametrize("pivot", ["first", "last", "median_of_three", "random"])
|
|
@pytest.mark.parametrize("size", [10, 100, 1000])
|
|
def test_quick_sort_property(self, pivot: PivotStrategy, size: int) -> None:
|
|
"""Property test: quick_sort should match sorted() for random arrays."""
|
|
random.seed(42)
|
|
arr = [random.randint(-1000, 1000) for _ in range(size)]
|
|
|
|
result = quick_sort(arr, pivot_strategy=pivot, seed=42)
|
|
expected = sorted(arr)
|
|
|
|
assert result == expected
|
|
|
|
|
|
if __name__ == "__main__":
|
|
pytest.main([__file__, "-v"])
|
|
|