Ruby Program to Perform Selection Sort on an Array

A Ruby program for selection sort uses nested loops to find the smallest element and swap it with the current position, like for i in 0...arr.length; min_idx = i; for j in i+1...arr.length; min_idx = j if arr[j] < arr[min_idx]; end; arr[i], arr[min_idx] = arr[min_idx], arr[i]; end.

Examples

Input[3, 1, 4, 2]

Output[1, 2, 3, 4]

Input[10, 9, 8, 7]

Output[7, 8, 9, 10]

Input[]

Output[]

How to Think About It

To sort an array using selection sort, think of repeatedly picking the smallest number from the unsorted part and moving it to the front. You start at the first position, find the smallest element in the rest of the array, and swap it with the current position. Repeat this for each position until the whole array is sorted.

Algorithm

1

Start from the first element of the array.

2

Find the smallest element in the unsorted part of the array.

3

Swap the smallest element with the element at the current position.

4

Move to the next position and repeat until the entire array is sorted.

Code

ruby

def selection_sort(arr)
  n = arr.length
  for i in 0...n
    min_idx = i
    for j in (i + 1)...n
      min_idx = j if arr[j] < arr[min_idx]
    end
    arr[i], arr[min_idx] = arr[min_idx], arr[i]
  end
  arr
end

puts selection_sort([3, 1, 4, 2]).inspect

Output

[1, 2, 3, 4]

Dry Run

Let's trace [3, 1, 4, 2] through the code

1

Initial array

[3, 1, 4, 2]

2

Find smallest from index 0

Smallest is 1 at index 1, swap with 3

3

Array after first swap

[1, 3, 4, 2]

4

Find smallest from index 1

Smallest is 2 at index 3, swap with 3

5

Array after second swap

[1, 2, 4, 3]

6

Find smallest from index 2

Smallest is 3 at index 3, swap with 4

7

Array after third swap

[1, 2, 3, 4]

8

Index 3 is last, done

[1, 2, 3, 4]

Iteration	Current Index (i)	Min Index (min_idx)	Array State
1	0	1	[1, 3, 4, 2]
2	1	3	[1, 2, 4, 3]
3	2	3	[1, 2, 3, 4]

Why This Works

Step 1: Find minimum element

The inner loop finds the smallest element in the unsorted part by comparing each element with the current minimum using <.

Step 2: Swap elements

After finding the smallest element, it swaps places with the element at the current position using parallel assignment arr[i], arr[min_idx] = arr[min_idx], arr[i].

Step 3: Repeat for all positions

The outer loop moves the current position forward, repeating the process until the entire array is sorted.

Alternative Approaches

Using Ruby's built-in sort method

ruby

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

This is much simpler and faster but does not show how selection sort works.

Recursive selection sort

ruby

def recursive_selection_sort(arr, start=0)
  return arr if start >= arr.length - 1
  min_idx = start
  (start + 1...arr.length).each do |i|
    min_idx = i if arr[i] < arr[min_idx]
  end
  arr[start], arr[min_idx] = arr[min_idx], arr[start]
  recursive_selection_sort(arr, start + 1)
end

puts recursive_selection_sort([3, 1, 4, 2]).inspect

Uses recursion instead of loops, which can be harder to understand but is a different approach.

Complexity: O(n^2) time, O(1) space

Time Complexity

Selection sort uses two nested loops each running up to n times, so it takes about n squared steps, or O(n^2).

Space Complexity

It sorts the array in place without extra memory, so space complexity is O(1).

Which Approach is Fastest?

Using Ruby's built-in sort is fastest and recommended for real use, but selection sort helps understand sorting basics.

Approach	Time	Space	Best For
Selection Sort	O(n^2)	O(1)	Learning sorting basics
Recursive Selection Sort	O(n^2)	O(n) due to recursion stack	Understanding recursion
Ruby Built-in sort	O(n log n)	O(n)	Practical sorting tasks