Implement the algorithm in Ruby: Day 2 -Bubble sort-

The second day I was wondering whether to do it honestly. Click here for the first day <Implementing the algorithm in Ruby: Day 1 -Euclidean algorithm->

Implement bubble sort today

What is bubble sort?

Algorithm that compares adjacent numbers and exchanges according to conditions This time, we will implement by comparing from the right side of the sequence and arranging in ascending order.

bubbleSort.rb

code

#Bubble sort

def bubbleSort(num)
  len = num.length                           #Stores the length of a sequence
  len.times do |i|                           #Loop for the length of the sequence
    (len - 1).downto(i+1) do |j|             #Sequence length-1~i+Loop to 1
      if num[j]  < num[j-1]                  #Compare the innermost part of the sequence with the one before it.
        num[j], num[j-1] = num[j-1], num[j]  #If the number in the back is smaller, replace it
      end
    end
    puts "#{i+1}Time;#{num.join(" ")}"       #output
  end
end

puts "Enter numbers"
number = gets.split().map(&:to_i)             #Store the entered number in an array as an int type
bubbleSort(number)                            #Run

Run

Enter numbers
5 9 3 1 2 8 4 7 6
1st time; 1 5 9 3 2 4 8 6 7
2nd time; 1 2 5 9 3 4 6 8 7
3rd time; 1 2 3 5 9 4 6 7 8
4th time; 1 2 3 4 5 9 6 7 8
5th time; 1 2 3 4 5 6 9 7 8
6th time; 1 2 3 4 5 6 7 9 8
7th time; 1 2 3 4 5 6 7 8 9
8th time; 1 2 3 4 5 6 7 8 9
9th time; 1 2 3 4 5 6 7 8 9

Maybe this is right ... This time from the back of the array. In short, I sorted in order from the numbers I put in later. Therefore, instead of repeating with times as usual, I tried using downto.

downto method

downto(min) {|n| ... } -> self Repeat the block, decrementing from self to min by 1. If self <min, do nothing. .. [Reference: Ruby 2.7.0 Reference Manual]

Finally

It seems that various implementations can be made by changing the conditions, and it was fun to write. Is it unique to Ruby to replace the elements of an array? I felt like it was, but I couldn't compare it because I didn't understand other languages.

I feel that it will be possible to speed up execution and simplify the code under the same conditions, so please lend me the wisdom of all the experts.

Tomorrow we will implement a binary search.

Recommended Posts

Implement the algorithm in Ruby: Day 2 -Bubble sort-
Implement the algorithm in Ruby: Day 1 -Euclidean algorithm-
Implement the algorithm in Ruby: Day 3 -Binary search-
Make bubble sort and selection sort in Ruby
Sorting in ascending order in Java (bubble sort: simple exchange algorithm)
Try to implement Yubaba in Ruby
Implement a gRPC client in Ruby
Sort by multiple fields in the class
Implemented basic search / sort algorithm in Java
The ruby version is managed in the .rbenv / version file
[Ruby] Code to display the day of the week
Implement the Like feature in Ajax with Rails.
How Docker works ~ Implement the container in 60 lines
How to build the simplest blockchain in Ruby
I want to get the value in Ruby
java bubble sort
Class in Ruby
Heavy in Ruby! ??
Count the number of occurrences of a string in Ruby
[Ruby] The role of subscripts in learning elements in arrays
About the difference between classes and instances in Ruby
[Ruby / Rails] Set a unique (unique) value in the class
Get the URL of the HTTP redirect destination in Ruby