Forum: Ruby Feeling sharp? Sort an array subset in place.

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
2b1b2c4661dd593b46ecd24492bc243d?d=identicon&s=25 Michael Judge (bluetrust)
on 2006-02-07 09:29
(Received via mailing list)
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.)
Dd76a12d66f843de5c5f8782668e7127?d=identicon&s=25 Mauricio Fernandez (Guest)
on 2006-02-07 10:18
(Received via mailing list)
On Tue, Feb 07, 2006 at 05:28:21PM +0900, Michael Judge wrote:
> Sorted array contents
>   1
>   x
>   2
>   y
>   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[i]] = 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]
2ee1a7960cc761a6e92efb5000c0f2c9?d=identicon&s=25 William James (Guest)
on 2006-02-07 10:21
(Received via mailing list)
Michael Judge wrote:
> Sorted array contents
>
> 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.)

a = [ 3, :x, 1, :y, 2 ]
f=nil
tmp = a.partition{ f=!f }
p tmp.first.sort.zip( tmp.last ).flatten.compact
5befe95e6648daec3dd5728cd36602d0?d=identicon&s=25 Robert Klemme (Guest)
on 2006-02-07 10:24
(Received via mailing list)
Michael Judge wrote:
> Sorted array contents
>
> How would you do it?

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]; i+=1; r) : e}
=> [1, "y", 2, "x", 3]
F48798d589f12df278a6aaf82b581179?d=identicon&s=25 Peter Thoman (Guest)
on 2006-02-07 10:30
(Received via mailing list)
Michael Judge wrote:

>Sorted array contents
>
>How would you do it?
>
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
A9b6a93b860020caf9d2d1d58c32478f?d=identicon&s=25 Ross Bamford (Guest)
on 2006-02-07 15:13
(Received via mailing list)
On Tue, 2006-02-07 at 17:28 +0900, Michael Judge wrote:
> Here's the situation: I have an array and I'd like to sort certain
> elements in place -- without touching the others.

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]
>> # => [2, "a", 3, "b", "c", 1]
a.select_sort! { |x| x.is_a? Fixnum }
>> p a
# => [1, "a", 2, "b", "c", 3]
a.select_sort!(lambda { |x,y| y <=> x }) { |x| x.is_a? Fixnum }
>> p a
# => [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.
This topic is locked and can not be replied to.