@EvilJS Very nice! Took me a second to recognize the people shapes as such, though. Maybe give heads and bodies a same-colored contour?

@Raphael That is a good idea.

But the graph-like text is not even close to readable on smaller space.

If you think the graphic needs text, you do not have to make it much smaller. Give it a light color and but it over the bodies at 90% width?

Hello, is there anybody familliar with sorting and median-about algorithms?

@Kropekk Hi! Sorting, yes; I don't know what "median-about" means.

Given a set of numbers (set implicates no duplicates), find k elements which are closest to the median of S. 1<=k<=|S|

i need it to work with O(|S|) time

i thought about finding median (O(|S|)), lets say it has index "i", finding element which would have index "i-k" in sorted array, finding "i+k" element and sort these two arrays and then finding appropiate elements with algormithm like "merge" in mergeSort

but it's clearly not O(|S|) for big k as i need to sort arrays

@Raphael any ideas?

@Kropekk That gives you the $k$ "closest" elements in terms of the positions in the original array, if your set is given as an array. Given that sets are usually given without implies order, I think the task is to find the $k$ elements that are closest to the median in terms of value.

@Raphael Yes, i do that - with algorithm like "merge" in mergeSort - looking through array of k smaller elements and array of k bigger elements

I see an $\Theta(|S| + k \log k)$ time algorithm.

That's probably close enough to linear running time for practical purposes. I take it this is a homework task then?

yes, it is. and i'm stuck with it

No "k" in time-complexity is impossible to aquire in my opinion...

@Raphael could you share your idea?

@Kropekk Quite true; but terms in $O(k)$ are dominated by $O(|S|)$ so that would be okay.

yes, by O(k log k) may be more than O(|S|) - that's why i thought about my approach as wrong

@Kropekk Probably what you have in mind, modulo formulation. Find elements of rank $n/2 - k$ and $n/2 + k$ ($O(n)$); select all elements that are in the interval ($O(n + k)$); pick the $k$ smallest among those ($O(k \log k)$ by (partial) sorting).

(You should use $\Theta$ and $\Omega$ instead of saying things like "more than $O(n)$".)

(If the LaTeX confuses you, please get ChatJax++.)

$O(n + k \log n)$ is also easy (think of Heapsort).

i understand it - it just doesn't render here. anyway - what do you mean by " select all elements that are in the interval ($O(n + k)$);" ? I mean, why O(n+k)? shouldn't it be just O(n)?

@Kropekk You need to assemble the output.

But $O(n + k) \subseteq O(n)$ since $k \leq n$.

Hm. If $k \in o(n)$, all is well with this solution.

what do you mean by the last last line?

If not, can we capitalize from the fact the know we search for "most" elements?

@Kropekk In that case, $k \log k \in o(n)$, so $O(n + k \log k) \subseteq O(n)$.

Ah, I see now. Hint: knowing the median value, find the k-smallest difference from it. Work from there.

FWIW, this will only work in the uniform cost model, but that's probably what your instructor intends.

@Raphael k-smallest difference, but how to do that in other way than finding "n/2 - k" "n/2 + k" and than sort these two arrays?

Since you already know how to find order statistics, I'll let you chew on that for the time being. :)

So i'm stuck in the point that i've come here in... anyway, thanks ;)

I don't know how to give you a better hint without giving away everything, sorry.

Maybe this one: you can transform all values in S in linear time.

If you post the problem with your thoughts on the main site, I'll answer -- but only in a few days. I don't believe in taking away the fun of doing your own homework. ;)

@Raphael transform values - i don't understand... anyway, thanks a lot! ;) on Thursday i'll see how to solve this... so no need to post it on main site :)

@Kropekk hi, nice nick ;)

@Raphael [null, "chat", "Computer Science chat", "You are not machine? Come and prove it"] is now, any other texts or preference from given ones?

@Raphael ok, after correction and if it is doable, applying text I will post it on meta those versions at proper place. I wanted to get some feedback first, so thank you.

@EvilJS hello. how are you? ;)

What do you find nice about my nick? first time to hear it's 'nice' :D

@Kropekk fine, thank you, and you? If this was not intentional, the translation to my language means the male form of "dot", with additional "k" at the end.

@EvilJS bylo zamierzone ;)

@Raphael I found the solution, which is O(|S|), regardless of what k is. :)

@Kropekk Good job! Care to share?

@Raphael Is this where I come and talk about my feelings?

If you have something to share.

@Auberon so how do you feel about this secret that you share?