* fix: restrict introsort heap fallback to the active range
* test: cover introsort heap fallback range boundaries
* fix: sort introsort heap fallback ranges without copying
* test: cover introsort heap sort range boundaries and default end
* fix(sorts): make smoothsort generic over Comparable items
* The TypeVar is no longer needed.
---------
Co-authored-by: Christian Clauss <cclauss@me.com>
* types(reverse_selection): constrain items to Comparable
Bind reverse_selection_sort's element type to a Comparable Protocol so the
signature says "a list of items that can be compared with each other"
instead of a bare list, and keep the element type in the return.
reverse_subarray only swaps elements and never compares them, so its
TypeVar stays unbounded.
Also adds doctests for a comparable non-int type (strings, floats) and for
the failure mode: mixing non-comparable items must raise TypeError rather
than silently mis-sort. The test battery picks the sort up for the shared
cases and for the rejection check.
* updating DIRECTORY.md
---------
Co-authored-by: AuroraAeon <auroraeon@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.com>
Co-authored-by: cclauss <cclauss@users.noreply.github.com>
* Make bitonic sort support comparable items
* Add comparable item tests for bitonic sort
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.com>
Bind merge and iter_merge_sort's element type to a Comparable Protocol so
the signatures say "a list of items that can be compared with each other"
instead of a bare list, and keep the element type in the return. result is
annotated list[T] so the generic survives the local binding.
iter_merge_sort was already in the shared SORTS battery but was missing from
test_sort_rejects_non_comparable_items, so its checklist box was only half
done; this completes it.
Also adds a doctest for the failure mode: mixing non-comparable items must
raise TypeError rather than silently mis-sort. The 'cba' doctest becomes
list('cba') so it matches the list[T] signature now on the function -- the
runtime behaviour is unchanged, since iter_merge_sort copies its input with
list() either way.
Co-authored-by: AuroraAeon <auroraeon@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.com>
Part of #15234
- Replace list[Any] with a Comparable-bounded TypeVar so
odd_even_transposition sorts any mutually comparable items,
not just ints
- Add str/float/int success doctests plus a TypeError rejection
doctest for non-comparable mixed input
- Assert in-place behavior via `result is values` doctest
- Register the sort in the shared battery and in
test_sort_rejects_non_comparable_items
Co-authored-by: ayushman-it <253447966+ayushman-it@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.com>
* feat(sorts): make reversort generic over comparable items
Part of #15234
- Replace list[Any] with a Comparable-bounded TypeVar so reversort and
reversort_cost sort any mutually comparable items, not just ints
- Add TypeError doctests confirming mixed non-comparable input raises
- Register reversort in the shared test battery covering str/float/
dataclass/NamedTuple cases and the non-comparable rejection path
* style(sorts): use PEP 695 type parameters per repo convention
ruff UP047 requires the sanctioned [T: Comparable] signature form used
by the reference insertion_sort.py. Keep the module-level TypeVar as in
the reference.
* Apply batched suggestions from code review
Co-authored-by: Christian Clauss <cclauss@me.com>
---------
Co-authored-by: Christian Clauss <cclauss@me.com>
* sorts: make bogo_sort generic for comparable items
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update tests/test_sorts.py
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.com>
* sorts: make recursive_insertion_sort generic over Comparable items
Part of #15234
- switch rec_insertion_sort/insert_next to the Comparable/TypeVar-bound
MutableSequence[T] pattern (in-place sorts bucket) per the convention
discussed on #15234
- make rec_insertion_sort return the sorted collection and give n a
default of len(collection), so it can be called with a single
argument like the other sorts in the shared test battery
- add a string doctest
- register rec_insertion_sort in tests/test_sorts.py's shared SORTS
battery and the non-comparable-items rejection test
* fix: keep rec_insertion_sort in-place with None return, per maintainer review
- Revert n to a required parameter and drop the MutableSequence[T] return
value; rec_insertion_sort stays a pure in-place sort returning None, as
requested in review.
- Keep the Comparable/TypeVar generalization (no PEP 695 syntax, to match
the existing TypeVar style in the file).
- Keep the non-int (string) doctest.
- tests/test_sorts.py: rec_insertion_sort no longer fits the shared SORTS
battery (which asserts on a returned value), so it's removed from that
tuple and given its own parametrized in-place test, plus its own
non-comparable-items rejection test.
* test: adjust test_sorts.py for rec_insertion_sort's None-returning in-place contract
rec_insertion_sort no longer fits the shared SORTS battery (which asserts
on a returned value), so it's removed from that tuple and given its own
parametrized in-place test (checked against sorted()) plus its own
non-comparable-items rejection test.
* Apply batched suggestions from code review
Co-authored-by: Christian Clauss <cclauss@me.com>
---------
Co-authored-by: Christian Clauss <cclauss@me.com>
* sorts: make odd_even_sort generic over any comparable type (Part of #15234)
Adds a Comparable-bound TypeVar (matching the pattern used in insertion_sort.py), doctests covering strings, floats, and the non-comparable TypeError case, and registers odd_even_sort in the shared test_sort_rejects_non_comparable_items test.
Part of #15234
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Drop redundant module-level TypeVar, bind Comparable to __gt__
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Fix import block formatting per ruff
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.com>
Part of #15234
- switch pancake_sort's TypeVar to the Comparable/TypeVar-bound
pattern used by insertion_sort.py
- add doctests covering strings, floats, and random data
- register pancake_sort in tests/test_sorts.py's shared battery and
the non-comparable-items rejection test
Co-authored-by: Christian Clauss <cclauss@me.com>
* sorts: support comparable items in circle_sort
* style: format circle_sort
* Apply batched suggestions from code review
Co-authored-by: Christian Clauss <cclauss@me.com>
---------
Co-authored-by: Christian Clauss <cclauss@me.com>
* sorts: type bubble sort for any comparable items
Bound bubble_sort_iterative and bubble_sort_recursive to a Comparable protocol instead of Any, add TypeError doctests, and cover the mixed-type failure in tests/test_sorts.py.
Refs #15234
* Update tests/test_sorts.py
* Add binary insertion sort to tests and rename function
Updated tests to include binary insertion sort and renamed test function.
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
---------
Co-authored-by: Harsh Raj Singhania <harshrajsinghania@proton.me>
Co-authored-by: Christian Clauss <cclauss@me.com>
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
* Improve binary insertion sort comparable typing
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Update binary_insertion_sort function signature
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.com>
* Add pytest for heap_sort
* [pre-commit.ci] auto fixes from pre-commit.com hooks
for more information, see https://pre-commit.ci
* Add __init__.py to tests to fix Ruff namespace package error
---------
Co-authored-by: pre-commit-ci[bot] <66853113+pre-commit-ci[bot]@users.noreply.github.com>
Co-authored-by: Christian Clauss <cclauss@me.com>
Milad Khoshdel