6

One list with names:(unsorted) e.g [paul, foul, mark]

Another list with integers: e.g [5, 2, 6]

The values on the second list are the numbers "selected" by each person(name), so paul has number 5, foul's number is 2, mark's number is 6.

I'm trying to sort the names' list based on the values of the second list on a descending order. I cant use a map as i need both lists on other occasions on my program.

With the sorting method i did i get a list like that: [paul, mark, foul]

As you can see, its not sorted as i would want.

The correct one would be: [mark,paul,foul]

But i cant find the fault on the code.

public ArrayList<String> sortNames(ArrayList<Integer> results){
    String tmp;
    for (int k=0; k<Names.size()-1; k++) {

        boolean isSorted=true;
        for (int i=1; i<Names.size()-k; i++) {

             if (results.get(i)>results.get(i-1)  ) {

                tmp=Names.get(i);
                Names.set(i,Names.get(i-1));
                Names.set(i-1,tmp);

                isSorted=false;
            }
        }
        if (isSorted) break;
    }
    return Names;

}

EDIT!!! with the help of the answers below,the code is:

    public ArrayList<String> sortNames(ArrayList<Integer> results){
        String tmp2;
        int tmp;
        for (int k=0; k<Names.size()-1; k++) {

            boolean isSorted=true;
            for (int i=1; i<Names.size()-k; i++) {

                 if (results.get(i)>results.get(i-1)  ) {
                     tmp=results.get(i);
                     results.set(i,results.get(i-1));
                     results.set(i-1,tmp);


                    tmp2=Names.get(i);
                    Names.set(i,Names.get(i-1));
                    Names.set(i-1,tmp2);

                    isSorted=false;
                }
            }
            if (isSorted) break;
        }
    return Names;

}

This code works properly(for small lists) I've just the query why it doesnt work for objects like ImageIcon. Any ideas?

Improve this question
6
  • 1
    "I cant use a map as i need both lists on other occasions on my program." To do what, exactly? Commented Jan 29, 2011 at 23:16
  • Lists are needed on other classes for example. is it possible to sort them on a map and then use them separately? :/ Commented Jan 29, 2011 at 23:18
  • write any sort algo you find on the net quick/merge/shell/whatever and when you swap, swap both of the lists Commented Jan 30, 2011 at 1:02
  • 2
    To anyone offering Map uses: it doesn't allow duplicates Commented Jan 30, 2011 at 1:25
  • I know it can't, but probably a Multimap (e.g. from Guava) would do the job. Commented Jan 30, 2011 at 1:28

5 Answers 5

Reset to default
6

Get rid of the two Lists. If the data is related then the data should be stored together in a simple class. Then the entire class is added to a list where you can sort on the individual properties if required. You can use a Bean Comparator to sort this List however you desire.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

^this deserves to be the accepted answer, even if it doesn't answer the question directly. I was going to drop a wrap the int+string into a comparable class and sort it, unwrap it afterwards but then it's just that the data structure is flawed. There is one special case when using 2/3/n separate arrays is a good practice in java (but not in c) . It is working w/ very simple but exceptionally numerous structures like complex numbers; having 2 arrays double[] a,b than an array of class Complex{double a,b} is way better performance (and memory) wise. Yet, only in such case.
2

You're sort of sorting the List Names based on values of the List results... and it only terminates because of the condition k<Names.size()-1. Such a condition is usually not needed at all in bubblesort, which shows that there's something wrong.

You'd have to swap elements in both lists, not only in Names. This is the answer, but be warned that bubblesort is one of the worst algorithms ever.

Edit:

I cant use a map as i need both lists on other occasions on my program.

For sure you can (assuming the numbers are unique):

Map<Integer, String> m = new HashMap<Integer, String>();
for (int i=0; i<results.size(); ++i) m.put(results.get(i), Names.get(i));
Collections.sort(results);
for (int i=0; i<results.size(); ++i) Names.set(i, m.get(results.get(i));

There may be errors, but the idea should be clear.

There's another solution using a class of pairs (result, name), which works even with non-unique numbers, if you need it.

A slightly shorter solution:

Map<Integer, String> m = new TreeMap<Integer, String>();
for (int i=0; i<results.size(); ++i) m.put(results.get(i), Names.get(i));
Names.clear();
Names.addAll(m.values());

This is based on properties of TreeSet.values "The collection's iterator returns the values in ascending order of the corresponding keys" and List.addAll "Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection's iterator"

Improve this answer

20 Comments

What did you say about swapping is wright! Thanks! Could you explain a bit what do u mean in the beginning? I know that bubblesort doesnt need -1 on the counter of the size. But testing only the second note that you posted i get the correct results. How the first one doesnt react to it? :/ EDIT: comment posted before your edit.
Normally, bubble sort terminates simply because of the break in the outer loop. It's known, that it can't take more then N-1 iterations, but you don't need such a condition, s. en.wikipedia.org/wiki/Bubble_sort#Pseudocode_implementation Your wrong implementation would never terminated (unless when started with a sorted sequence). But that's unimportant... it was just my first idea as I saw it.
Collections.sort() requires a List, which HashMap doesn't implement.
Using map, is it possible after to use separately the 2 lists? - Sure, the map is only temporary. As for the bubblesort - In case your list are guaranteed to be very short (<10 items), it could make sense. For longer lists, the Map solution is faster. Anyway, I'd go for the simpler solution.
Collections.sort() requires a List, which HashMap doesn't implement. - Am I a fool using sort(map)?
|
1

  1. Build a list of pairs of (name, value) by taking elements from the two lists pairwise (having a class that stores the two values as fields). Implement Comparable to compare the value field.

  2. Sort the result with Collections.sort().

  3. Extract the names from the sorted list.

Improve this answer

4 Comments

Thanks Karl Knechtel. Your proposal is right. Im still thinking though if instead of using another class, its better to let it like the one i posted and use only what @maaartinus said about sorting also the second list.
Using a self-made algorithm is quite error-prone as you see. And buublesort is simply terrible for longer lists. Btw., I mentioned Karl's method at the end of my first edit, it was just to much writing.
aha thanks maaartinus. As for bubblesort,take in mind that my lists will have maximum size 4. So i dont think bubble effects so much,thats why i choosed it. Thanks for the ideas.
@maaartinus if one cant implement a sorting algorithm, there is not much point of
1

There you go w/ the vanilest quicksort you'd ever get, the simplest principle is: when you swap the 1st list, swap the 2nd as you go. Hopefully that's not a homework, but even if it's not... In short, copy/paste and enjoy the quickSort(list1, list2) is all you need. The lists are sorted by the 1st list natural oredering define by Comparable.

private static void swap(List<?> l1, List<?> l2, int i, int j){
    Collections.swap(l1, i, j);
    Collections.swap(l2, i, j);     
}
private static <T extends Comparable<? super T>>  int partition(List<T> comp, List<?> l2, int left, int right){
    int i = left, j = right;
    T pivot = comp.get((left + right) / 2);

    while (i <= j) {
        while (comp.get(i).compareTo(pivot)<0)
            i++;

        while (comp.get(i).compareTo(pivot)>0)
            j--;

        if (i <= j) {
            swap(comp, l2, i++, j--);
        }
    };
    return i;
}
private <T extends Comparable<? super T>>  void quickSort(List<T> comp, List<?> l2, int left, int right) {
    int index = partition(comp, l2, left, right);

    if (left < index - 1)
        quickSort(comp, l2, left, index - 1);

    if (index < right)
        quickSort(comp, l2, index, right);
}

public <T extends Comparable<? super T>>  void quickSort(List<T> comp, List<?> l2) {
    if (comp.size()<l2.size())
        throw new IndexOutOfBoundsException();
    quickSort(comp, l2, 0, comp.size());
}
Improve this answer

1 Comment

This does not work. For eg. try to sort a list {"abc", "cde","egg", "high", "jkl"} using list {1,2,3,4,5}. Here comp will be {1,2,3,4,5}. This goes not infinite loop.
1

Create a temporary mapping name->number, then sort names with custom comparator which uses the mapping:

Map<String, Integer> m = new HashMap<String, Integer>;
for(int i = 0; i < Names.size(); i++)
    m.put(Names.get(i), results.get(i));
Collections.sort(Names, new Comparator<String>() {
    @Override
    public int compare(String s1, s2) { return m.get(s2) - m.get(s1); }
});

This solution will work even if some numbers are equal.

Improve this answer

5 Comments

testing this. i get an error at line: "Names.sort(new Comparator<String>() {"
oops. if i understand well with this one u sort names right? but it sorts them separately with numbers, not according to their values. no?
@FILIas I forgot that sort() method is not on List, should work now. The Comparator makes sort use the previous mapping, descending order also goes here.
right miah. but what about the different values. are u sure it really works also for same values? cause normally hashmaps dont
This Map is Name->Number, not the other way. Names ARE unique, right?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.