Insertion Sort Algorithm in Ruby
Insertion sort algorithm was developed using comparison algorithm. This algorithm splits the array into two sub-arrays namely sorted
and un-sorted sub arrays. Initially the sorted sub array contains only one element in other words the first item of a main array was considered
as a sorted array and the rest of the items was considered as a un-sorted array. Take a leftmost element in a un-sorted array to
find the suitable place in the sorted array and finally place the number in a suitable place holder till there is no elements exist
in the un-sorted sub array. Insertion sort is an easiest way of sorting technique, but it's not an efficient on large data sets.
Moreover, Insertion sort is more efficient and advanced algorithm than the Quick sort, Heap sort or merge sort.
Time Complexity
- Best complexity: n
- Average complexity: n^2
- Worst complexity: n^2
Insertion Sort Implementation in Ruby
Ruby Input Screen
class InsertionSortExample
def insertionSort(arr)
for i in 1...arr.length do
temp = arr[i]
holePosition = i
while(holePosition > 0 && arr[holePosition - 1] > temp)
arr[holePosition] = arr[holePosition - 1]
holePosition = holePosition - 1
end
arr[holePosition] = temp
end
end
def printArray(arr)
for i in 0...arr.length do
print(arr[i].to_s + " ")
end
puts("")
end
end
obj = InsertionSortExample.new
arr = [15, 3, 12, 6, -9, 9, 0]
print("Before Sorting: ")
obj.printArray(arr)
obj.insertionSort(arr)
print("After Sorting: ")
obj.printArray(arr)
Ruby Output Screen
Before Sorting: 15 3 12 6 -9 9 0
After Sorting: -9 0 3 6 9 12 15
Insertion sort implementation steps:
Let's take the input array as { 15, 3, 12, 6, -9, 9, 0 } and we can see how the Insertion sort is sorting the array.
- Split the array into two sub arrays namely sorted and un-sorted arrays,
- The first array was partitioned from a main array with only one element. It contains only the 0th indexed element, in other words the first item of a main array and it's always considered as a sorted array.
- The second array was partitioned from a main array and it has the remaining element except the first element (i.e. index position 0 to length - 1) and it's always considered as a un-sorted array.
- Transfer the leftmost item in a un-sorted array to a temporary variable and mark the position as empty and attach this empty position to the end of the sorted array
- Compare the temporary variable with an element in a sorted array from the right to left direction.
- Shift the position by one on the right hand side (i.e. shift the value to the empty place holder)
immediately only if the element is greater than the temporary variable and mark the place as an empty
and continue the comparison process till the temporary variable is greater than the items in the sorted item.
- Place the value of the temporary variable to the recently marked empty place holder.
- Apply the steps 2 and 3 until there is no more elements in un-sorted array.
Insertion Sort Implementation in Ruby with explanation
Ruby Input Screen
class InsertionSortExample
def insertionSort(arr)
# Un-sorted array from position 1 to length -1
for i in 1...arr.length do
# Take the left most item in an un-sorted array to temp variable
temp = arr[i]
# Mark the left most position as empty or hole
holePosition = i
# Traverse the sorted array from right to left direction
# Move the item from the sorted array to the empty position (i.e. holePosition) only if the temp variable is less then
# Mark the current item's position as empty by decrementing the value by one
while(holePosition > 0 && arr[holePosition - 1] > temp)
arr[holePosition] = arr[holePosition - 1]
holePosition = holePosition - 1
end
# Once the comparison done, move the value in temp variable to the lastly marked empty position
arr[holePosition] = temp
end
end
def printArray(arr)
# Loop the item and print each item in the console with white space seperated
for i in 0...arr.length do
print(arr[i].to_s + " ")
end
puts("")
end
end
obj = InsertionSortExample.new
arr = [15, 3, 12, 6, -9, 9, 0]
print("Before Sorting: ")
obj.printArray(arr)
obj.insertionSort(arr)
print("After Sorting: ")
obj.printArray(arr)
Ruby Output Screen
Before Sorting: 15 3 12 6 -9 9 0
After Sorting: -9 0 3 6 9 12 15
BBMINFO
