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.

Recommended Posts

Make bubble sort and selection sort in Ruby
Implement the algorithm in Ruby: Day 2 -Bubble sort-
Write keys and values in Ruby
Make Ruby segfault in two lines
Summary of hashes and symbols in Ruby
[Ruby] Classification and usage of loops in Ruby
Difference between "|| =" and "instance_variable_defined?" In Ruby memoization
[Understanding] Differences between hashes and arrays in Ruby
java selection sort
Heavy in Ruby! ??
Ruby and Gem
About the difference between classes and instances in Ruby
In fact, Ruby distinguishes between line breaks and whitespace.
[Ruby] Difficulty in refactoring logical operators (accuracy and readability)
How to handle TSV files and CSV files in Ruby
Get location information in Rails and sort in ascending order
Handling of date and time in Ruby. Use Date and Time properly.
Ruby classes and instances
Output triangle in Ruby
Variable type in ruby
Fast popcount in Ruby
Make your own simple server in Java and understand HTTP
AtCoder dwango Programming Contest B in Ruby, Perl and Java
Sorting in ascending order in Java (bubble sort: simple exchange algorithm)