Sorting in Ruby with each method

Question

I have the code below:

def shuffle arr
  shuffled = []
  while arr.length > 0
    randNum = rand(arr.length)
    idx = 0
    unshuf = []
    arr.each do |item|
      if idx == randNum
        shuffled.push item
      else
        unshuf.push item
      end
      idx = idx + 1
    end
    arr = unshuf
  end
  return shuffled
end

puts(shuffle([ 11, 12, 13]))

I am trying to understand the status of the array unshuf as the method shuffle is called. The array unshuf is being reset to an empty array each time before method each is called. Under such implementation, how are the numbers pushed into unshuf retained for the next round of if condition?

Dude, not that I'm the biggest expert on Earth, but did you write that code yourself? While I suppose not, it still needs some serious refactoring. — Boris Stitnicky
– Boris Stitnicky, Commented Dec 30, 2012 at 22:29
I don't know whether the book is perhaps from the time when #shuffle method still didn't exist in the Array class :-) — Boris Stitnicky
– Boris Stitnicky, Commented Dec 30, 2012 at 22:34
It's just for exercise purposes. Yes, of course the sort method would be simpler! :) — KMcA
– KMcA, Commented Dec 30, 2012 at 22:36
Yes unshuf = [] repoints the label 'unshuf' at a new, empty, array. it has no effect on the object formerly referenced by unshuf — Frederick Cheung
– Frederick Cheung, Commented Dec 30, 2012 at 22:57

steenslag · Accepted Answer · 2012-12-31 11:47:07Z

3

The code works like this:

Create an empty array where the end result will be stored.
Get a random number between 0 and the initial array's seize.
Initialize an indexcounter to zero.
Create an unshuffled empty array.
Loop through the initial array
- pushing every item to the unshuffled array,
- except the one where the indexcounter == random number, that goes to the result array
- while keeping an indexcounter.
Rename the unshuffled array to the initial array.
Repeat from step 2 until the initial array is empty.

Needless to say, this is clumsy. Also it is written in a very unRuby way,keeping a manual index and using variable names like randNum. This does about the same:

def shuffle(arr)
  dup = arr.dup
  arr.size.times.map do # actually arr.map would work
    dup.slice!(rand(dup.size))
  end
end

But as mentioned by others, [1,2,3].shuffle is standard Ruby.

edited Dec 31, 2012 at 11:47

answered Dec 30, 2012 at 23:24

steenslag

80.2k16 gold badges144 silver badges174 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Boris Stitnicky Over a year ago

Great. You actually brought yourself to explain this horrible thing step by step ^_^

Boris Stitnicky · Accepted Answer · 2012-12-30 23:01:13Z

2

I don't know where did you get the above code. Ruby Array#shuffle method calls #shuffle! native method rb_ary_shuffle_bang, which goes as follows:

static VALUE
rb_ary_shuffle_bang(int argc, VALUE *argv, VALUE ary)
{
  VALUE *ptr, opts, *snap_ptr, randgen = rb_cRandom;
  long i, snap_len;

  if (OPTHASH_GIVEN_P(opts)) {
    randgen = rb_hash_lookup2(opts, sym_random, randgen);
  }
  if (argc > 0) {
    rb_raise(rb_eArgError, "wrong number of arguments (%d for 0)", argc);
  }
  rb_ary_modify(ary);
  i = RARRAY_LEN(ary);
  ptr = RARRAY_PTR(ary);
  snap_len = i;
  snap_ptr = ptr;
  while (i) {
    long j = RAND_UPTO(i);
    VALUE tmp;
    if (snap_len != RARRAY_LEN(ary) || snap_ptr != RARRAY_PTR(ary)) {
      rb_raise(rb_eRuntimeError, "modified during shuffle");
    }
    tmp = ptr[--i];
    ptr[i] = ptr[j];
    ptr[j] = tmp;
  }
  return ary;
}

Here you can see the correct approach to shuffling. Ignoring the top half of the above code, notice just while loop, which goes through the array from the top down, and always picks an element from the section below the index i at random and moves it to the current position of i, continuing with decremented i. Its complexity is O(n) in n = length of array, as it should be for shuffling.

Whereas, the code from your book works quite differently: It always picks one element (rand( arr.length )) from the array, and then iterates over the array to see when the element with that index is encountered, giving complexity O(n**2/2). Your code also gives a good example of using #push method, although #<< would have sufficed, as only one element is pushed each time. Your code gives bad example of manually maintaining index idx inside each loop. #each_with_index method should have been used instead. Of course, outside demonstration purposes, the internal loop should be dropped altogether and an approach similar to the native #shuffle method should be used.

edited Dec 30, 2012 at 23:01

answered Dec 30, 2012 at 22:33

Boris Stitnicky

12.6k5 gold badges61 silver badges75 bronze badges

2 Comments

KMcA Over a year ago

Boris, unfortunately that doesn't really answer my question.

Boris Stitnicky Over a year ago

I was still editing the answer then. If now, after the save, the answer does not answer your question, than you need to ask something more specific than "I'd like to understand the concept".

user1852994 · Accepted Answer · 2012-12-31 00:13:33Z

def shuffle arr
  shuffled = []

  while arr.length > 0
    randNum = rand(arr.length)

    idx = 0
    unshuf = []

    print '--- arr='; p arr # <--------
    arr.each do |item|
      if idx == randNum
        shuffled.push item
      else
        unshuf.push item
      end
      print 'shuffled='; print shuffled; print ', unshuf='; p unshuf # <--------
      idx = idx + 1
    end

    arr = unshuf
  end

  return shuffled
end

p shuffle([ 11, 12, 13, 14, 15])

Execution :

$ ruby -w t.rb 
--- arr=[11, 12, 13, 14, 15]
shuffled=[], unshuf=[11]
shuffled=[], unshuf=[11, 12]
shuffled=[13], unshuf=[11, 12]
shuffled=[13], unshuf=[11, 12, 14]
shuffled=[13], unshuf=[11, 12, 14, 15]
--- arr=[11, 12, 14, 15]
shuffled=[13, 11], unshuf=[]
shuffled=[13, 11], unshuf=[12]
shuffled=[13, 11], unshuf=[12, 14]
shuffled=[13, 11], unshuf=[12, 14, 15]
--- arr=[12, 14, 15]
shuffled=[13, 11, 12], unshuf=[]
shuffled=[13, 11, 12], unshuf=[14]
shuffled=[13, 11, 12], unshuf=[14, 15]
--- arr=[14, 15]
shuffled=[13, 11, 12, 14], unshuf=[]
shuffled=[13, 11, 12, 14], unshuf=[15]
--- arr=[15]
shuffled=[13, 11, 12, 14, 15], unshuf=[]
[13, 11, 12, 14, 15]

Explanation : the content of arr is randomly distributed between shuffled and unshuf. Then unshuf replaces arr and, if there was something in unshuf, the while loop redistributes randomly a little in shuffle, a little in unshuf. And so on until unshuf is empty. So shuffled is progressively filled with elements randomly taken from the parameter arr initially given to the method shuffle, but arr is also progressively emptied by keeping only unshuf elements in arr = unshuf. Of course after having been moved into arr, unshuf must be reset to an empty array to receive the new distribution, while shuffled must keep growing. Hope it's clear.

Perfect, thank you. Silly mistake in that I wasn't immediately seeing the implication of arr = unshuf.

Collectives™ on Stack Overflow

Sorting in Ruby with each method

3 Answers 3

1 Comment

2 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

2 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related