Sort_by for custom sorting in Ruby - Time & Space Complexity

Time Complexity: Sort_by for custom sorting

O(n log n)

Understanding Time Complexity

When we use sort_by in Ruby, it helps us sort items based on a custom rule.

We want to know how the time it takes to sort grows as we have more items.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

items = ["apple", "banana", "pear", "grape"]
sorted = items.sort_by { |item| item.length }
puts sorted

This code sorts a list of words by their length using sort_by.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The sorting process compares items based on their length.
• How many times: It compares items multiple times, roughly proportional to the number of items times the logarithm of that number.

How Execution Grows With Input

As the list gets bigger, the number of comparisons grows faster than just the number of items.

Input Size (n)	Approx. Operations
10	About 30 comparisons
100	About 700 comparisons
1000	About 10,000 comparisons

Pattern observation: The work grows a bit faster than the list size, but not as fast as the square of the size.

Final Time Complexity

Time Complexity: O(n log n)

This means that if you double the number of items, the time to sort grows a bit more than double, but much less than square.

Common Mistake

[X] Wrong: "Sorting with sort_by takes the same time no matter how many items there are."

[OK] Correct: Sorting needs to compare items, and more items mean more comparisons, so time grows as the list grows.

Interview Connect

Understanding how sorting time grows helps you explain your code choices clearly and shows you know how your program behaves with bigger data.

Self-Check

"What if the block inside sort_by was more complex and took longer to run for each item? How would that affect the time complexity?"

Practice

1. What does the Ruby method sort_by do?

easy

A. Sorts elements based on a value you specify for each element.

B. Changes the original array to a sorted one.

C. Removes duplicate elements from an array.

D. Reverses the order of elements in an array.

Solution

1. Step 1: Understand the purpose of sort_by

   sort_by sorts elements by a value you choose for each element, like length or age.

2. Step 2: Compare with other array methods

   Unlike sort!, sort_by returns a new sorted array without changing the original.

3. Final Answer:

   Sorts elements based on a value you specify for each element. -> Option A

4. Quick Check:

   sort_by sorts by chosen value [OK]

Hint: Remember: sort_by sorts by a custom value, not in-place [OK]

Common Mistakes:

• Thinking sort_by changes the original array
• Confusing sort_by with reverse or uniq
• Assuming sort_by removes duplicates

2. Which of the following is the correct syntax to sort an array words by their length using sort_by?

easy

A. words.sort_by(word.length)

B. words.sort_by => word.length

C. words.sort_by { |word| word.length }

D. words.sort_by(word) { length }

Solution

1. Step 1: Recall Ruby block syntax for sort_by

   The correct syntax uses a block with curly braces and a block variable: array.sort_by { |item| expression }.

2. Step 2: Match syntax with the options

   words.sort_by { |word| word.length } correctly uses words.sort_by { |word| word.length }. Others have syntax errors or wrong usage.

3. Final Answer:

   words.sort_by { |word| word.length } -> Option C

4. Quick Check:

   sort_by needs a block with |variable| [OK]

Hint: Use curly braces and |var| for sort_by blocks [OK]

Common Mistakes:

• Passing arguments directly instead of using a block
• Using => instead of block braces
• Misplacing parentheses around block

3. What will be the output of this Ruby code?

people = [{name: "Anna", age: 30}, {name: "Bob", age: 25}, {name: "Cara", age: 35}]
sorted = people.sort_by { |person| person[:age] }
puts sorted.map { |p| p[:name] }

medium

A. ["Anna", "Bob", "Cara"]

B. ["Bob", "Anna", "Cara"]

C. ["Cara", "Anna", "Bob"]

D. ["Bob", "Cara", "Anna"]

Solution

1. Step 1: Understand sorting by age

   The array is sorted by the :age key in ascending order: 25, 30, 35.

2. Step 2: Map sorted array to names

   After sorting, the order is Bob (25), Anna (30), Cara (35). Mapping names gives ["Bob", "Anna", "Cara"].

3. Final Answer:

   ["Bob", "Anna", "Cara"] -> Option B

4. Quick Check:

   sort_by age ascending = [Bob, Anna, Cara] [OK]

Hint: Sort_by returns new array sorted by block value [OK]

Common Mistakes:

• Assuming sort_by sorts descending by default
• Confusing keys in hash access
• Not mapping to names after sorting

4. Identify the error in this code snippet:

items = ["apple", "pear", "banana"]
sorted = items.sort_by do |item|
  item.length
end
puts sorted

medium

A. No error; code works correctly

B. Incorrect block syntax for sort_by

C. Missing parentheses in sort_by call

D. Using sort_by instead of sort

Solution

1. Step 1: Check block syntax

   The block uses do |item| ... end, which is valid for sort_by.

2. Step 2: Verify sort_by usage

   sort_by accepts a block and returns a new array sorted by item length. No syntax or logic errors.

3. Final Answer:

   No error; code works correctly -> Option A

4. Quick Check:

   sort_by with do-end block is valid [OK]

Hint: do-end blocks work fine with sort_by [OK]

Common Mistakes:

• Thinking parentheses are mandatory around block
• Confusing sort_by with sort!
• Assuming sort_by modifies original array

5. Given an array of hashes representing products:

products = [
  {name: "Pen", price: 1.5, stock: 10},
  {name: "Notebook", price: 2.0, stock: 0},
  {name: "Eraser", price: 0.5, stock: 5}
]

How would you use sort_by to get products sorted by price but only include those with stock greater than zero?

hard

A. products.sort_by { |p| p[:stock] }.select { |p| p[:price] > 0 }

B. products.sort_by { |p| p[:price] if p[:stock] > 0 }

C. products.sort_by { |p| p[:stock] > 0 ? p[:price] : 0 }

D. products.select { |p| p[:stock] > 0 }.sort_by { |p| p[:price] }

Solution

1. Step 1: Filter products with stock > 0

   Use select to keep only products where stock is greater than zero.

2. Step 2: Sort filtered products by price

   Apply sort_by on the filtered array to sort by price.

3. Final Answer:

   products.select { |p| p[:stock] > 0 }.sort_by { |p| p[:price] } -> Option D

4. Quick Check:

   Filter then sort_by for correct result [OK]

Hint: Filter first, then sort_by for combined conditions [OK]

Common Mistakes:

• Trying to filter inside sort_by block
• Sorting by stock instead of price
• Selecting after sorting, which keeps unwanted items