File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Java in General and the fly likes Sorting two ArrayLists, one dependent on the other Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Sorting two ArrayLists, one dependent on the other" Watch "Sorting two ArrayLists, one dependent on the other" New topic
Author

Sorting two ArrayLists, one dependent on the other

Krit Christoforou
Ranch Hand

Joined: Mar 01, 2005
Posts: 46
Hello all,
I have two ArrayLists in my program:
- one contains words,
- and the other contains their respective pronunciation symbols.

I want to sort the two arraylists
The simplest way to sort the words is Collections.sort(WordsList).

The problem is that i want to sort the pronunciations list as well, but not alphabetically, because its dependent on the words list.

For example suppose this is my dictionary
ABACIae b ax s ay
ABACUS ae b ax k ax s
ABACKax b ae k

Therefore the words list contains [ABACI, ABACK, ABACUS] and the pronunciations list contains [ae b ax s ay, ax b ae k, ae b ax k ax s]

The bug question is:
How can i sort the words list alphabetically, and sort the pronunciation list so that each of the words keeps its pronunciation?

Is there a way to do that without writing my own code?
If not, what's the best sort method i can use for large ArrayLists?

Thanks
Ernest Friedman-Hill
author and iconoclast
Marshal

Joined: Jul 08, 2003
Posts: 24187
    
  34

There's no way to do it without writing your own parallel-sort routine, unless you can find one on the Internet somewhere. But ask yourself why you've got two parallel ArrayLists of Strings, instead of one ArrayList of Word objects, which have "text" and "pronunciation" properties? This would make your problem go away.


[Jess in Action][AskingGoodQuestions]
Yevgeniy Treyvus
Ranch Hand

Joined: Mar 09, 2005
Posts: 48
You can search for a reply I posted on Apr 1st in this forum. Search for "Dynamic Arrays In Java" and there's a code example there that can help you.


SCJP, SCJD
Ryan McGuire
Ranch Hand

Joined: Feb 18, 2005
Posts: 1010
    
    3
Three ideas spring to mind:
  • Implement your own sort that swaps elements in both ArrayLists.
  • Define a new class to hold a word and its pronunciation. Then define a new Comparable that takes two objects of the new class and compares just the words.
  • Before sorting, use the two ArrayLists to populate a HashMap. Sort the words. Then use the values in the HashMap to repopulate the pronunciation ArrayList in the new order.


  • I think I like the second one best.

    Ryan
    Krit Christoforou
    Ranch Hand

    Joined: Mar 01, 2005
    Posts: 46
    Indeed, that is a very good question, but i'm learning as i'm building my project, from my mistakes. Therefore i'm stuck with the two ArrayLists for now as i would need too much time to change it into one ArrayList.

    Which sort algorithm is the best for this purpose? Any useful links you can suggest?

    I have tried doing that with a Selection sort, and it is way too slow.

    Just out of curiosity, which sort algorithm does Collections.sort() use?
    Krit Christoforou
    Ranch Hand

    Joined: Mar 01, 2005
    Posts: 46
    Originally posted by Ryan McGuire:
    Three ideas spring to mind:
  • Implement your own sort that swaps elements in both ArrayLists.
  • I tried this with selection sort and it's too slow. Any suggestions for any alternative methods?
  • Define a new class to hold a word and its pronunciation. Then define a new Comparable that takes two objects of the new class and compares just the words.
  • No time for that, besides i'm a beginner and i'd mess everything up instead!
  • Before sorting, use the two ArrayLists to populate a HashMap. Sort the words. Then use the values in the HashMap to repopulate the pronunciation ArrayList in the new order.

  • The problem is that i've got duplicate words(with different pronunciations) duplicate pronunciations(with different words), so a set would delete some of them.
    Ryan McGuire
    Ranch Hand

    Joined: Feb 18, 2005
    Posts: 1010
        
        3
    Or as a combination of my second (similar to Ernest's) and third ideas...

    - Define a (possibly inner) Word class, which implements Comparable and has word and pronunciation fields.
    - Fill up a temporary ArrayList with these objects from the two separate ArrayLists.
    - Sort the temp ArrayList of Word objects using Collection.sort().
    - Use the sorted Word objects to repopulate the original ArrayLists of words and pronunciations.

    This has the advantage of basically doing the right thing, but without having to go back through all your code that already has words and pronunciations in two separate ArrayLists.

    ...but yes, it's a hack.

    Ryan
    [ April 07, 2005: Message edited by: Ryan McGuire ]
    M Beck
    Ranch Hand

    Joined: Jan 14, 2005
    Posts: 323
    is this a case of there never being enough time to do it right, but always enough time to do it over?

    if you should decide you do have enough time, the Java Collections framework has an interface that might do the job for you. associating pronunciations with spellings is the perfect job for a dictionary data structure (which java calls a Map), and someone has seen fit to create one that keeps its keys in sorted order; sounds like just what the doctor ordered, to me.
    Krit Christoforou
    Ranch Hand

    Joined: Mar 01, 2005
    Posts: 46
    Hmm, i thought that a map might do the job, but i can't understand how it works, and what it really does.
    I'm trying to understand what Ryan suggested with storing the lists in a temporary list, and if i get it right eventually, i'll do that.
    I actually have quite a lot of time ahead of me but i dont feel really comfortable trying to make such bug changes to the program because i might end with a half working program and no time.
    Krit Christoforou
    Ranch Hand

    Joined: Mar 01, 2005
    Posts: 46
    Is there a way to make a two column ArrayList and sort the first column alphabetically with collections.sort? If i made it that way would the second column sort correctly with the first column?
    M Beck
    Ranch Hand

    Joined: Jan 14, 2005
    Posts: 323
    i don't think so; a List is "single-column" by definition. you should be able to sort it - i've never tried to do that in Java myself, but it shouldn't be very hard - but what'll be sorted are the individual items in the list.

    but you're making headway; you're creeping up on the idea of making a two-item custom data type, storing objects of that in a list, and then sorting that list, here. that would be one way of making a "two-column list", and possibly the most direct one to get functionality equivalent to that description.

    however, for reference, i'll try to explain how a Map (dictionary) works. it's a tremendously useful data type, and it's crucial to properly using several other languages (Perl, Python, AWK, and others).

    a dictionary is basically a set of name==value mappings. each entry in the dictionary consists of a "key" (the name) and a "value". when you put stuff into the dictionary, you have to specify both key and value; to retrieve a value, you only have to know the key.

    some people like to think of a dictionary as a special kind of array, where absolutely anything can serve as the index (the key), and you don't have to specify the size of the array when you declare it because it'll grow and shrink as needed. the term "associative array" (associating the values with the keys) is an older synonym for "dictionary".

    dictionaries are usually implemented as hash tables behind the scenes (that's why Perl calls them "hashes"), and this is why you typically can't have duplicate keys in a dictionary. one name, normally, can only have one value - but that's not much of a concern; if you need more values, put them in a List and store that as the value.

    Java has several kinds of dictionary (Map, in Java-ese) with different implementations behind the scenes. apart from the plain-vanilla hashtable-based version, there's one that maintains the keys in the order you created them, so you can iterate through them in FIFO sequence. another even keeps the keys sorted so you can iterate through them in order - fairly fancy; most languages make you extract the list of keys, sort that, and iterate through the result.
     
    It is sorta covered in the JavaRanch Style Guide.
     
    subject: Sorting two ArrayLists, one dependent on the other