# Hash function orders ships from closest to furthest from the origin

Suppose we have a circular radar that scans for ships in an area enclosed by $$x^2+y^2 \leq z^2$$ (a circle).

We wish to design a hash function $$h$$ such that, we can order the $$n$$ ships from closest to furtest away from the origin.

We want to have an expected time complexity of this ordering algorithm to be done in $$\theta(n)$$ time.

Each ship has a coordinate $$(x,y)$$, and so I want my hash function to be something like $$\text{h((x,y)) = small index if close to origin, big index if farther}$$.

What would be a hash function and algorithm that can run in expected $$\theta(n)$$ time?

I think my hash function should be something like the following, taking into account the distance:

$$h((x,y)) = \sqrt{(x-0)^2 + (y-0)^2} = \sqrt{x^2+y^2}$$

## bumped to the homepage by Community♦14 hours ago

This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.

You can't. This problem is as hard as sorting, so it'll need $$\Omega(n \log n)$$ time (in the comparison-based model); it's not reasonable to expect a linear-time algorithm for sorting.