CODEWITHSUNDEEP
ruby
Xullnn
Xullnn

Reputation: 405

How to delete elements from an array that are followed by the same elements

I have an array. There are two 46s at indices 3 and 7:

arr = [7, 68, 42, 46, 9, 91, 77, 46, 86, 1]

I got a mission to sort this array using selection sort, but not .sort. The result should be:

[1, 7, 9, 42, 46, 46, 68, 77, 86, 91]

So, I did this in a .rb file:

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 got this:

[1, 7, 9, 42, 68, 91, 77, 86, 46]

If I delete one 46, it came out with this:

[1, 7, 9, 42, 46, 68, 77, 86, 91]

My code does not work when there are multiple occurrences of some single value in the array. When the each_with_index block went to index 3, it deleted all 46s from the rest of the array.

Could anyone tell me how to correct this?

Upvotes: 3

Views: 146

Answers (3)

Sagar Pandya
Sagar Pandya

Reputation: 9497

To implement a Selection Sort in Ruby you can use Kernel#loop, being careful to pass obj to break in order 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]

See with_object for more info.

Upvotes: 0

Sebasti&#225;n Palma
Sebasti&#225;n Palma

Reputation: 33420

To "emulate" this kind of selection sort you could try iterating over an array using a range starting from 0 as the value with index 0 and with the length of the array as last element. This range won't take the last array value.

Using each you get access to 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 ahead, that's adding 1 to the current value for a. This way again, using each you have access to a and b, from the "parent" and "child" range created before.

Now you can check if the value for the element with index b in the array is minor than the value for the element with index a in the array, if this validation is true then create a temp variable with the value of the element in the array with index b, then the element in the array at position (index) b will be equal to the element in the array with the position a, finally the element in the array at position a, will be equal to the temp variable created before.

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 added @MarkThomas, you can "skip" the temp variable by swapping 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

Upvotes: 4

Xullnn
Xullnn

Reputation: 405

Thanks all of you. I improved my code and it seems work well.Here's 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}"

Upvotes: 0

Related Questions