Reputation
646
Top tag
Next privilege 1,000 Rep.
See votes, expandable usercard
Badges
1 5 17
Impact
~41k people reached

Jan
11
accepted Intersection of geometric entities
Jan
11
accepted Optimal fixed-size sequential sorting algorithms
Jan
1
revised Efficient algorithm to merge n successive sorted arrays in place
Note about size.
Dec
31
revised Efficient algorithm to merge n successive sorted arrays in place
Add C++ code for the current solution.
Dec
31
revised Efficient algorithm to merge n successive sorted arrays in place
Add current solution.
Dec
31
revised Efficient algorithm to merge n successive sorted arrays in place
Add more detailed explanation.
Dec
31
comment Efficient algorithm to merge n successive sorted arrays in place
It looks like a case of confusion: it seems that they thought that I was trying to merge n sorted arrays into another big array while those « n arrays » are already a single big array that's only waiting for a big in-place merge operation.
Dec
30
asked Efficient algorithm to merge n successive sorted arrays in place
Oct
5
comment Optimal fixed-size sequential sorting algorithms
Oh, and I almost forgot, but amongst what I was trying to achieve, I wanted an « optimal » sort to have an optimal number of assignments, whatever the input. While the number of comparisons will depend on how we look at the input, I believe that there is an optimal number of assignments for every input, no matter how we analyze it.
Oct
5
comment Optimal fixed-size sequential sorting algorithms
@rwong I delibrately chose to ignore the hardware problem for the question (hence the no parallel stuff) knowing that it makes basically everything harder to reason about :)
Oct
5
comment Optimal fixed-size sequential sorting algorithms
@rwong Yeah, I know about partially sorted data, I've recently designed a sorting algorithms along the lines of TimSort specially for those :p My point about optimal sorting networks wasn't that optimal sorting networks didn't exist but that they do not produce optimal sorting algorithms: the three values sort that I have provided for example always does less work than an optimal sorting network of size 3.
Oct
5
comment Optimal fixed-size sequential sorting algorithms
Well, I get your point. I guess that I was going for the kind of « optimal » which gets the least work done, like checking first if the collection is sorted, and don't move anything if it is. But my premises seem to be wrong then (and my English is becoming brittle...). And you're right about equality cases. I totally failed to take those into account.
Oct
5
asked Optimal fixed-size sequential sorting algorithms
Jun
20
awarded  Popular Question
May
29
awarded  Citizen Patrol
May
28
reviewed Reviewed const reference and const pointer. How do they work?
May
27
comment Why can't there be any implicit conversions?
The Zen of Python, second principle: Explicit is better than implicit.
May
6
comment Intersection of geometric entities
If I understand correctly, the problem with your solution is that it only works when the result of the intersection is a set a points. However, an intersection between two lines can return a point, a line or nothing. Bottom line: the result can be a set of widely different shapes, so an array of one type can't do it :/
May
6
comment Intersection of geometric entities
Exceptions are brutally slow except when not called. In one of the examples, I returned the most case and threw the "exceptional" ones which are statistically brutally uncommon, so the speed should not have been a problem. I wouldn't choose the exceptions for other reasons, though :)
May
6
revised Intersection of geometric entities
Time machine note.