Thread: Sorting a trip from longest or shortest

1. No Profile Picture
O.(O.O).O Champion
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2001
Location
New York, NY, USA
Posts
26
Rep Power
0

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?
2. No Profile Picture
Contributing User
Devshed God 1st Plane (5500 - 5999 posts)

Join Date
Oct 2000
Location
Back in the real world.
Posts
5,960
Rep Power
193
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.
3. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Dec 2001
Location
Houston, TX
Posts
383
Rep Power
16

Graphs!

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.