How to remove elements from an array followed by the same elements
I have an array. There are two 46
by indices 3
and 7
:
arr = [7, 68, 42, 46, 9, 91, 77, 46, 86, 1]
I was lucky enough to sort this array using the sort selection , but not .sort
. The result should be:
[1, 7, 9, 42, 46, 46, 68, 77, 86, 91]
So, I did this in a file .rb
:
def insertion_sort(arr)
length = arr.size
arr.each_with_index do |number, index|
puts "Now the index is #{index}"
current_minimum = arr.last(length - index).min
puts "Now the current_minimum in last#{length - index} elements is #{current_minimum}"
arr.delete(current_minimum)
arr.insert(index, current_minimum)
end
end
arr = [7, 68, 42, 46, 9, 91, 77, 46, 86, 1]
answer = insertion_sort(arr)
puts answer.to_s
I executed this file, then I got this:
[1, 7, 9, 42, 68, 91, 77, 86, 46]
If I remove one 46
it exits like this:
[1, 7, 9, 42, 46, 68, 77, 86, 91]
My code doesn't work if there are multiple occurrences of any of the same value in the array. When the block each_with_index
got into the index 3
, it deleted everything 46
from the rest of the array.
Can anyone tell me how to fix this?
source to share
To "emulate" this type selection sort
, you can try to iterate over the array using a range starting at 0 as the value at index 0 and with the length of the array as the last element. This range will not accept the value of the last array.
Using each
, you access each value from the created range, then using that "index", you can create a new range, again without taking the last element, but this time one step forward by adding 1 to the current value for a
. Thus, by using each
, you have access to a
and b
from the previously created "parent" and "child" range.
Now you can check if the value for the element with index b
in the array is less than the value for the element with index a
in the array, if this check is true, then create a variable temp
with the value of the element in the array with index b
, then the element in the array at position (index) b
will be the element in the array with position a
, finally, the element in the array in position a
will be equal to the variable temp
created earlier.
Finally, return the array passed as argument.
def insertion_sort(array)
(0...array.length).each do |a|
((a+1)...array.size).each do |b|
if array[b] < array[a]
temp = array[b]
array[b] = array[a]
array[a] = temp
end
end
end
array
end
arr = [7, 68, 42, 46, 9, 91, 77, 46, 86, 1]
p insertion_sort(arr)
# => [1, 7, 9, 42, 46, 46, 68, 77, 86, 91]
As @MarkThomas added, you can "skip" the variable temp
by replacing the array values with a
and b
indexes:
def insertion_sort(array)
(0...array.length).map do |a|
((a+1)...array.size).each do |b|
array[a], array[b] = array[b], array[a] if array[b] < array[a]
end
end
array
end
source to share
Thank you everybody. I have improved my code and it seems to be working well. Here is the code:
def insertion_sort(arr)
length = arr.size
arr.each_with_index do |number, index|
current_minimum = arr.last(length - index).min
current_minimum_index = arr.last(length-index).index(current_minimum) + index # this insure it will delete the right element
arr.delete_at(current_minimum_index)
arr.insert(index, current_minimum)
end
end
arr = [7, 68, 42, 46, 9, 91, 77, 46, 86, 1]
answer = insertion_sort(arr)
puts "---------------------------------------------------------------"
puts "Finally we get #{answer.to_s}"
source to share
To implement Selection Sort in Ruby, you can use Kernel#loop
, with care, to pass obj
in break
to get the correct return value.
arr = [7, 68, 42, 46, 9, 91, 77, 46, 86, 1]
sorted = loop.with_object([]) do |_,obj|
mindex = arr.index arr.min #find index of a minimum
obj << arr.delete_at(mindex) #push this minimum value to obj
break obj if arr.empty?
end
sorted #=> [1, 7, 9, 42, 46, 46, 68, 77, 86, 91]
For details see with_object
.
source to share