Skip to content
Tutorials Center
My learning

Topics

Lesson 39 of 134 ยท Collections

Sorting and Searching Arrays

Learn how to sort and search Ruby arrays - sort, sort_by, min and max, binary search with bsearch, include?, index, find, sum, tally and uniq, with runnable code.

Once data is in an array you usually want to put it in order, find the biggest or smallest item, check whether something is present, or remove duplicates. Ruby has a method for each of these jobs, and a few of them hide interesting details: sort_by is usually the right sort, min and max can return several results at once, sum is not just a shortcut for reduce, and bsearch is a real binary search that only works on sorted data.

This lesson goes through sorting (including sorting by several keys and in descending order), finding extremes, searching by value and by condition, binary search, counting, and removing duplicates. Along the way you will see which of these methods copy the array and which change it, what happens when the elements cannot be compared, and how to pick the cheapest method for the job.

sort and the spaceship operator

sort returns a new array in ascending order. It compares elements with the spaceship operator <=>, which returns -1, 0 or 1 (and nil when two objects cannot be compared). Numbers compare numerically, strings alphabetically by character code (so uppercase letters come before lowercase).

Ruby sort, sort with a block, sort!

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

The original numbers stays unchanged after sort, while sort! sorts in place. A block given to sort receives two elements and returns the spaceship result, so b <=> a reverses the order. 1 <=> "a" is nil, which leads to the next section.

Ruby Sorting mixed types (fails on purpose)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

Elements that cannot be compared raise ArgumentError. The first call is rescued and prints rescued: comparison of String with :pear failed, and [1, nil, 3].max ends the program with comparison of Integer with nil failed (ArgumentError). The fix is to clean the data (compact, map(&:to_i)) or to sort by a key that is always comparable.

sort_by: sorting by a key

Most real sorting is "sort these objects by this property". sort_by computes the key once per element and sorts by it. It is shorter than sort with a block, and faster when computing the key is expensive.

Ruby sort_by with one and several keys

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

The trick for multiple keys is to return an array: Ruby compares arrays element by element, so [-age, name] means "age descending, then name ascending". Negating a number reverses its order; for strings, sort ascending and call reverse, or use sort with the block. The last example shows why sort_by is better than plain sort for names with numbers: "a10" sorts before "a2" as text.

Ruby's sort is not guaranteed to be stable: elements that compare equal may come out in a different order than they went in. If you need a defined order for ties, include a tie-breaker in the key, such as [-age, name] above or [score, index] with each_with_index.

min, max and friends

Ruby Finding extremes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

With a number argument, min(2) and max(2) return the two smallest or largest in order, without sorting the whole array first, which is more efficient than sort.first(2) for large arrays. max_by and min_by take a block that produces the key. On an empty array max and min return nil.

sum, count and tally

sum adds up numbers (and anything that supports +, if you give a starting value). It also takes a block, which makes it a replacement for map(...).sum. For floating-point numbers, Ruby uses a compensated algorithm that is more accurate than a plain loop.

Ruby sum, count, tally, uniq

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

tally counts occurrences and returns a hash, which then combines nicely with max_by or sort_by for "most common" questions. uniq keeps the first of each value (or of each block result) and drops later duplicates; uniq! changes the array and returns nil when nothing was removed. The sum of the three floats is exactly 0.6, while reduce(:+) accumulates a tiny rounding error and gives 0.6000000000000001 (see Numbers).

Searching by value or condition

Ruby include?, index, find and friends

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

include? and index use == and scan from the start, which means the work grows with the array length. That is fine for small arrays. If you ask the same membership question many times about a large collection, build a Set once and use its constant-time include?. find returns the element, find_index its position; both return nil when nothing matches, so check before using the result.

Binary search with bsearch

If the array is sorted, you can find an element much faster than scanning: look in the middle, and discard the half that cannot contain the answer. For a million elements, that is about 20 steps instead of up to a million. Ruby provides bsearch, which works in two modes:

  • find-minimum mode: the block returns true or false; bsearch returns the first element for which the block is true. The block must be false for the first part of the array and true for the rest.
  • find-any mode: the block returns a number (like <=>): 0 for a match, negative to go left, positive to go right.
Ruby bsearch in both modes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

In find-any mode the block compares the target with the element (target <=> x): zero means found, and a negative result means the target is smaller, so search left. The last two lines wrap it into a membership test. Because bsearch assumes the order, calling it on unsorted data does not raise an error; it simply returns an answer that may be wrong. Sort first, or keep the array sorted.

Ruby bsearch on unsorted data gives a wrong answer

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

The first call returns nil even though 3 is in the array, because the binary search looked in the wrong half. After sorting, it finds the 3. include? always works, since it does not need order.

Random order with a seed

Shuffling and sampling are related to ordering. With a seeded random generator they become repeatable, which matters for tests (see Random Numbers and Math).

Ruby Reproducible shuffle and sample

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with gets), it gets the next line from this box.

Two generators with the same seed give the same shuffle, so test code can rely on it. Without random: the order differs on every run, so never print unseeded results in examples or compare them in tests.

Which one should I use?

  • Ordered copy: sort for plain comparable elements, sort_by for "by property".
  • Descending: sort_by { -key } for numbers, otherwise sort_by { key }.reverse.
  • Only the extreme: min, max, min_by, max_by. Do not sort just to take the first.
  • One element by condition: find; by value: index or include?.
  • Many lookups: build a Set or a Hash.
  • Sorted data and speed: bsearch.
  • Counting: count, tally; duplicates: uniq.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which call sorts words by length, longest first, and alphabetically among equal lengths?

    Returning an array as the key compares element by element: first the negated length (longest first), then the word itself for ties.
  2. 2. What does [3, "apple"].sort do?

    3 <=> "apple" is nil, so sort raises ArgumentError (a message of the form comparison of Integer with String failed).
  3. 3. What is [].max?

    min and max return nil for an empty array, while sum returns 0.
  4. 4. What must be true for bsearch to give a correct answer?

    bsearch halves the search space based on the order. On unsorted data it may silently return nil or a wrong element.
  5. 5. Which expression returns the most frequent word in words?

    tally builds a hash of counts; max_by picks the pair with the highest count and first returns the word.

Summary

  • sort orders comparable elements; sort_by orders by a key and is usually what you want. Return an array to sort by several keys.
  • Mixed or nil elements raise ArgumentError; ties are not guaranteed to keep their original order.
  • min, max, min_by, max_by and minmax find extremes (and min(n)/max(n) return the top n); empty arrays give nil.
  • sum handles numbers (and other types with a start value) accurately; tally counts; uniq removes duplicates.
  • include?, index, find and find_index scan linearly; use a Set or Hash for many lookups.
  • bsearch is a binary search with a find-minimum mode and a find-any mode, and only works on sorted data.
  • Use seeded Random objects for reproducible shuffles.

Next: Hashes