Start learning free

LESSON 271 OF 679 · TUPLES, SORTING & BUILT-INS

Shortest Words First in Rust: Sorting with sort_by and then

Practice Read the full explanation

You get a Vec of words, words. Return the words sorted from shortest to longest.

Words of the same length go in alphabetical order, from A to Z.

A word can appear more than once. Every copy stays in the result.

 

Example 1:

Input: words = ["banana", "fig", "apple", "kiwi"]
Output: ["fig", "kiwi", "apple", "banana"]
Explanation: "fig" has 3 letters and "kiwi" has 4.
"apple" has 5 and "banana" has 6.

Example 2:

Input: words = ["dog", "cat", "ant", "bee"]
Output: ["ant", "bee", "cat", "dog"]
Explanation: All four words have 3 letters.
So they go from A to Z.

Example 3:

Input: words = ["sun", "a", "moon", "sun"]
Output: ["a", "sun", "sun", "moon"]
Explanation: "sun" appears twice, so it stays twice.
Both copies come after "a" and before "moon".

 

Constraints:

  • words has 1 to 100 words.
  • Each word has 1 to 20 lowercase letters.
STEP 1 OF 2
    Ctrl + Enter to check

    RUST · TUPLES, SORTING & BUILT-INS

    Shortest Words First in Rust, explained

    Problem overview

    The function sort_by_length receives a vector of words, words, and returns it sorted from the shortest word to the longest. Words of the same length go in alphabetical order. A word that appears more than once stays in the result as many times as it appeared.

    For ["banana", "fig", "apple", "kiwi"] the answer is ["fig", "kiwi", "apple", "banana"]: lengths 3, 4, 5 and 6. For ["dog", "cat", "ant", "bee"] every word has 3 letters, so the order is alphabetical: ["ant", "bee", "cat", "dog"]. For ["sun", "a", "moon", "sun"] the answer is ["a", "sun", "sun", "moon"].

    Approach

    A plain sort() would order the words alphabetically only. Here the main rule is length, and the alphabet only breaks ties. sort_by takes a closure that compares two items, so two rules fit in one closure: compare the lengths first, and compare the words themselves only when the lengths are equal.

    The cmp method compares two values and returns an Ordering, which is Less, Equal or Greater. The method then on an Ordering keeps the first result unless it is Equal; only then does it use the second one. That is exactly the tie-breaking rule the statement asks for.

    Step by step

    1. Sort in place. The parameter is declared mut words, so words.sort_by(...) can reorder the vector itself. The closure gets two items, a and b, as references.
    2. First rule: a.len().cmp(&b.len()) puts the shorter word first. The argument of cmp is a reference, hence the &.
    3. Second rule: chain .then(a.cmp(b)). Comparing two strings with cmp orders them alphabetically, and then uses it only for words of equal length.
    4. Return words. Sorting only moves words around, so duplicates are never dropped.

    The solution in Rust

    impl Solution {
    fn sort_by_length(mut words: Vec<String>) -> Vec<String> {
        words.sort_by(|a, b| a.len().cmp(&b.len()).then(a.cmp(b)));
        return words;
    }
}

    len() counts bytes, which equals the number of letters here because the words use only lowercase letters a to z. String comparison is by bytes too, so lowercase words come out in A to Z order.

    Another way

    When both rules point the same way, sort_by_key can compare a tuple of keys. Tuples compare field by field, so the length decides first and the word breaks ties:

    words.sort_by_key(|w| (w.len(), w.clone()));

    On ["sun", "a", "moon", "sun", "kiwi", "fig"] this gives ["a", "fig", "sun", "sun", "kiwi", "moon"]. The clone() is needed because the key must be an owned value. The lesson's sort_by avoids that copy, and it is the form that also works when one rule must run in reverse, such as sorting scores from high to low.

    Testing

    The three examples give:

    ["fig", "kiwi", "apple", "banana"]
["ant", "bee", "cat", "dog"]
["a", "sun", "sun", "moon"]

    Edge cases and common mistakes

    • Forgetting the second rule. With only the length comparison, the order of equal-length words is not defined by the rule you wrote, so the tests for ties could fail.
    • Swapping a and b in the length rule. That sorts the longest word first.
    • Calling sort_by on a vector declared without mut. The compiler reports that it cannot borrow the vector as mutable; the lesson's signature already has mut words.
    • Thinking sort_by returns the sorted vector. It sorts in place and returns nothing, which is why the function sorts first and returns words on the next line.
    Keep going with Rust500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free