Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
November 21st, 2002, 01:20 AM
 Outrager
O.(O.O).O Champion

Join Date: Nov 2001
Location: New York, NY, USA
Posts: 26
Time spent in forums: 1 h 18 m 5 sec
Reputation 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?
__________________
iRants.com says, "WH(:O)MP! Wazoink!"

#2
November 21st, 2002, 01:51 PM
 M.Hirsch
Contributing User

Join Date: Oct 2000
Location: Back in the real world.
Posts: 5,966
Time spent in forums: 1 Month 2 Days 52 m 24 sec
Reputation Power: 190
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.
__________________
--
Manuel Hirsch - Linux, FreeBSD, programming, administration articles, tutorials and more.

#3
December 4th, 2002, 11:40 AM
 Strike
Contributing User

Join Date: Dec 2001
Location: Houston, TX
Posts: 383
Time spent in forums: 1 h 41 m 27 sec
Reputation Power: 12
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.
__________________
Debian - because life's too short for worrying.
Best. (Python.) IRC bot. ever.

#4
December 4th, 2002, 04:12 PM
 riv
Contributing User

Join Date: May 2001
Posts: 465
Time spent in forums: 3 h 46 m 15 sec
Reputation Power: 13
__________________
Words must be weighed, not counted.

 Viewing: Dev Shed Forums > Programming Languages - More > Software Design > Sorting a trip from longest or shortest