Marat's Notes

Hola. Today let’s take a look to the basic sorting alghoritms implementation in Ruby.

Three sorting methods - Bubble sort, Selection sort and Insertion sort - but keep in mind, they all are not very efficient.

Simple bubble sort - effecient for arrays with small number of elements.

Сomplexity of the algorithm - O(n2).

def bubble_sort(array)
  # set sorted flag to false
  sorted = false

  until sorted
    sorted = true
    for index in 0..(array.length - 2)
      if array[index] > array[index + 1]
        sorted = false
        array[index], array[index + 1] = array[index + 1], array[index]
      end
    end
  end

  return array
end

Selection sort complexity is again O(n2), because we have nested loop here.

Main idea - set first element as minimum index and then iterate over two arrays - with sorted elements and unsorted.

def selection_sort(array)
  for index in 0..(array.length - 2)
    # select the first element as the temp minimum
    minimum_index = index

    # iterate over all other elements to find the min
    for inner_index in index..(array.length - 1)
      if array[inner_index] < array[minimum_index]
        minimum_index = inner_index
      end
    end

    if minimum_index != index
      array[index], array[minimum_index] = array[minimum_index], array[index]
    end
  end

  return array
end

Insertion sort has complexity O(n2) too. But you can found this type of sorting in everyday practice.

def insertion_sort(array)
  for index in 1..(array.length - 1)
    for inner_index in 0..(index - 1)
      if array[inner_index] >= array[index]
        array.insert(inner_index, array[index])
        array.delete_at(index + 1)
      end
    end
  end
   
  return array
end

And a simple benchmark.

require 'benchmark'
count = 100.freeze
Benchmark.bm(10) do |x|
  x.report("Bubble") {  { count.times { bubble_sort(arr) } }
  x.report("Selection" ) { count.times { selection_sort(arr)  } }
  x.report("Insertion")     { count.times { insertion_sort(arr) } }
end

# user     system      total        real
# Bubble       0.000000   0.000000   0.000000 (  0.000153)
# Selection    0.010000   0.000000   0.010000 (  0.000601)
# Insertion    0.000000   0.000000   0.000000 (  0.000547)

Basic sorting algorithms in Ruby