Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!gegeweb.42!gegeweb.eu!nntpfeed.proxad.net!proxad.net!feeder1-1.proxad.net!198.186.194.247.MISMATCH!news-out.readnews.com!transit3.readnews.com!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail From: Lew Newsgroups: comp.lang.java.help Subject: Re: How to sort String array A based on int array B Date: Mon, 26 Sep 2011 09:00:56 -0700 (PDT) Organization: http://groups.google.com Lines: 141 Message-ID: <3452617.773.1317052856872.JavaMail.geo-discussion-forums@prfh23> References: <1k2n77ltdv7ml661pa9a2g63j8q5l1c66g@4ax.com> <822p77tjmlsdrp2r7so1ko70igu9fascn6@4ax.com> <5PmdnbXtmIHNYOHTnZ2dnUVZ_vCdnZ2d@earthlink.com> Reply-To: comp.lang.java.help@googlegroups.com NNTP-Posting-Host: 67.218.102.230 Mime-Version: 1.0 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable X-Trace: posting.google.com 1317053738 11143 127.0.0.1 (26 Sep 2011 16:15:38 GMT) X-Complaints-To: groups-abuse@google.com NNTP-Posting-Date: Mon, 26 Sep 2011 16:15:38 +0000 (UTC) In-Reply-To: Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=67.218.102.230; posting-account=CP-lKQoAAAAGtB5diOuGlDQk0jIwmH0T User-Agent: G2/1.0 X-Google-Web-Client: true Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.help:1135 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 =3D {1,2,3,4,5,6}; > >> > >> The song tiltles are not sorted: > >> > >> String[] song =3D {"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. >=20 > 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. >=20 > >> 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. >=20 > 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. =20 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 { private final int rank; private final String name; public ManagedSong( int r, String n ) { this.rank =3D r; this.name =3D n; } @Override public int getRank() { return rank; } @Override public String getName() { return name; } @Override public int compareTo( Song song ) { return song =3D=3D null || getRank() > song.getRank()? 1=20 : getRank() =3D=3D song.getRank()? 0 : -1; } @Override public boolean equals( Object o ) { if ( ! o instanceof Song ) { return false; } Song song =3D (Song) o; return getRank() =3D=3D song.getRank(); } @Override public int hashCode() { return rank; } } Now you can apply any sort algorithm you like to a 'Collection= ' 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. =20 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" } --=20 Lew