Sort a String ArrayList based on order defined by another String Array

Question

I've seen several other questions similar to this one but I haven't really been able to find anything that resolves my problem.

What would be the way to sort numberWords ArrayList based on ORDER array?

I'm not saying that numberWords must be ArrayList, it can be an array as well, but I thought it might fit better for getStoredWords() method as I should return List<String>. Tried to compare numberWords to ORDER e.g. numberWords.get(first).equals(ORDER[first]), but it didn't work out the way it should.

public class WordStore {
    List<String> numberWords = new ArrayList<>();

    private static final String[] ORDER = {
            "one", "two", "three", "four", "five",
            "six", "seven", "eight", "nine", "ten"
    };

    public void add(String numberAsWord) {
        numberWords.add(numberAsWord);
    }

    public List<String> getStoredWords() {
        
    }
}

Example tests:

public void insertedInArbitraryOrder() {
        WordStore wordStore = new WordStore();

        wordStore.add("three");
        wordStore.add("one");
        wordStore.add("two");
        wordStore.add("ten");
        wordStore.add("one");
        wordStore.add("five");
        wordStore.add("ten");
        wordStore.add("nine");
        wordStore.add("eight");

        assertThat(wordStore.getStoredWords(),
                contains("one", "one", "two", "three",
                        "five", "eight", "nine", "ten", "ten"));
    }

public void insertedInReverseOrder() {
        WordStore wordStore = new WordStore();

        wordStore.add("three");
        wordStore.add("two");
        wordStore.add("one");

        assertThat(wordStore.getStoredWords(),
                contains("one", "two", "three"));

    }

You need to map your words to their position in ORDER like Lino already suggested. For larger lists you might also consider using a Map<String, Integer> which maps the words (keys) to some order (in your case those could be the actual integer values). — Thomas
– Thomas, Commented Mar 29, 2021 at 8:47
@NikolasCharalambidis I think you're right, it wouldn't work with binarySearch — Lino
– Lino, Commented Mar 29, 2021 at 11:00

Nikolas · Accepted Answer · 2021-03-29 09:53:48Z

3

It can be a one-liner, but don't do it, this approach is not good performance-wise.

numberWords.sort(Comparator.comparingInt(ORDER::indexOf));               // DON'T use me

However, let's reuse the idea of the look-up based on the index of each word as the order definition.

You need two steps:

Extraction: Assign a numeric order to each word in ORDERS. The data structure Map<String, Integer> is suitable for it. The HashMap is useful for look-up based on the word.
```
Map<String, Integer> orders = IntStream.range(0, ORDER.length)
        .boxed()
        .collect(Collectors.toMap(i -> ORDER[i], Function.identity()));
```
The key is the word itself (for look-up) and value is its position or index.
Sort: Using the comparison based on the integers obtained through the map for each word.
```
numberWords.sort(Comparator.comparingInt(orders::get));
```

edited Mar 29, 2021 at 9:53

answered Mar 29, 2021 at 8:59

Nikolas

45k19 gold badges132 silver badges201 bronze badges

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

Collectives™ on Stack Overflow

Sort a String ArrayList based on order defined by another String Array

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related