Skip to content
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.

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

sort: TestAdversary is broken #21581

Closed
tom93 opened this issue Aug 24, 2017 · 1 comment
Closed

sort: TestAdversary is broken #21581

tom93 opened this issue Aug 24, 2017 · 1 comment

Comments

@tom93
Copy link
Contributor

@tom93 tom93 commented Aug 24, 2017

There are some major problems with TestAdversary (based on A Killer Adversary for Quicksort by M. D. McIlroy).

  1. The data field is modified by Swap() but ignored by Less(), so swapping has no effect.

  2. Less() compares elements using >=, which is messed up.

  3. The test never checks anything, so it will always pass. It should count the number of comparisons and fail if there are too many.

  4. The size 100 is too small to distinguish between O(n^2) with a small constant factor and O(n*log(n)).

  5. (nitpicking) map[int]int can be replaced with []int, which is much more efficient.

@gopherbot
Copy link

@gopherbot gopherbot commented Aug 24, 2017

Change https://golang.org/cl/58330 mentions this issue: sort: fix TestAdversary

@gopherbot gopherbot closed this in 3723d08 Aug 25, 2017
@golang golang locked and limited conversation to collaborators Aug 25, 2018
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
2 participants
You can’t perform that action at this time.