Array sorting and reversing in Ruby - Time & Space Complexity

Time Complexity: Array sorting and reversing

O(n log n)

Understanding Time Complexity

When we sort or reverse an array, we want to know how the time it takes changes as the array gets bigger.

We ask: How does the work grow when the array size grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

arr = [5, 3, 8, 1, 2]
sorted_arr = arr.sort
reversed_arr = sorted_arr.reverse
puts reversed_arr

This code sorts an array and then reverses the sorted array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting the array (arr.sort) which compares and rearranges elements.
• How many times: Sorting usually looks at many pairs of elements multiple times depending on the algorithm.
• Secondary operation: Reversing the array (arr.reverse) which swaps elements from start to end once.
• How many times: Reversing goes through the array once, swapping pairs.

How Execution Grows With Input

Sorting takes more time as the array grows, much more than just going through it once.

Input Size (n)	Approx. Operations
10	About 30 to 40 comparisons and swaps
100	About 700 to 1000 comparisons and swaps
1000	About 10,000 to 15,000 comparisons and swaps

Pattern observation: Sorting grows faster than the size itself, roughly like n times log n. Reversing grows just like the size.

Final Time Complexity

Time Complexity: O(n log n)

This means sorting takes more time as the array grows, but reversing only adds a small extra step.

Common Mistake

[X] Wrong: "Sorting and reversing both take the same time because they both touch every element."

[OK] Correct: Reversing just swaps elements once, so it grows linearly. Sorting compares many pairs multiple times, so it grows faster than just the number of elements.

Interview Connect

Understanding how sorting and reversing scale helps you explain your code choices clearly and shows you know what happens behind the scenes.

Self-Check

"What if we used a different sorting method that is already optimized for nearly sorted arrays? How would the time complexity change?"

Practice

1. What does the Ruby method sort do when called on an array?

easy

A. It arranges the elements in ascending order.

B. It reverses the order of elements.

C. It removes duplicate elements.

D. It shuffles the elements randomly.

Solution

1. Step 1: Understand the purpose of sort

   The sort method arranges elements in ascending order by default.

2. Step 2: Compare with other methods

   Unlike reverse which flips order, sort orders elements from smallest to largest.

3. Final Answer:

   It arranges the elements in ascending order. -> Option A

4. Quick Check:

   sort = ascending order [OK]

Hint: Remember: sort arranges ascending, reverse flips order [OK]

Common Mistakes:

• Confusing sort with reverse
• Thinking sort removes duplicates
• Assuming sort shuffles elements

2. Which of the following is the correct syntax to reverse an array arr in Ruby?

easy

A. arr.reverse!

B. arr.reverse[]

C. reverse.arr()

D. arr.reverse()!

Solution

1. Step 1: Identify the correct method call

   The method to reverse an array in place is reverse! called on the array object.

2. Step 2: Check syntax correctness

   Only arr.reverse! is valid Ruby syntax; others are incorrect method calls or misplaced symbols.

3. Final Answer:

   arr.reverse! -> Option A

4. Quick Check:

   reverse! modifies array in place [OK]

Hint: Use reverse! to reverse array in place [OK]

Common Mistakes:

• Using parentheses incorrectly
• Placing exclamation mark after parentheses
• Calling reverse as a standalone function

3. What is the output of the following Ruby code?

arr = [3, 1, 4, 2]
sorted_arr = arr.sort
reversed_arr = sorted_arr.reverse
puts reversed_arr.inspect

medium

A. [1, 2, 3, 4]

B. [3, 1, 4, 2]

C. [4, 3, 2, 1]

D. [2, 4, 1, 3]

Solution

1. Step 1: Sort the original array

   Calling arr.sort returns a new array sorted ascending: [1, 2, 3, 4].

2. Step 2: Reverse the sorted array

   Calling sorted_arr.reverse flips the order to [4, 3, 2, 1].

3. Final Answer:

   [4, 3, 2, 1] -> Option C

4. Quick Check:

   sort then reverse = descending order [OK]

Hint: Sort then reverse = descending order [OK]

Common Mistakes:

• Assuming reverse modifies original array
• Confusing sorted array with original
• Expecting reverse to sort ascending

4. Identify the error in this Ruby code snippet:

arr = [5, 2, 9]
arr.sort!
arr.reverse
puts arr.inspect

medium

A. Missing parentheses in method calls cause errors.

B. The sort! method is invalid syntax.

C. The array arr cannot be reversed after sorting.

D. Using reverse does not change arr in place.

Solution

1. Step 1: Understand sort! effect

   sort! sorts the array arr in place, so arr becomes [2, 5, 9].

2. Step 2: Check reverse method usage

   reverse returns a new reversed array but does not modify arr itself.

3. Final Answer:

   Using reverse does not change arr in place. -> Option D

4. Quick Check:

   reverse without ! returns new array [OK]

Hint: Use reverse! to modify array in place [OK]

Common Mistakes:

• Assuming reverse changes original array
• Thinking sort! is invalid
• Believing method calls need parentheses always

5. Given an array arr = [7, 3, 5, 3, 9, 1], how can you create a new array that is sorted in descending order without changing the original array?

hard

A. Use arr.sort! then arr.reverse!

B. Use arr.sort.reverse

C. Use arr.reverse.sort

D. Use arr.reverse! then arr.sort!

Solution

1. Step 1: Sort the array without modifying original

   arr.sort returns a new sorted array ascending, original arr stays unchanged.

2. Step 2: Reverse the sorted array to get descending order

   Calling reverse on the sorted array returns a new array reversed, still not changing original.

3. Final Answer:

   Use arr.sort.reverse -> Option B

4. Quick Check:

   sort then reverse = descending new array [OK]

Hint: Chain sort then reverse to get descending without changing original [OK]

Common Mistakes:

• Using sort! or reverse! which modify original array
• Reversing before sorting
• Expecting reverse.sort to work the same