#1
  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?
    iRants.com says, "WH(:O)MP! Wazoink!"
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed God 1st Plane (5500 - 5999 posts)

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

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

    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.
  6. #4
  7. Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2001
    Posts
    465
    Rep Power
    14
    Words must be weighed, not counted.

IMN logo majestic logo threadwatch logo seochat tools logo