Merge insertion sort doesn't work

[remram44]

>>> merge_insertion_sort([0, 1, 2, 3, 4])
[0, 2, 1, 3, 4]

Cc @ulwlu #2211 sorts/merge_insertion_sort.py

[remram44]

In general I suggest you test all your sort algorithms on all permutations of range(0, 5). That's only 120 permutations.

[cclauss]

This sounds like a great idea. There are test that all Euler solutions have to pass and you could create something similar for the sort algorithms.

[AilisOsswald]

Hello, I'd like to take up this Issue with a fellow student of mine. (@yellowsto)
We would like to take a look at Merge Insertion Sort to fix it and write Test Cases for at least that Sort, as suggested above.

We are both new to Open Source, but happy to learn! (so far we've read your contribution guidelines and some short tutorials how to work with github)

Could we get this Issue assigned?

[Rohanrbharadwaj]

@AilisOsswald Issues aren't really assigned here, anybody can work on them. You just have to open a PR with the changes that you plan to make. The maintainers will review it and merge it if it looks good :)

[AilisOsswald]

Hey, we have wrote script which should make testing sort algorithms easier.
It generates a txt file for doctesting a certain sort algorithm for all permutations in range(0,5).
If called the script lets the user input the name of the sort to be tested and then generates a fitting txt (which should be deleted after use).

Does this seem like a good idea? If yes, we could make a PR, but we wanted to check first.
I have added the file make_sort_tests.txt (since we don't want to put it into our current pull request)

If someone wants to try:

• insert the file into your sorts folder
• download the file and convert it into .txt (just changing the ending of the file should do it)
• run it with "python3 make_sort_tests.py"
• run the test with "python3 -m doctest -v test_sort.txt"

We'd be happy about Feedback!

[cclauss]

Why do you not want to put a text file in your pull request?

[AilisOsswald]

We thought one PR for one thing - and the PR we have know is for fixing the merge_insertion sort.
As far as we tried out, if we commit to our own fork, which is in the PR all our new commits automatically get into that old PR - and not inte a new one/ none at all.

[cclauss]

I wonder why we are creating a txt file containing the permutations instead of doing #5774 (comment)

[AilisOsswald]

Because we did not get to figure out how to put a for loop into the doctests - Since the syntac in a doctest works like

algorithm_to_be_tested(input)
expected_output

Now if i create all permutations anwant to run them what comes to my mind is:

for i in range(len(permutations)):
if algorithm_to_be_tested(input) != expected_output
print("found error")

I wouldn't know how to convert this into a fitting docstring test, since my for still needs to run and all wouldn_t it be somewhat like this?

for i in range(len(permutations)):
... algorithm_to_be_tested
expected_output

But this does not seem to work for us - that's why we did the file

[AilisOsswald]

for clarification also, the txt file we have attached here is actually an .py file - but github does not support py files in comments

[remram44]

Why does this have to be in doctests?

[Rohanrbharadwaj]

@AilisOsswald Why not create a one-line list comprehension and check if all results are what we want?

[AilisOsswald]

@remram44 I thought doctests were the standard for testing here

Ohh, a one line seems like a good idea!

so far I have tried:
>>> [None if merge_insertion_sort(x)==[0,1,2,3,4] else print(x,"sorted to",merge_insertion_sort(x)) for x in permutations]

But this gives back a 120 long list of None's - which isn't really what i looked for
optimally I'd like to get nothing back from that one line statement if there is no error.
I've tried it with pass and continue but it does not work, any ideas?

BTW Thanks for all the Feedback, everyone!

[Rohanrbharadwaj]

I was thinking:

>>> results = [True for x in permutations if merge_insertion_sort(x) == [0,1,2,3,4]]
>>> len(results) == 120  # Do all 120 pass?
True

[remram44]

>>> all(merge_insertion_sort(x) == [0, 1, 2, 3, 4] for x in permutations)
True

[AilisOsswald]

Certainly should work, but we wouldn't see for which permutation it wouldn't work?
That would be helpful if we'd try to find out why

[Rohanrbharadwaj]

>>> [x for x in permutations if merge_insertion_sort(x) != [0, 1, 2, 3, 4]]
[]  # Ideally should be an empty list, otherwise it will have the permutations that don't work

(Latest edit)

[AilisOsswald]

Yes!

bad_ones = [x for x in permutations if merge_insertion_sort(x) != [0, 1, 2, 3, 4]]
[]

should work perfectly, I think we don't even need the print, because if it works, the list is empty and we should get no feedback. but if it doesn't work we will get the "expected [] but got [(where_it_did_not_work)]" and will see the permutations that failed anyways

[cclauss]

>>> all(a == e for a, e in zip(actual, expected))
True