Re: Need some help with sorting

jobo schrieb:
Hey there,

I'm having some issues trying to figure out an efficient way to do
this.
So I query a database for a bunch of real estate properties that gives
me latitude/longitude coordinates. The maximum number of results that
will be returned is 100.

From those 100 properties I need to calculate a bounding box that will
enclose all 100 properties. This might sound confusing, but just think
about a graph full of X/Y coordinates and you need to calculate an
appropiate view screen that will show all points.

The solution I have come up with is you have an array of latitude/
longitude and you have two for loops that would iterate and calculate
maximum distance between two points and keep track of the current
maximum distance between two points untl it reaches the end of the
loop. But this is a very inefficient solution.

Given that there are 100 properties it would give me a Big-O of
100*100 = 10,000 iterations.

I was thinking of sorting the points somehow and indexing is (nlogn)
then iterate through it once to find the maximum distance which would
be at most 100*log(100) + 100 = 300.

Anyone have any ideas? Thanks!


sounds like homework...

1. you can let the database/SQLQuery calculate the Bounding box..
2. if you want java do it than it can be done in O(n)
as you only need maximum and minimum values of longitude and latitude..

just scan through all points and check them against current max and
minvaules and voila you got your bounding box..

3. there is no Big-O of 10000 .. O(10000) = O(1) so for 100 entrys your
solution will allways be in O(1) and therefore "fast"

4. log(100) is not 2 ... not that it matters in O notation... but binary
sort algos log would be of base 2
.

Relevant Pages

  • Re: Need some help with sorting
    ... me latitude/longitude coordinates. ... longitude and you have two for loops that would iterate and calculate ... maximum distance between two points untl it reaches the end of the ... It'll be a bounding box. ...
    (comp.lang.java.programmer)
  • Re: Need some help with sorting
    ... me latitude/longitude coordinates. ... longitude and you have two for loops that would iterate and calculate ... maximum distance between two points untl it reaches the end of the ... and its longitudeMax will be>= any returned property's longitudeMax, and similarly for the latitudeMin and latitudeMax. ...
    (comp.lang.java.programmer)
  • Need some help with sorting
    ... longitude and you have two for loops that would iterate and calculate ... maximum distance between two points untl it reaches the end of the ... But this is a very inefficient solution. ...
    (comp.lang.java.programmer)
  • Re: Need some help with sorting
    ... So I query a database for a bunch of real estate properties that gives ... longitude and you have two for loops that would iterate and calculate ... maximum distance between two points untl it reaches the end of the ... Use one loop only, no nesting. ...
    (comp.lang.java.programmer)