Re: How to sort String array A based on int array B
On Monday, September 26, 2011 6:37:34 AM UTC-7, Thee Chicago Wolf (MVP) wro=
te:
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 l=
ook 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 valu=
e carried by some key information.
This concept of payload, and of key-value pairs, pertains throughout the pr=
actice 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 backwa=
rds 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 occ=
upy a given rank at a time.
Pushing the rank into the String part of that pair is exactly the wrong thi=
ng to do.
As others have told you, part of your homework is to figure out how to main=
tain that pairwise association (int, String) as you move things around in t=
heir order.
The simple but flawed approach, but good enough for homework now, is to mai=
ntain 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 c=
onnected by always reflecting swaps in one that you do in the other. So th=
e nth element of the 'int' array always goes to the nth element of the 'Str=
ing' array. When you swap two elements of the 'int' array to get them in o=
rder, 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 a=
s 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 t=
he scope of your homework.
The main point is that you need to drop your current approach. Don't mangl=
e 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", "Marri=
age 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 Cli=
ps", "Just Be Mine", "Doo-Wop Bop" }
--
Lew