659 lines
24 KiB
Python
659 lines
24 KiB
Python
#!/usr/bin/env python3
|
||
"""
|
||
Comprehensive Test Suite for Insertion Sort - Decreasing Order
|
||
|
||
This module contains extensive test cases for the insertion sort implementation,
|
||
including unit tests, edge cases, performance tests, and stress tests.
|
||
"""
|
||
|
||
import unittest
|
||
import random
|
||
import time
|
||
import sys
|
||
from typing import List, Tuple
|
||
|
||
# Import the functions to test
|
||
from insertion_sort_decreasing import insertion_sort_decreasing, insertion_sort_decreasing_inplace
|
||
|
||
|
||
class TestInsertionSortDecreasing(unittest.TestCase):
|
||
"""Test cases for insertion_sort_decreasing function."""
|
||
|
||
def test_basic_sorting(self):
|
||
"""Test basic sorting functionality."""
|
||
test_cases = [
|
||
([5, 2, 8, 1, 9, 3], [9, 8, 5, 3, 2, 1]),
|
||
([64, 34, 25, 12, 22, 11, 90], [90, 64, 34, 25, 22, 12, 11]),
|
||
([3, 1, 4, 1, 5, 9, 2, 6], [9, 6, 5, 4, 3, 2, 1, 1]),
|
||
]
|
||
|
||
for input_arr, expected in test_cases:
|
||
with self.subTest(input_arr=input_arr):
|
||
result = insertion_sort_decreasing(input_arr)
|
||
self.assertEqual(result, expected)
|
||
|
||
def test_already_sorted_ascending(self):
|
||
"""Test arrays already sorted in ascending order."""
|
||
test_cases = [
|
||
([1, 2, 3, 4, 5], [5, 4, 3, 2, 1]),
|
||
([1, 2, 3], [3, 2, 1]),
|
||
([1], [1]),
|
||
]
|
||
|
||
for input_arr, expected in test_cases:
|
||
with self.subTest(input_arr=input_arr):
|
||
result = insertion_sort_decreasing(input_arr)
|
||
self.assertEqual(result, expected)
|
||
|
||
def test_already_sorted_descending(self):
|
||
"""Test arrays already sorted in descending order."""
|
||
test_cases = [
|
||
([5, 4, 3, 2, 1], [5, 4, 3, 2, 1]),
|
||
([10, 8, 6, 4, 2], [10, 8, 6, 4, 2]),
|
||
([3, 2, 1], [3, 2, 1]),
|
||
]
|
||
|
||
for input_arr, expected in test_cases:
|
||
with self.subTest(input_arr=input_arr):
|
||
result = insertion_sort_decreasing(input_arr)
|
||
self.assertEqual(result, expected)
|
||
|
||
def test_empty_array(self):
|
||
"""Test empty array."""
|
||
result = insertion_sort_decreasing([])
|
||
self.assertEqual(result, [])
|
||
|
||
def test_single_element(self):
|
||
"""Test arrays with single element."""
|
||
test_cases = [
|
||
([1], [1]),
|
||
([42], [42]),
|
||
([0], [0]),
|
||
([-5], [-5]),
|
||
]
|
||
|
||
for input_arr, expected in test_cases:
|
||
with self.subTest(input_arr=input_arr):
|
||
result = insertion_sort_decreasing(input_arr)
|
||
self.assertEqual(result, expected)
|
||
|
||
def test_duplicate_elements(self):
|
||
"""Test arrays with duplicate elements."""
|
||
test_cases = [
|
||
([3, 3, 3, 3], [3, 3, 3, 3]),
|
||
([5, 2, 5, 2, 5], [5, 5, 5, 2, 2]),
|
||
([1, 1, 2, 2, 3, 3], [3, 3, 2, 2, 1, 1]),
|
||
]
|
||
|
||
for input_arr, expected in test_cases:
|
||
with self.subTest(input_arr=input_arr):
|
||
result = insertion_sort_decreasing(input_arr)
|
||
self.assertEqual(result, expected)
|
||
|
||
def test_negative_numbers(self):
|
||
"""Test arrays with negative numbers."""
|
||
test_cases = [
|
||
([-1, -2, -3, -4, -5], [-1, -2, -3, -4, -5]),
|
||
([5, -2, 8, -1, 9, -3], [9, 8, 5, -1, -2, -3]),
|
||
([-10, 5, -3, 0, 2], [5, 2, 0, -3, -10]),
|
||
]
|
||
|
||
for input_arr, expected in test_cases:
|
||
with self.subTest(input_arr=input_arr):
|
||
result = insertion_sort_decreasing(input_arr)
|
||
self.assertEqual(result, expected)
|
||
|
||
def test_zero_values(self):
|
||
"""Test arrays containing zero values."""
|
||
test_cases = [
|
||
([0, 1, 2, 3], [3, 2, 1, 0]),
|
||
([5, 0, -2, 0, 3], [5, 3, 0, 0, -2]),
|
||
([0, 0, 0], [0, 0, 0]),
|
||
]
|
||
|
||
for input_arr, expected in test_cases:
|
||
with self.subTest(input_arr=input_arr):
|
||
result = insertion_sort_decreasing(input_arr)
|
||
self.assertEqual(result, expected)
|
||
|
||
def test_large_numbers(self):
|
||
"""Test arrays with large numbers."""
|
||
test_cases = [
|
||
([1000000, 999999, 1000001], [1000001, 1000000, 999999]),
|
||
([2**31 - 1, 2**31 - 2, 2**31 - 3], [2**31 - 1, 2**31 - 2, 2**31 - 3]),
|
||
]
|
||
|
||
for input_arr, expected in test_cases:
|
||
with self.subTest(input_arr=input_arr):
|
||
result = insertion_sort_decreasing(input_arr)
|
||
self.assertEqual(result, expected)
|
||
|
||
def test_original_array_unchanged(self):
|
||
"""Test that original array is not modified."""
|
||
original = [5, 2, 8, 1, 9, 3]
|
||
original_copy = original.copy()
|
||
result = insertion_sort_decreasing(original)
|
||
|
||
self.assertEqual(original, original_copy)
|
||
self.assertNotEqual(result, original)
|
||
|
||
def test_sorting_stability(self):
|
||
"""Test that sorting is stable (equal elements maintain relative order)."""
|
||
# For insertion sort, stability means equal elements keep their original order
|
||
input_arr = [(5, 'a'), (3, 'b'), (5, 'c'), (3, 'd')]
|
||
result = insertion_sort_decreasing(input_arr)
|
||
|
||
# Check that elements with same first value maintain their order
|
||
# Since we're sorting by the first element in decreasing order,
|
||
# all 5s should come before all 3s, and within each group,
|
||
# the original order should be preserved
|
||
self.assertEqual(result[0], (5, 'c')) # First 5 should be 'c' (stable)
|
||
self.assertEqual(result[1], (5, 'a')) # Second 5 should be 'a' (stable)
|
||
self.assertEqual(result[2], (3, 'd')) # First 3 should be 'd' (stable)
|
||
self.assertEqual(result[3], (3, 'b')) # Second 3 should be 'b' (stable)
|
||
|
||
|
||
class TestInsertionSortDecreasingInplace(unittest.TestCase):
|
||
"""Test cases for insertion_sort_decreasing_inplace function."""
|
||
|
||
def test_basic_sorting(self):
|
||
"""Test basic sorting functionality."""
|
||
test_cases = [
|
||
([5, 2, 8, 1, 9, 3], [9, 8, 5, 3, 2, 1]),
|
||
([64, 34, 25, 12, 22, 11, 90], [90, 64, 34, 25, 22, 12, 11]),
|
||
([3, 1, 4, 1, 5, 9, 2, 6], [9, 6, 5, 4, 3, 2, 1, 1]),
|
||
]
|
||
|
||
for input_arr, expected in test_cases:
|
||
with self.subTest(input_arr=input_arr):
|
||
result = insertion_sort_decreasing_inplace(input_arr)
|
||
self.assertEqual(result, expected)
|
||
self.assertEqual(input_arr, expected) # Original should be modified
|
||
|
||
def test_empty_array(self):
|
||
"""Test empty array."""
|
||
arr = []
|
||
result = insertion_sort_decreasing_inplace(arr)
|
||
self.assertEqual(result, [])
|
||
self.assertEqual(arr, [])
|
||
|
||
def test_single_element(self):
|
||
"""Test arrays with single element."""
|
||
arr = [42]
|
||
result = insertion_sort_decreasing_inplace(arr)
|
||
self.assertEqual(result, [42])
|
||
self.assertEqual(arr, [42])
|
||
|
||
def test_original_array_modified(self):
|
||
"""Test that original array is modified."""
|
||
original = [5, 2, 8, 1, 9, 3]
|
||
result = insertion_sort_decreasing_inplace(original)
|
||
|
||
self.assertEqual(original, result)
|
||
self.assertEqual(original, [9, 8, 5, 3, 2, 1])
|
||
|
||
|
||
class TestPerformance(unittest.TestCase):
|
||
"""Performance and stress tests."""
|
||
|
||
def test_performance_small_arrays(self):
|
||
"""Test performance with small arrays."""
|
||
sizes = [10, 50, 100]
|
||
|
||
for size in sizes:
|
||
with self.subTest(size=size):
|
||
arr = list(range(size))
|
||
random.shuffle(arr)
|
||
|
||
start_time = time.time()
|
||
result = insertion_sort_decreasing(arr)
|
||
end_time = time.time()
|
||
|
||
# Verify correctness
|
||
expected = list(range(size - 1, -1, -1))
|
||
self.assertEqual(result, expected)
|
||
|
||
# Performance should be reasonable for small arrays
|
||
execution_time = end_time - start_time
|
||
self.assertLess(execution_time, 1.0) # Should complete within 1 second
|
||
|
||
def test_worst_case_performance(self):
|
||
"""Test performance with worst-case input (ascending order)."""
|
||
sizes = [10, 50, 100]
|
||
|
||
for size in sizes:
|
||
with self.subTest(size=size):
|
||
arr = list(range(size)) # Already sorted ascending (worst case)
|
||
|
||
start_time = time.time()
|
||
result = insertion_sort_decreasing(arr)
|
||
end_time = time.time()
|
||
|
||
# Verify correctness
|
||
expected = list(range(size - 1, -1, -1))
|
||
self.assertEqual(result, expected)
|
||
|
||
execution_time = end_time - start_time
|
||
self.assertLess(execution_time, 1.0)
|
||
|
||
def test_best_case_performance(self):
|
||
"""Test performance with best-case input (descending order)."""
|
||
sizes = [10, 50, 100]
|
||
|
||
for size in sizes:
|
||
with self.subTest(size=size):
|
||
arr = list(range(size - 1, -1, -1)) # Already sorted descending
|
||
|
||
start_time = time.time()
|
||
result = insertion_sort_decreasing(arr)
|
||
end_time = time.time()
|
||
|
||
# Verify correctness
|
||
expected = list(range(size - 1, -1, -1))
|
||
self.assertEqual(result, expected)
|
||
|
||
execution_time = end_time - start_time
|
||
self.assertLess(execution_time, 1.0)
|
||
|
||
|
||
class TestEdgeCases(unittest.TestCase):
|
||
"""Edge cases and boundary conditions."""
|
||
|
||
def test_very_large_numbers(self):
|
||
"""Test with very large numbers."""
|
||
arr = [sys.maxsize, sys.maxsize - 1, sys.maxsize - 2]
|
||
result = insertion_sort_decreasing(arr)
|
||
expected = [sys.maxsize, sys.maxsize - 1, sys.maxsize - 2]
|
||
self.assertEqual(result, expected)
|
||
|
||
def test_very_small_numbers(self):
|
||
"""Test with very small numbers."""
|
||
arr = [-sys.maxsize, -sys.maxsize + 1, -sys.maxsize + 2]
|
||
result = insertion_sort_decreasing(arr)
|
||
expected = [-sys.maxsize + 2, -sys.maxsize + 1, -sys.maxsize]
|
||
self.assertEqual(result, expected)
|
||
|
||
def test_mixed_types_comparable(self):
|
||
"""Test with mixed types that are comparable."""
|
||
# Note: This will work with Python's comparison rules
|
||
arr = [1, 1.5, 2, 2.5]
|
||
result = insertion_sort_decreasing(arr)
|
||
expected = [2.5, 2, 1.5, 1]
|
||
self.assertEqual(result, expected)
|
||
|
||
def test_random_large_array(self):
|
||
"""Test with a larger random array."""
|
||
random.seed(42) # For reproducible tests
|
||
arr = [random.randint(-1000, 1000) for _ in range(100)]
|
||
result = insertion_sort_decreasing(arr)
|
||
|
||
# Verify it's sorted in decreasing order
|
||
for i in range(len(result) - 1):
|
||
self.assertGreaterEqual(result[i], result[i + 1])
|
||
|
||
|
||
class TestNegativeCases(unittest.TestCase):
|
||
"""Negative test cases - testing invalid inputs and error conditions."""
|
||
|
||
def test_none_input(self):
|
||
"""Test that None input raises appropriate error."""
|
||
with self.assertRaises((TypeError, AttributeError)):
|
||
insertion_sort_decreasing(None)
|
||
|
||
with self.assertRaises((TypeError, AttributeError)):
|
||
insertion_sort_decreasing_inplace(None)
|
||
|
||
def test_non_list_input(self):
|
||
"""Test that non-list inputs behave unexpectedly or raise errors."""
|
||
# Test inputs that should raise errors
|
||
error_inputs = [
|
||
"string", # String doesn't support item assignment
|
||
123, # Int doesn't support indexing
|
||
45.67, # Float doesn't support indexing
|
||
]
|
||
|
||
for invalid_input in error_inputs:
|
||
with self.subTest(input_type=type(invalid_input).__name__, input_value=invalid_input):
|
||
with self.assertRaises((TypeError, AttributeError)):
|
||
insertion_sort_decreasing(invalid_input)
|
||
|
||
with self.assertRaises((TypeError, AttributeError)):
|
||
insertion_sort_decreasing_inplace(invalid_input)
|
||
|
||
# Test inputs that might work but shouldn't be used
|
||
problematic_inputs = [
|
||
{"key": "value"}, # Dict - might work but unpredictable
|
||
(1, 2, 3), # Tuple - immutable, will cause errors on modification
|
||
set([1, 2, 3]), # Set - unordered, unpredictable
|
||
]
|
||
|
||
for invalid_input in problematic_inputs:
|
||
with self.subTest(input_type=type(invalid_input).__name__, input_value=invalid_input):
|
||
# These might not raise errors immediately but are problematic
|
||
try:
|
||
result = insertion_sort_decreasing(invalid_input)
|
||
# If it doesn't raise an error, verify it's problematic
|
||
self.assertIsInstance(result, type(invalid_input))
|
||
except (TypeError, AttributeError):
|
||
# Expected for some types
|
||
pass
|
||
|
||
def test_non_comparable_elements(self):
|
||
"""Test arrays with non-comparable elements."""
|
||
# Mixed types that can't be compared
|
||
non_comparable_arrays = [
|
||
[1, "string", 3],
|
||
[1, [2, 3], 4],
|
||
[1, {"key": "value"}, 3],
|
||
[1, None, 3],
|
||
]
|
||
|
||
for arr in non_comparable_arrays:
|
||
with self.subTest(array=arr):
|
||
with self.assertRaises(TypeError):
|
||
insertion_sort_decreasing(arr)
|
||
|
||
with self.assertRaises(TypeError):
|
||
insertion_sort_decreasing_inplace(arr)
|
||
|
||
def test_nested_lists(self):
|
||
"""Test arrays with nested lists (should work with lexicographic comparison)."""
|
||
nested_arrays = [
|
||
[[1, 2], [3, 4]],
|
||
[[1], [2], [3]],
|
||
[[1, 2, 3], [4, 5, 6]],
|
||
]
|
||
|
||
for arr in nested_arrays:
|
||
with self.subTest(array=arr):
|
||
result = insertion_sort_decreasing(arr)
|
||
# Verify it's sorted correctly (lexicographically)
|
||
for i in range(len(result) - 1):
|
||
self.assertGreaterEqual(result[i], result[i + 1])
|
||
|
||
# Test in-place version
|
||
arr_copy = arr.copy()
|
||
insertion_sort_decreasing_inplace(arr_copy)
|
||
self.assertEqual(arr_copy, result)
|
||
|
||
def test_objects_without_comparison(self):
|
||
"""Test arrays with objects that don't support comparison."""
|
||
class NonComparable:
|
||
def __init__(self, value):
|
||
self.value = value
|
||
|
||
obj1 = NonComparable(1)
|
||
obj2 = NonComparable(2)
|
||
|
||
with self.assertRaises(TypeError):
|
||
insertion_sort_decreasing([obj1, obj2])
|
||
|
||
with self.assertRaises(TypeError):
|
||
insertion_sort_decreasing_inplace([obj1, obj2])
|
||
|
||
def test_custom_objects_with_comparison(self):
|
||
"""Test arrays with custom objects that do support comparison."""
|
||
class Comparable:
|
||
def __init__(self, value):
|
||
self.value = value
|
||
|
||
def __lt__(self, other):
|
||
return self.value < other.value
|
||
|
||
def __gt__(self, other):
|
||
return self.value > other.value
|
||
|
||
def __eq__(self, other):
|
||
return self.value == other.value
|
||
|
||
obj1 = Comparable(5)
|
||
obj2 = Comparable(2)
|
||
obj3 = Comparable(8)
|
||
|
||
# This should work since the objects support comparison
|
||
result = insertion_sort_decreasing([obj1, obj2, obj3])
|
||
self.assertEqual([obj.value for obj in result], [8, 5, 2])
|
||
|
||
def test_very_large_arrays(self):
|
||
"""Test with very large arrays (should still work but may be slow)."""
|
||
# Test with a moderately large array
|
||
large_array = list(range(1000))
|
||
random.shuffle(large_array)
|
||
|
||
# This should work but might be slow
|
||
result = insertion_sort_decreasing(large_array)
|
||
expected = list(range(999, -1, -1))
|
||
self.assertEqual(result, expected)
|
||
|
||
def test_infinity_values(self):
|
||
"""Test arrays containing infinity values."""
|
||
import math
|
||
|
||
inf_arrays = [
|
||
[1, float('inf'), 3],
|
||
[1, float('-inf'), 3],
|
||
[float('inf'), float('-inf'), 0],
|
||
]
|
||
|
||
for arr in inf_arrays:
|
||
with self.subTest(array=arr):
|
||
result = insertion_sort_decreasing(arr)
|
||
# Verify it's sorted correctly
|
||
for i in range(len(result) - 1):
|
||
self.assertGreaterEqual(result[i], result[i + 1])
|
||
|
||
def test_nan_values(self):
|
||
"""Test arrays containing NaN values (NaN comparisons are unpredictable)."""
|
||
import math
|
||
|
||
nan_arrays = [
|
||
[1, float('nan'), 3],
|
||
[float('nan'), 1, 3],
|
||
[1, 3, float('nan')],
|
||
]
|
||
|
||
for arr in nan_arrays:
|
||
with self.subTest(array=arr):
|
||
# NaN comparisons don't raise errors but produce unpredictable results
|
||
# We just verify the function doesn't crash
|
||
result = insertion_sort_decreasing(arr)
|
||
self.assertEqual(len(result), len(arr))
|
||
|
||
# Test in-place version
|
||
arr_copy = arr.copy()
|
||
insertion_sort_decreasing_inplace(arr_copy)
|
||
self.assertEqual(len(arr_copy), len(arr))
|
||
|
||
def test_mixed_numeric_types(self):
|
||
"""Test arrays with mixed numeric types (should work)."""
|
||
mixed_arrays = [
|
||
[1, 2.5, 3],
|
||
[1.0, 2, 3.14],
|
||
[1, 2.0, 3],
|
||
]
|
||
|
||
for arr in mixed_arrays:
|
||
with self.subTest(array=arr):
|
||
result = insertion_sort_decreasing(arr)
|
||
# Verify it's sorted correctly
|
||
for i in range(len(result) - 1):
|
||
self.assertGreaterEqual(result[i], result[i + 1])
|
||
|
||
def test_empty_strings_and_numbers(self):
|
||
"""Test arrays with empty strings and numbers."""
|
||
mixed_arrays = [
|
||
[1, "", 3],
|
||
["", 1, 3],
|
||
[1, 3, ""],
|
||
]
|
||
|
||
for arr in mixed_arrays:
|
||
with self.subTest(array=arr):
|
||
with self.assertRaises(TypeError):
|
||
insertion_sort_decreasing(arr)
|
||
|
||
with self.assertRaises(TypeError):
|
||
insertion_sort_decreasing_inplace(arr)
|
||
|
||
def test_boolean_values(self):
|
||
"""Test arrays with boolean values (should work)."""
|
||
bool_arrays = [
|
||
[True, False, True],
|
||
[False, True, False],
|
||
[True, True, False],
|
||
]
|
||
|
||
for arr in bool_arrays:
|
||
with self.subTest(array=arr):
|
||
result = insertion_sort_decreasing(arr)
|
||
# Verify it's sorted correctly (True > False)
|
||
for i in range(len(result) - 1):
|
||
self.assertGreaterEqual(result[i], result[i + 1])
|
||
|
||
def test_very_deep_recursion_simulation(self):
|
||
"""Test with arrays that might cause issues in very deep recursion."""
|
||
# Create an array that's already sorted in descending order
|
||
# This should be the best case for insertion sort
|
||
descending_array = list(range(100, 0, -1))
|
||
|
||
result = insertion_sort_decreasing(descending_array)
|
||
expected = list(range(100, 0, -1))
|
||
self.assertEqual(result, expected)
|
||
|
||
def test_unicode_strings(self):
|
||
"""Test arrays with unicode strings."""
|
||
unicode_arrays = [
|
||
["hello", "world", "test"],
|
||
["α", "β", "γ"],
|
||
["🚀", "🌟", "⭐"],
|
||
]
|
||
|
||
for arr in unicode_arrays:
|
||
with self.subTest(array=arr):
|
||
result = insertion_sort_decreasing(arr)
|
||
# Verify it's sorted correctly (lexicographically)
|
||
for i in range(len(result) - 1):
|
||
self.assertGreaterEqual(result[i], result[i + 1])
|
||
|
||
|
||
class TestHelperFunctions(unittest.TestCase):
|
||
"""Test helper functions if any."""
|
||
|
||
def test_print_array_function(self):
|
||
"""Test the print_array helper function."""
|
||
# This is more of a smoke test since print_array doesn't return anything
|
||
from insertion_sort_decreasing import print_array
|
||
|
||
# Should not raise any exceptions
|
||
print_array([1, 2, 3], "Test Array")
|
||
print_array([], "Empty Array")
|
||
|
||
def test_print_array_with_invalid_input(self):
|
||
"""Test print_array with invalid input."""
|
||
from insertion_sort_decreasing import print_array
|
||
|
||
# Test with None - should handle gracefully or raise error
|
||
try:
|
||
print_array(None, "None Array")
|
||
except (TypeError, AttributeError):
|
||
pass # Expected behavior
|
||
|
||
# Test with non-list input - should handle gracefully or raise error
|
||
try:
|
||
print_array("not a list", "String Array")
|
||
except (TypeError, AttributeError):
|
||
pass # Expected behavior
|
||
|
||
|
||
def run_performance_benchmark():
|
||
"""Run a performance benchmark comparing different scenarios."""
|
||
print("\n" + "="*60)
|
||
print("PERFORMANCE BENCHMARK")
|
||
print("="*60)
|
||
|
||
scenarios = [
|
||
("Random Array", lambda n: [random.randint(1, 1000) for _ in range(n)]),
|
||
("Ascending Order", lambda n: list(range(n))),
|
||
("Descending Order", lambda n: list(range(n-1, -1, -1))),
|
||
("All Same", lambda n: [42] * n),
|
||
]
|
||
|
||
sizes = [10, 50, 100, 500]
|
||
|
||
for scenario_name, generator in scenarios:
|
||
print(f"\n{scenario_name}:")
|
||
print("-" * 40)
|
||
|
||
for size in sizes:
|
||
arr = generator(size)
|
||
|
||
# Test non-inplace version
|
||
start_time = time.time()
|
||
result1 = insertion_sort_decreasing(arr)
|
||
time1 = time.time() - start_time
|
||
|
||
# Test inplace version
|
||
arr_copy = arr.copy()
|
||
start_time = time.time()
|
||
result2 = insertion_sort_decreasing_inplace(arr_copy)
|
||
time2 = time.time() - start_time
|
||
|
||
print(f"Size {size:3d}: Non-inplace: {time1:.6f}s, In-place: {time2:.6f}s")
|
||
|
||
|
||
def run_stress_test():
|
||
"""Run stress tests with various edge cases."""
|
||
print("\n" + "="*60)
|
||
print("STRESS TEST")
|
||
print("="*60)
|
||
|
||
stress_cases = [
|
||
("Empty array", []),
|
||
("Single element", [42]),
|
||
("Two elements", [2, 1]),
|
||
("All zeros", [0, 0, 0, 0]),
|
||
("Negative numbers", [-5, -2, -8, -1]),
|
||
("Mixed positive/negative", [5, -2, 8, -1, 0]),
|
||
("Large numbers", [1000000, 999999, 1000001]),
|
||
("Duplicate elements", [3, 3, 1, 1, 2, 2]),
|
||
]
|
||
|
||
for case_name, test_arr in stress_cases:
|
||
print(f"\n{case_name}: {test_arr}")
|
||
|
||
# Test both functions
|
||
result1 = insertion_sort_decreasing(test_arr)
|
||
test_arr_copy = test_arr.copy()
|
||
result2 = insertion_sort_decreasing_inplace(test_arr_copy)
|
||
|
||
# Verify results are identical
|
||
assert result1 == result2, f"Results differ for {case_name}"
|
||
|
||
# Verify sorting is correct
|
||
for i in range(len(result1) - 1):
|
||
assert result1[i] >= result1[i + 1], f"Not sorted correctly at index {i}"
|
||
|
||
print(f"✓ Passed: {result1}")
|
||
|
||
|
||
if __name__ == "__main__":
|
||
# Set random seed for reproducible tests
|
||
random.seed(42)
|
||
|
||
print("Insertion Sort - Decreasing Order Test Suite")
|
||
print("=" * 60)
|
||
|
||
# Run unit tests
|
||
print("\nRunning Unit Tests...")
|
||
unittest.main(argv=[''], exit=False, verbosity=2)
|
||
|
||
# Run performance benchmark
|
||
run_performance_benchmark()
|
||
|
||
# Run stress tests
|
||
run_stress_test()
|
||
|
||
print("\n" + "="*60)
|
||
print("All tests completed!")
|
||
print("="*60)
|