Selection Sort Algorithm in Ruby

1. Introduction

Selection sort is a simple comparison-based sorting algorithm. The primary idea behind selection sort is to divide the input list into two parts: a sorted and an unsorted region. The algorithm repeatedly selects the smallest (or largest, depending on the sorting order) element from the unsorted region and swaps it with the first unsorted element, thus extending the sorted region.

2. Implementation Steps

1. Start with the first element of the list as the minimal.

2. Iterate through the unsorted part of the list to find the minimal (or maximal) element.

3. Swap the found minimum element with the first element of the unsorted part.

4. Move the boundary between the sorted and unsorted regions by one element.

5. Repeat steps 2-4 until the list is sorted.

3. Implementation in Ruby Programming

def selection_sort(arr)
    n = arr.length
    # Outer loop to move the boundary between sorted and unsorted regions
    for i in 0...n
        min_index = i
        # Inner loop to find the minimal element in the unsorted region
        for j in (i+1)...n
            min_index = j if arr[j] < arr[min_index]
        end
        # Swap the found minimum element with the first element in the unsorted region
        arr[i], arr[min_index] = arr[min_index], arr[i]
    end
    arr
end
# Client code
arr = [64, 34, 25, 12, 22, 11, 90]
puts "Original array: #{arr}"
sorted_array = selection_sort(arr)
puts "Sorted array: #{sorted_array}"

Output:

Original array: [64, 34, 25, 12, 22, 11, 90]
Sorted array: [11, 12, 22, 25, 34, 64, 90]

Explanation:

1. Selection sort works by repeatedly finding the minimum element from the unsorted part and placing it at the beginning.

2. We maintain two subarrays in a given array: the first subarray is already sorted, and the second is unsorted.

3. In every iteration, the smallest element from the unsorted subarray is picked and swapped with the leftmost unsorted element, moving the subarray boundaries.

4. This process continues until the entire array becomes sorted.

5. The outer loop in the implementation runs for each element, and the inner loop searches for the minimum element from the unsorted subarray.

6. Once the minimum element is identified, we swap it with the leftmost unsorted element, effectively growing the sorted portion of the array.