Feeling sharp? Sort an array subset in place.

M

Michael Judge

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.)
 
W

William James

Michael said:
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.)

a = [ 3, :x, 1, :y, 2 ]
f=nil
tmp = a.partition{ f=!f }
p tmp.first.sort.zip( tmp.last ).flatten.compact
 
M

Mauricio Fernandez

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

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]
 
R

Robert Klemme

Michael said:
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?

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]
 
P

Peter Thoman

Michael said:
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?
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
 
R

Ross Bamford

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]
# => [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.
 

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. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,902
Latest member
Elena68X5

Latest Threads

Top