Feeling sharp? Sort an array subset in place.

Discussion in 'Ruby' started by Michael Judge, Feb 7, 2006.

  1. Here's the situation: I have an array and I'd like to sort certain
    elements in place -- without touching the others.

    Unsorted array contents:
    3 <-- sort me!
    x
    1 <-- sort me!
    y
    2 <-- sort me!

    Sorted array contents
    1
    x
    2
    y
    3

    See how 1, 2, and 3 played musical chairs? That's exactly what we
    want. It seems like there should be an easy one, two or three-line way
    to do this given an array and a test condition (for identifying
    elements which need sorting.)

    How would you do it?

    (My solution was a dirty cheat, it involved building a hash of {from =>
    to} moves, cloning the original array contents, then changing each
    element one at a time. Blah. There's got to be a sexier way.)
     
    Michael Judge, Feb 7, 2006
    #1
    1. Advertisements

  2. a = [ 3, :x, 1, :y, 2 ]
    f=nil
    tmp = a.partition{ f=!f }
    p tmp.first.sort.zip( tmp.last ).flatten.compact
     
    William James, Feb 7, 2006
    #2
    1. Advertisements

  3. class Array
    def sort_subset!
    els, indices = [], []
    each_with_index{|x,i| (els << x; indices << i) if yield(x) }
    els.sort.each_with_index{|x,i| self[indices] = x}
    end
    end

    a = (0..10).sort_by{rand}
    a # => [1, 8, 2, 10, 3, 0, 5, 4, 9, 7, 6]
    a.sort_subset!{|x| x % 2 == 0} # => [0, 2, 4, 6, 8, 10]
    a # => [1, 0, 2, 4, 3, 6, 5, 8, 9, 7, 10]
    a.sort_subset!{|x| x % 2 == 1} # => [1, 3, 5, 7, 9]
    a # => [1, 0, 2, 4, 3, 6, 5, 8, 7, 9, 10]
     
    Mauricio Fernandez, Feb 7, 2006
    #3
  4. I'd change the app design to not have these arrays. Seriously. It seems
    as if you were storing things together that do not belong together. Why
    do you need that?

    Kind regards

    robert


    irb(main):001:0> a=[3,"y",1,"x",2]
    => [3, "y", 1, "x", 2]
    irb(main):002:0> s=a.select {|x| Integer === x}.sort
    => [1, 2, 3]
    irb(main):003:0> i=0
    => 0
    irb(main):004:0> a.map! {|e| Integer === e ? (r=s; i+=1; r) : e}
    => [1, "y", 2, "x", 3]
     
    Robert Klemme, Feb 7, 2006
    #4
  5. Michael Judge

    Peter Thoman Guest

    I'm definitely *not* feeling sharp (10 AM here and I haven't slept yet)
    but here's my try:

    arr = [3,:x,1,:y,2] # => [3, :x, 1, :y, 2]
    sorted = arr.select { |v| v.class == Fixnum }.sort # => [1, 2, 3]
    arr.map { |v| v.class == Fixnum ? sorted.shift : v } # => [1, :x, 2,
    :y, 3]

    Of course, substitute conditions as appropriate.

    - Peter
     
    Peter Thoman, Feb 7, 2006
    #5
  6. Michael Judge

    Ross Bamford Guest

    I agree with Robert that you should probably think about why your data
    is kept this way. But here's one I've used:

    class Array
    def select_sort!(sort_proc = nil)
    t = []
    map! { |x| if yield x then t << x; nil else x end }
    t.sort!(&sort_proc)
    map! { |x| x or t.shift }
    end
    end

    Which works like:

    a = [2,'a',3,'b','c',1]
    # => [1, "a", 2, "b", "c", 3]
    # => [3, "a", 2, "b", "c", 1]

    But it breaks down if your array contains nil elements beforehand, and
    has that nasty two-block look about it.
     
    Ross Bamford, Feb 7, 2006
    #6
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.