Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.java.help > #1135

Re: How to sort String array A based on int array B

Show all headers | View raw

On Monday, September 26, 2011 6:37:34 AM UTC-7, Thee Chicago Wolf (MVP) wrote:
> >On 9/23/2011 6:27 PM, Thee Chicago Wolf (MVP) wrote:
> >...
> >> The int array is already sorted:
> >>
> >> int[] rank = {1,2,3,4,5,6};
> >>
> >> The song tiltles are not sorted:
> >>
> >> String[] song = {"6_song",
> >> "4_song",
> >> "1_song",
> >> "3_song",
> >> "2_song",
> >> "5_song"};
> >>
> >> I took the top 6 songs from the "Top 40 Charts" that are already
> >> ranked from 1-6.
> >
> >This does not have much to do with the requirement you quoted earlier.
> 
> Patricia, what I think you're failing to see is that to rank a bunch
> of songs based on a *defined* rank of most to least popular will just
> re-randomize them and not order them in a rank. Top 40 songs are not
> ordered randomly but by popularity so you already *know* their rank as
> a byproduct of their popularity.
> 
> >> Modify any of the sort algorithms to sort a secondary array B based on
> >> the sorting order of A (that is akin to say: sort the titles of the
> >> songs (B) based on their rank (A).
> >
> >However, it is your homework problem, and I assume your interpretation
> >takes into account information given in class beyond the quoted problem
> >statement.
> 
> It just required thinking outside of the box, not something extra we
> discussed in class. One has to come to the conclusion that in order to
> sort a bunch of things that are String items, they somehow *have to*
> have an order to them, otherwise you're just re-randomizing (or
> alphabetizing), not ordering. At least that is how I see it. Thanks
> anyway.

You aren't seeing it in the usual way that homework assignments like this look for.

The Strings, as people keep telling you, do not figure into the comparisons or the sort.  They are payload, a technical term meaning they are the value carried by some key information.

This concept of payload, and of key-value pairs, pertains throughout the practice of algorithms.  This early homework assignment is supposed to teach you this paradigm.

You keep focusing on the String part, which is the "value" of the pair.  It is not the key.  You sort on keys, then look up the value based on the key.

For the sort in your homework, the key is the rank, which is sort of backwards from the usual perspective.  The fundamental insight is that you have a *pair* of things - in this case an (int, String) pair.  Ignoring ties (we can discuss tie-breakers another time), only one String-named thing can occupy a given rank at a time.

Pushing the rank into the String part of that pair is exactly the wrong thing to do.

As others have told you, part of your homework is to figure out how to maintain that pairwise association (int, String) as you move things around in their order.  

The simple but flawed approach, but good enough for homework now, is to maintain two arrays - one for rank and one for song name, or one for the 'int' part of the pair, and the other for the 'String' part.  You keep the two connected by always reflecting swaps in one that you do in the other.  So the nth element of the 'int' array always goes to the nth element of the 'String' array.  When you swap two elements of the 'int' array to get them in order, you do the exact same swap in the 'String' array.

More advanced is to create a simple type to hold the pair, with one value as the key for comparisons.

 public interface Song
 {
   int getRank();
   String getName();
 }

 public class ManagedSong
   implements Song, Comparable<Song>
 {
   private final int rank;
   private final String name;
   public ManagedSong( int r, String n )
   {
     this.rank = r;
     this.name = n;
   }
   @Override public int getRank() { return rank; }
   @Override public String getName() { return name; }
   @Override public int compareTo( Song song )
   {
     return song == null || getRank() > song.getRank()? 1 
         : getRank() == song.getRank()? 0 : -1;
   }
   @Override public boolean equals( Object o )
   {
     if ( ! o instanceof Song ) { return false; }
     Song song = (Song) o;
     return getRank() == song.getRank();
   }
   @Override public int hashCode()
   {
     return rank;
   }
 }

Now you can apply any sort algorithm you like to a 'Collection<ManagedSong>' of your choosing.

Things get more complicated if you allow ties for rank, but that's beyond the scope of your homework.

The main point is that you need to drop your current approach.  Don't mangle names to hold non-namey information.  Bad design.  

Sort your rank array as the key and let the values tag along for the ride.  Good design.

Rank: { 6, 3, 5, 1, 2, 4 }
Song: { "Doo-Wop Bop", "Having Fun", "Just Be Mine", "Love is Good", "Marriage or Money", "Zippers and Clips" }

after sorting:

Rank: { 1, 2, 3, 4, 5, 6 }
Song: { "Love is Good", "Marriage or Money", "Having Fun", "Zippers and Clips", "Just Be Mine", "Doo-Wop Bop" }

-- 
Lew

Back to comp.lang.java.help | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

How to sort String array A based on int array B "Thee Chicago Wolf [MVP]" <.@.> - 2011-09-22 14:31 -0500
  Re: How to sort String array A based on int array B markspace <-@.> - 2011-09-22 15:38 -0700
    Re: How to sort String array A based on int array B "Thee Chicago Wolf [MVP]" <.@.> - 2011-09-23 08:51 -0500
      Re: How to sort String array A based on int array B Patricia Shanahan <pats@acm.org> - 2011-09-23 07:23 -0700
        Re: How to sort String array A based on int array B "Thee Chicago Wolf [MVP]" <.@.> - 2011-09-23 10:51 -0500
          Re: How to sort String array A based on int array B Patricia Shanahan <pats@acm.org> - 2011-09-23 09:59 -0700
            Re: How to sort String array A based on int array B "Thee Chicago Wolf [MVP]" <.@.> - 2011-09-23 14:31 -0500
              Re: How to sort String array A based on int array B Patricia Shanahan <pats@acm.org> - 2011-09-23 12:39 -0700
              Re: How to sort String array A based on int array B "Charles Hottel" <chottel@earthlink.net> - 2011-09-23 17:42 -0400
                Re: How to sort String array A based on int array B "Thee Chicago Wolf (MVP)" <.@.> - 2011-09-23 20:27 -0500
                Re: How to sort String array A based on int array B Patricia Shanahan <pats@acm.org> - 2011-09-23 18:39 -0700
                Re: How to sort String array A based on int array B "Thee Chicago Wolf (MVP)" <.@.> - 2011-09-26 08:37 -0500
                Re: How to sort String array A based on int array B Patricia Shanahan <pats@acm.org> - 2011-09-26 08:04 -0700
                Re: How to sort String array A based on int array B "Thee Chicago Wolf [MVP]" <.@.> - 2011-09-27 13:47 -0500
                Re: How to sort String array A based on int array B "Thee Chicago Wolf [MVP]" <.@.> - 2011-09-27 13:59 -0500
                Re: How to sort String array A based on int array B Lew <lewbloch@gmail.com> - 2011-09-27 12:25 -0700
                Re: How to sort String array A based on int array B Lew <lewbloch@gmail.com> - 2011-09-26 09:00 -0700
                Re: How to sort String array A based on int array B "Charles Hottel" <chottel@earthlink.net> - 2011-09-23 23:31 -0400
                Re: How to sort String array A based on int array B "Thee Chicago Wolf (MVP)" <.@.> - 2011-09-26 08:29 -0500
  Re: How to sort String array A based on int array B Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-22 22:28 -0400
    Re: How to sort String array A based on int array B "Thee Chicago Wolf [MVP]" <.@.> - 2011-09-23 09:13 -0500
      Re: How to sort String array A based on int array B Eric Sosman <esosman@ieee-dot-org.invalid> - 2011-09-23 20:45 -0400
  Re: How to sort String array A based on int array B Roedy Green <see_website@mindprod.com.invalid> - 2011-09-23 02:28 -0700
    Re: How to sort String array A based on int array B "Thee Chicago Wolf [MVP]" <.@.> - 2011-09-23 09:14 -0500
  Re: How to sort String array A based on int array B Roedy Green <see_website@mindprod.com.invalid> - 2011-09-25 00:46 -0700

csiph-web