November 21st, 2002, 01:20 AM
Sorting a trip from longest or shortest
I'm doing this project in java that has an array of city objects that stores city names, longitudes, and latitudes and I need to sort it by the shortest trip and longest trip. Using a method I can calculate the distance between 2 cities given their longitude and latitude.
What's the easiest way (efficiency not really needed) to them into the longest and shortest trip?
November 21st, 2002, 01:51 PM
if efficiency does not matter, brute-force it (for school this probably won´t count!)
i.e. calculate all possible permutations of cities, then calculate the length of the way and then
- if you want to sort by length, search on google for "quicksort".
- if you only want the shortest and longest paths, find them in a single loop.
how many cities are there?
the number of loops max. needed is x.
all permutations for a given number n of cities are calculated as
x=n! = n*(n-1)*(n-2)*...*1
if your cpu can handle this many tries in a "normal" time, this is imho your "easiest" way.
December 4th, 2002, 11:40 AM
If you want something interesting to study, as well as an efficient way of doing this, then this is pretty much graph theory. It's not the easiest thing in the world, but some find it interesting and it's keyed to this sort of problem. Basically you have a set of vertices (the places) and edges (the distances between the vertices). There's a lot of good stuff on graph theory out there.
December 4th, 2002, 04:12 PM
Words must be weighed, not counted.