Insertion Sort Algorithm in Ruby

1. Introduction

Insertion sort is a straightforward and intuitive comparison-based sorting algorithm. The main idea behind insertion sort is to build the final sorted array one item at a time. It works similarly to how you might sort a hand of playing cards: by repeatedly taking one card from the input data and moving it to its correct position within the already-sorted set of cards.

2. Implementation Steps

1. Start from the second element (assume the first element is sorted).

2. Compare the current element with the previous element.

3. If the current element is smaller than the previous, compare it with the elements before. Move the greater elements one position up to make space for the swapped element.

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

3. Implementation in Ruby Programming

def insertion_sort(arr)
    for i in 1..(arr.length - 1)
        key = arr[i]
        j = i - 1
        # Move elements of arr[0..i-1] that are greater than key to one position ahead of their current position
        while j >= 0 && key < arr[j]
            arr[j + 1] = arr[j]
            j -= 1
        end
        arr[j + 1] = key
    end
    arr
end
# Client code
arr = [64, 34, 25, 12, 22, 11, 90]
puts "Original array: #{arr}"
sorted_array = insertion_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. Insertion sort works by considering one element at a time and ensuring that all the elements before it are in their correct positions.

2. Starting from the second element, we compare it with the previous ones. If the current element is smaller, we continue comparing it with the elements before until we reach a number smaller or the start of the array. This ensures that the first part of the array is always sorted.

3. As we progress with the iterations, more significant parts of the array become sorted.

4. The inner loop shifts each element to its correct position within the sorted part of the array.

5. Once all iterations are complete, the entire array is sorted.