[Ruby] Create bubble sort and selection sort with Ruby

1 minute read

Purpose

Let’s try to put together a sort algorithm by actually writing code. Let’s try the language with Ruby.

About sorting

To sort, sort the numbers given as input in ascending order.

Bubble sort

Bubble sort repeats the operation of “comparing and swapping two adjacent numbers from right to left in the sequence”. If the process is repeated once for a sequence of numbers, the smallest number will be in the first position of the array. It is possible to sort by going around the number of elements.

bubble.rb


def bubble_sort(array)
  length = array.length
  (length-1).times do |round|
    (length-1-round).times do |n|
      if array[length-n-1] <array[length-n-2]
        smaller = array[length-n-1]
        array[length-n-1] = array[length-n-2]
        array[length-n-2] = smaller
      end
    end
  end
  array
end

array = [2, 3, 13, 7, 8, 9, 11, 1, 5]
bubble_sort(array) #=> [1, 2, 3, 5, 7, 8, 9, 11, 13]

Contents of bubble sort function ・Get the length of array array by length (first line) ・(Length-1) round ends swapping (second line)

  • In the nth round, (length-n-1) times are compared and the process of swapping is performed (3rd line) ・If the value on the left is greater than the value on the right, swap them (lines 4-7). The number of comparisons is (length-1) + (length-2) + … + 1 = (length)^2 / 2.

    Selection sort

    For selective sorting, the operation of “searching for the minimum value in the sequence of numbers and replacing it with the leftmost number” is repeated.

selection.rb


def selection_sort(array)
  length = array.length
  (length-1).times do |round|
    min = round + 1
    round.upto(length-1) do |n|
      if array[n] <array[min]
        min = n
      end
    end
    min_number = array[min]
    array[min] = array[round]
    array[round] = min_number
  end
  array
end

Get the smallest index number and replace it after searching. Same as bubble sort, the number of comparisons is (length)^2/2.

Postscript

Next, I’ll summarize insert sort, heap sort, merge sort, quick sort, and bucket sort.

Tags:

Updated: