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-
[Ruby] then keyword and case in
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
java bubble sort
[Understanding] Differences between hashes and arrays in Ruby
Class in Ruby
Put CSV files containing "'" and "" "in MySQL in Ruby 2.3
java selection sort
Heavy in Ruby! ??
Ruby and Gem
Just put `clang 12.0.0` in macOS` Catalina` and put `ruby 3.0.0`
Differences between Ruby syntax error statements in Ruby and binary
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.
[java] sort in list
Make Blackjack in Java
[Ruby] Classes and instances
Symbols and Destructive Ruby
About eval in Ruby
[Ruby] Big Decimal and DECIMAL
Ruby classes and instances
Ruby inheritance and delegation
Ruby variables and methods
Output triangle in Ruby
Variable type in ruby
Fast popcount in Ruby
Multi-stage selection (Ruby Ractor)
[Java] Make variables in extended for statement and for Each statement immutable
Solving in Ruby, Perl and Java AtCoder ABC 113 C Reference
Math Girls Secret Note 104th implemented in Ruby and C
About the difference between "(double quotation)" and "single quotation" 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)
Handling of line beginning and line ending in regular expressions in Ruby
Write DiscordBot to Spreadsheets Write in Ruby and run with Docker