8000 Centralized tests for sorting algorithms by slarse · Pull Request #723 · TheAlgorithms/Python · GitHub
[go: up one dir, main page]
Skip to content

Centralized tests for sorting algorithms #723

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Closed
slarse wants to merge 22 commits into from
Closed

Centralized tests for sorting algorithms #723

slarse wants to merge 22 commits into from

Conversation

@slarse
Copy link
@slarse slarse commented Feb 27, 2019 •
edited
Loading

@poyea We bit off a bit more than we could chew, but we managed to finish parts of the unified test suite. I will try to bring it in bite-sized chunks, starting with this, if there is interest from your part. Our whole set of changes was a whopping 3800+/1400- lines.

This PR builds on #714, and the comments there are still applicable here. Additionally, this PR adds:

Tests

  • The import tests (just testing to import every module) have been removed to focus on the sorting part only (939c299)
  • Generic tests for out-of-place sorting algorithms (7edc521)
    • These tests are parameterized by function name. Any sorting function that just takes a collection can be added to the test suite bu adding it to the SORTS list.
  • Generic tests for in-place sorting algorithms (e4f9103)
    • Same case as above, in-place sorting algorithms can be tested by adding them to the SORTS list.
  • Tests for bogosort (e5c68a8)
    • Since bogosort is non-deterministic, running it on large lists is... inadvisable.

Bugfixes

  • Fix for bucket_sort crash on empty input (bd61f06)
  • Fix for timsort crash empty input (a9f9069)
  • FIx for merge_sort_fastest destroying the input list (2e382d0)
    • On a side note, this merge sort is O(n^2), not O(n) as it claims, because of the removals from the original list.
  • Fix for a rare edge case in comb_sort (1b7a82d)
  • Fix for tree_sort discarding duplicate elements (b46d67a)
  • Some minor fixes in files to make them importable from the root of the project

Broken algorithms

  • timsort
    • There are some edge-cases where timsort fails to sort properly, We don't know why.
  • radix_sort
    • Fails most tests, it appears that it cannot handle negative numbers (at the very least, may be more problems).

Notes

slarse and others added 22 commits February 22, 2019 21:15
@slarse
Move files and folders into unified package structure
529dc79
@mnil2 @slarse
Add import test
5fb67c2
@slarse
Add minimal setup.py
ebbb816
@slarse
Update .travis.yml
cac923d
@larshum @slarse
Fix undefined name
e7d121b
@slarse
Merge branch 'master' into package_project_pr
5810355
@slarse
Revert to initial directory structure
518045a
@slarse
Add scripts for running tests with coverage
6b97f3c
@slarse
Update .travis.yml
885f651
@mnil2 @slarse
Make modules in sorts importable (#32)
1aaf79d
@slarse
Add conftest to sorts tests
3c76239
@slarse
Add test cases for out-of-place sorting algorithms
7edc521
@slarse
Fix bucket sort crash on empty input
bd61f06
@slarse
Fix merge_sort_fastest mutating input
2e382d0
@slarse
Fix tree sort not handling duplicate elements
b46d67a
@slarse
Fix timsort not handling empty input
a9f9069
@slarse
Add generic tests for in-place sorting algorithms
e4f9103
@slarse
Add tests for bogosort
e5c68a8
@slarse
Fix edge case in comb_sort
1b7a82d
@slarse
Merge branch 'master' into sorts_test_pr_merge
60cbc82
@slarse
Fix import tests traversing non-packaged directories
2961e98
@slarse
Remove import tests
939c299
@slarse slarse closed this Apr 30, 2019
@slarse slarse mentioned this pull request Nov 18, 2019
Closed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

3 participants

@slarse @mnil2 @larshum
0