Make bubble sort and selection sort in Ruby

Purpose

Let's actually write the code and summarize the sorting algorithm. I will try the language in Ruby.

About sorting

Sorting is to 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 you perform one round of processing for a sequence, the smallest number will be in the first of the array. It can be sorted 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 the array array as length (1st line) ・ (Length -1) The replacement is completed in the round (2nd line) ・ In the nth round, compare (length --n --1) times and replace (3rd line). ・ If the value on the left is larger than the value on the right, replace it (lines 4 to 7). The number of magnitude comparisons is (length -1) + (length -2) + ・ ・ ・ + 1 = (length) ^ 2/2.

Selection sort

The selection sort repeats the operation of "searching for the minimum value in the sequence and replacing it with the leftmost number".

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 minimum index number, search for it, and then replace it. Same as bubble sort, the number of size comparisons is (length) ^ 2/2.

Postscript

Next, I will also summarize insertion sort, heapsort, merge sort, quicksort, and bucket sort.