Ruby Program for Quick Sort Algorithm Example

A Ruby program for quick sort uses a recursive method that picks a pivot, divides the array into smaller and larger parts, and sorts them with quick_sort(array) calling itself on subarrays.

Examples

Input[3, 1, 4, 1, 5]

Output[1, 1, 3, 4, 5]

Input[10, 7, 8, 9, 1, 5]

Output[1, 5, 7, 8, 9, 10]

Input[]

Output[]

How to Think About It

To sort an array using quick sort, pick a pivot element, then split the array into two parts: one with elements smaller than the pivot and one with elements larger or equal. Recursively apply the same process to these parts until the array is fully sorted.

Algorithm

1

If the array has 0 or 1 element, return it as it is already sorted.

2

Choose the last element of the array as the pivot.

3

Create two new arrays: one for elements less than the pivot, one for elements greater or equal.

4

Recursively quick sort the smaller and larger arrays.

5

Combine the sorted smaller array, pivot, and sorted larger array into one sorted array.

6

Return the combined sorted array.

Code

ruby

def quick_sort(arr)
  return arr if arr.length <= 1
  pivot = arr.pop
  left = arr.select { |x| x < pivot }
  right = arr.select { |x| x >= pivot }
  quick_sort(left) + [pivot] + quick_sort(right)
end

puts quick_sort([3, 1, 4, 1, 5]).inspect

Output

[1, 1, 3, 4, 5]

Dry Run

Let's trace quick_sort([3, 1, 4, 1, 5]) through the code

1

Initial call

Array: [3, 1, 4, 1, 5], pivot = 5, left = [3, 1, 4, 1], right = []

2

Sort left side

Call quick_sort([3, 1, 4, 1])

3

Left side pivot

Array: [3, 1, 4, 1], pivot = 1, left = [], right = [3, 4, 1]

4

Sort right side of left

Call quick_sort([3, 4, 1])

5

Right side pivot

Array: [3, 4, 1], pivot = 1, left = [], right = [3, 4]

6

Sort right side of right

Call quick_sort([3, 4])

7

Right side pivot

Array: [3, 4], pivot = 4, left = [3], right = []

8

Sort left side of right side

Call quick_sort([3]) returns [3]

9

Combine

Combine [3] + [4] + [] = [3, 4]

10

Combine

Combine [] + [1] + [3, 4] = [1, 3, 4]

11

Combine

Combine [] + [1] + [1, 3, 4] = [1, 1, 3, 4]

12

Combine final

Combine [1, 1, 3, 4] + [5] + [] = [1, 1, 3, 4, 5]

Call	Pivot	Left	Right	Result
[3,1,4,1,5]	5	[3,1,4,1]	[]	[1,1,3,4,5]
[3,1,4,1]	1	[]	[3,4,1]	[1,1,3,4]
[3,4,1]	1	[]	[3,4]	[1,3,4]
[3,4]	4	[3]	[]	[3,4]
[3]	-	-	-	[3]

Why This Works

Step 1: Choosing a pivot

The pivot divides the array into smaller and larger parts, helping to sort by comparison.

Step 2: Splitting the array

Elements less than the pivot go left, others go right, so sorting is easier on smaller parts.

Step 3: Recursion

Calling quick_sort on smaller parts repeats the process until arrays are tiny and sorted.

Step 4: Combining results

Joining sorted left, pivot, and sorted right gives the fully sorted array.

Alternative Approaches

In-place quick sort

ruby

def quick_sort_inplace(arr, low=0, high=nil)
  high ||= arr.length - 1
  if low < high
    p = partition(arr, low, high)
    quick_sort_inplace(arr, low, p - 1)
    quick_sort_inplace(arr, p + 1, high)
  end
  arr
end

def partition(arr, low, high)
  pivot = arr[high]
  i = low - 1
  (low...high).each do |j|
    if arr[j] < pivot
      i += 1
      arr[i], arr[j] = arr[j], arr[i]
    end
  end
  arr[i + 1], arr[high] = arr[high], arr[i + 1]
  i + 1
end

puts quick_sort_inplace([3,1,4,1,5]).inspect

This method sorts the array without extra space but is more complex to understand.

Using Ruby's built-in sort

ruby

arr = [3, 1, 4, 1, 5]
puts arr.sort.inspect

Simplest and fastest for practical use, but does not teach quick sort logic.

Complexity: O(n log n) average, O(n^2) worst time, O(n) space

Time Complexity

Quick sort divides the array and sorts parts recursively, averaging O(n log n) but can degrade to O(n^2) if pivot choices are poor.

Space Complexity

This implementation uses extra arrays for left and right parts, so it needs O(n) space; in-place versions use O(log n) space.

Which Approach is Fastest?

In-place quick sort is faster and uses less memory but is harder to implement; Ruby's built-in sort is optimized and usually fastest in practice.

Approach	Time	Space	Best For
Recursive quick sort with extra arrays	O(n log n) average	O(n)	Learning and clarity
In-place quick sort	O(n log n) average	O(log n)	Performance and memory efficiency
Ruby built-in sort	O(n log n)	O(n)	Practical use and simplicity