Forum: Ruby How to sort array ascending, except zero ?

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.
01bb0d480d4d2777661a15165b842590?d=identicon&s=25 Paganoni (Guest)
on 2009-06-08 10:40
(Received via mailing list)
Hello, I need to sort
[1,4,2,0,8,9] to [1,2,4,8,9,0]

A simple ascending sort but with the zero values to the end

I really don't see how to do

Thanks for your help
5772c599ccab3081e0fffb1d54f3b6de?d=identicon&s=25 Andrew Timberlake (andrewtimberlake)
on 2009-06-08 10:50
(Received via mailing list)
On Mon, Jun 8, 2009 at 10:40 AM, Paganoni<noway@fakenullvoid.com> wrote:
> Hello, I need to sort
> [1,4,2,0,8,9] to [1,2,4,8,9,0]
>
> A simple ascending sort but with the zero values to the end
>
> I really don't see how to do
>
> Thanks for your help
>

Maybe not the most elegant solution but it gets the job done:
arr = [1,4,2,0,8,9]
arr = (arr - [0]).sort << 0

Otherwise you want to override <=> on Fixnum

Andrew Timberlake
http://ramblingsonrails.com

http://MyMvelope.com - The SIMPLE way to manage your savings
Ae16cb4f6d78e485b04ce1e821592ae5?d=identicon&s=25 Martin DeMello (Guest)
on 2009-06-08 11:03
(Received via mailing list)
On Mon, Jun 8, 2009 at 2:10 PM, Paganoni<noway@fakenullvoid.com> wrote:
> Hello, I need to sort
> [1,4,2,0,8,9] to [1,2,4,8,9,0]
>
> A simple ascending sort but with the zero values to the end

max = a.max + 1
# or max = 2 ** 31, say, if you don't want the extra pass
# but sorting is O(n log n) and max is O(n) so it doesn't really matter

a.sort_by {|x| x.zero? ? max : x}

martin
E0d864d9677f3c1482a20152b7cac0e2?d=identicon&s=25 Robert Klemme (Guest)
on 2009-06-08 11:21
(Received via mailing list)
2009/6/8 Andrew Timberlake <andrew@andrewtimberlake.com>:
> On Mon, Jun 8, 2009 at 10:40 AM, Paganoni<noway@fakenullvoid.com> wrote:
>> Hello, I need to sort
>> [1,4,2,0,8,9] to [1,2,4,8,9,0]
>>
>> A simple ascending sort but with the zero values to the end

> Otherwise you want to override <=> on Fixnum

Definitively not!  Changing the default Fixnum ordering is dangerous
because it will likely break a lot of other code and it is
superfluous, too.  There are better tools for that, i.e. defining the
sort order in the place where it is needed (see Martin's solution).

Kind regards

robert
E0d864d9677f3c1482a20152b7cac0e2?d=identicon&s=25 Robert Klemme (Guest)
on 2009-06-08 11:28
(Received via mailing list)
2009/6/8 Martin DeMello <martindemello@gmail.com>:
> On Mon, Jun 8, 2009 at 2:10 PM, Paganoni<noway@fakenullvoid.com> wrote:
>> Hello, I need to sort
>> [1,4,2,0,8,9] to [1,2,4,8,9,0]
>>
>> A simple ascending sort but with the zero values to the end
>
> max = a.max + 1
> # or max = 2 ** 31, say, if you don't want the extra pass
> # but sorting is O(n log n) and max is O(n) so it doesn't really matter

Still traversing the array twice just to get the max beforehand does
not /feel/ right.  I'd rather use your "large constant" - maybe even
with a _really_ large number: :-)

irb(main):020:0> a = [1,4,2,0,8,9]
=> [1, 4, 2, 0, 8, 9]
irb(main):021:0> INF = 1.0 / 0.0
=> Infinity
irb(main):022:0> a.sort_by {|x| x == 0 ? INF : x}
=> [1, 2, 4, 8, 9, 0]

Another good alternative is to use the block form of #sort:

irb(main):023:0> a.sort do |x,y|
irb(main):024:1*   case
irb(main):025:2*   when x == 0 then  1
irb(main):026:2>   when y == 0 then -1
irb(main):027:2>   else             x <=> y
irb(main):028:2>   end
irb(main):029:1> end
=> [1, 2, 4, 8, 9, 0]

Kind regards

robert
Ae16cb4f6d78e485b04ce1e821592ae5?d=identicon&s=25 Martin DeMello (Guest)
on 2009-06-08 11:33
(Received via mailing list)
On Mon, Jun 8, 2009 at 2:57 PM, Robert
Klemme<shortcutter@googlemail.com> wrote:
> Still traversing the array twice just to get the max beforehand does
> not /feel/ right.  I'd rather use your "large constant" - maybe even
> with a _really_ large number: :-)
>
> irb(main):020:0> a = [1,4,2,0,8,9]
> => [1, 4, 2, 0, 8, 9]
> irb(main):021:0> INF = 1.0 / 0.0
> => Infinity

Ah yes, forgot you could compare floats with fixnums :)

martin
C06869c119472a139eb163b72040b0db?d=identicon&s=25 Bertram Scharpf (Guest)
on 2009-06-08 12:34
(Received via mailing list)
Hi,

Am Montag, 08. Jun 2009, 17:40:06 +0900 schrieb Paganoni:
> Hello, I need to sort
> [1,4,2,0,8,9] to [1,2,4,8,9,0]
> A simple ascending sort but with the zero values to the end

I don't know what you want to do further with the sorted values
but maybe this is an approach to consider:

  s = a.map { |x| x.nonzero? }
  s.compact!
  s.sort!

or

  s, z = a.map { |x| x.nonzero? }.partition { |x| x }
  s.sort!
  puts z.length

Bertram


P.S.: Still, my opinion is that there should be an equivalent
String#notempty?  to  Numeric#nonzero? !
2f4d4f9c35ea851bffb9a9cc2e086365?d=identicon&s=25 Harry Kakueki (Guest)
on 2009-06-08 13:00
(Received via mailing list)
On Mon, Jun 8, 2009 at 5:40 PM, Paganoni<noway@fakenullvoid.com> wrote:
> Hello, I need to sort
> [1,4,2,0,8,9] to [1,2,4,8,9,0]
>
> A simple ascending sort but with the zero values to the end
>
> I really don't see how to do
>
> Thanks for your help
>
>



tmp = arr.partition{|x| x != 0 }
(tmp[0].sort + tmp[1])

Harry
2f4d4f9c35ea851bffb9a9cc2e086365?d=identicon&s=25 Harry Kakueki (Guest)
on 2009-06-08 13:08
(Received via mailing list)
On Mon, Jun 8, 2009 at 7:59 PM, Harry Kakueki<list.push@gmail.com>
wrote:
>>
>
Oops!

tmp = arr.partition{|x| x != 0 }
p (tmp[0].sort + tmp[1])

The second line should be like this, of course.

Harry
01bb0d480d4d2777661a15165b842590?d=identicon&s=25 Paganoni (Guest)
on 2009-06-08 15:11
(Received via mailing list)
le 08/06/2009 10:38, Paganoni nous a dit:
> Hello, I need to sort
> [1,4,2,0,8,9] to [1,2,4,8,9,0]
>
> A simple ascending sort but with the zero values to the end
>
> I really don't see how to do
>
> Thanks for your help

I forgot to mention that the array can contain several 0 values not only
one.
64aa4b69fdd7127e6f3ee16ae065a620?d=identicon&s=25 Giampiero Zanchi (giampiz)
on 2009-06-08 15:44
ciao
if you are sure not to have negative numbers in your input, then you can
map each number to its negative, sort descending and then map again to
positive
64aa4b69fdd7127e6f3ee16ae065a620?d=identicon&s=25 Giampiero Zanchi (giampiz)
on 2009-06-08 15:49
Giampiero Zanchi wrote:
> ciao
> if you are sure not to have negative numbers in your input, then you can
> map each number to its negative, sort descending and then map again to
> positive

sorry; it cannot work, of course
Ae16cb4f6d78e485b04ce1e821592ae5?d=identicon&s=25 Martin DeMello (Guest)
on 2009-06-08 15:56
(Received via mailing list)
On Mon, Jun 8, 2009 at 6:40 PM, Paganoni<noway@fakenullvoid.com> wrote:
> le 08/06/2009 10:38, Paganoni nous a dit:
>>
> I forgot to mention that the array can contain several 0 values not only
> one.

My solution took that into account. Give it a try.

martin
D7891452fffe9e1e55f9ff18b7e87845?d=identicon&s=25 andrea (Guest)
on 2009-06-08 17:10
(Received via mailing list)
Robert Klemme <shortcutter@googlemail.com> wrote:

> Another good alternative is to use the block form of #sort:
>
> irb(main):023:0> a.sort do |x,y|
> irb(main):024:1*   case
> irb(main):025:2*   when x == 0 then  1
> irb(main):026:2>   when y == 0 then -1
> irb(main):027:2>   else             x <=> y
> irb(main):028:2>   end
> irb(main):029:1> end
> => [1, 2, 4, 8, 9, 0]

isn't this simplified version fine too?

irb(main):003:0> a=[0,3,2,-5,0,4]
=> [0, 3, 2, -5, 0, 4]
irb(main):004:0> a.sort{|x,y| x.zero? ? 1 : x<=>y}
=> [-5, 2, 3, 4, 0, 0]

--

http://myretrocomputing.altervista.org
Baf83fa62a7481a08c40353795e11f44?d=identicon&s=25 Michael Neumann (mneumann)
on 2009-06-08 19:03
(Received via mailing list)
Paganoni schrieb:
> I forgot to mention that the array can contain several 0 values not only
> one.

Infinity = 1.0/0.0

[1,4,2,0,8,9].sort_by {|x| x == 0 ? Infinity : x }

Or:

a = [1,4,2,0,8,9]
max = a.max + 1
a.sort_by {|x| x == 0 ? max : x }

Regards,

   Michael
E0d864d9677f3c1482a20152b7cac0e2?d=identicon&s=25 Robert Klemme (Guest)
on 2009-06-08 20:31
(Received via mailing list)
On 08.06.2009 17:07, andrea wrote:
>> irb(main):029:1> end
>> => [1, 2, 4, 8, 9, 0]
>
> isn't this simplified version fine too?
>
> irb(main):003:0> a=[0,3,2,-5,0,4]
> => [0, 3, 2, -5, 0, 4]
> irb(main):004:0> a.sort{|x,y| x.zero? ? 1 : x<=>y}
> => [-5, 2, 3, 4, 0, 0]

irb(main):003:0> a=[1,0]
=> [1, 0]
irb(main):004:0> a.sort{|x,y| x.zero? ? 1 : x<=>y}
=> [0, 1]
irb(main):005:0>

Not what the OP wanted.

Cheers

  robert
E0c987f680cd640c14912ebfbf0f0f07?d=identicon&s=25 unknown (Guest)
on 2009-06-08 20:55
(Received via mailing list)
On 6/8/09, Robert Klemme <shortcutter@googlemail.com> wrote:
> irb(main):005:0>
Assuming a stable sorting algorithm, sort twice is an option:

irb(main):001:0> [1, 0].sort.sort_by{|n| n.zero? ? 1 : 0}
=> [1, 0]
irb(main):002:0> [0,3,2,-5,0,4].sort.sort_by{|n| n.zero? ? 1 : 0}
=> [-5, 4, 3, 2, 0, 0]
irb(main):003:0> a = (1..10).map{|n| rand(5) - 2}
=> [-1, 2, -1, 0, 0, 2, 0, 2, 2, -2]
irb(main):004:0> a.sort.sort_by{|n| n.zero? ? 1 : 0}
=> [-2, -1, -1, 2, 2, 2, 2, 0, 0, 0]
irb(main):033:0> a.sort.sort_by{|n| n.zero?.to_s}
=> [-2, -1, -1, 2, 2, 2, 2, 0, 0, 0]
E0d864d9677f3c1482a20152b7cac0e2?d=identicon&s=25 Robert Klemme (Guest)
on 2009-06-08 21:27
(Received via mailing list)
On 08.06.2009 20:55, brabuhr@gmail.com wrote:
>> irb(main):005:0>
>
> Assuming a stable sorting algorithm, sort twice is an option:
>
> irb(main):001:0> [1, 0].sort.sort_by{|n| n.zero? ? 1 : 0}
> => [1, 0]

Sorting twice only to make the block to sort simpler does not sound like
a good operation.

Kind regards

  robert
E0c987f680cd640c14912ebfbf0f0f07?d=identicon&s=25 unknown (Guest)
on 2009-06-08 21:55
(Received via mailing list)
On 6/8/09, Robert Klemme <shortcutter@googlemail.com> wrote:
> On 08.06.2009 20:55, brabuhr@gmail.com wrote:
>> Assuming a stable sorting algorithm, sort twice is an option:
>>
>> irb(main):001:0> [1, 0].sort.sort_by{|n| n.zero? ? 1 : 0}
>> => [1, 0]
>
> Sorting twice only to make the block to sort simpler does not sound like
> a good operation.

Especially the to_s version :-)

Error: Your application used more memory than the safety cap of 500m.
Specify -J-Xmx####m to increase it (#### = cap size in MB).
Specify -w for full OutOfMemoryError stack trace

require 'benchmark'
Infinity = 1.0/0.0
Benchmark.bm(25) do |b|
  a = (1..500000).map{|n| rand(10) - 20}
  b.report("A")    {
    a.sort.sort_by{|n| n.zero? ? 1 : 0}
  }
  b.report("B") {
    a.sort_by {|x| x == 0 ? Infinity : x }
  }
  b.report("C") {
    max = a.max + 1
    a.sort_by {|x| x == 0 ? max : x }
  }
  b.report("D") {
    tmp = a.partition{|x| x != 0 }
    tmp[0].sort + tmp[1]
  }
  b.report("E") {
    a.sort do |x,y|
      case
      when x == 0 then  1
      when y == 0 then -1
      else x <=> y
      end
    end
  }
end

Linux 2.6.28-11-generic #42-Ubuntu SMP Fri Apr 17 01:57:59 UTC 2009
i686 GNU/Linux

ruby 1.8.7 (2008-08-11 patchlevel 72) [i486-linux]
                               user     system      total        real
A                          1.070000   0.160000   1.230000 (  1.320943)
B                          1.290000   0.140000   1.430000 (  1.691468)
C                          1.530000   0.200000   1.730000 (  2.863440)
D                          0.750000   0.180000   0.930000 (  1.323304)
E                          3.840000   0.400000   4.240000 (  5.043411)

ruby 1.9.0 (2008-06-20 revision 17482) [i486-linux]
                               user     system      total        real
A                          0.470000   0.020000   0.490000 (  0.522487)
B                          0.550000   0.010000   0.560000 (  0.631449)
C                          0.640000   0.000000   0.640000 (  0.692639)
D                          0.230000   0.020000   0.250000 (  0.279466)
E                          0.820000   0.000000   0.820000 (  0.870455)

jruby 1.3.0 (ruby 1.8.6p287) (2009-06-03 5dc2e22) (OpenJDK Client VM
1.6.0_0) [i386-java]
                               user     system      total        real
A                          1.664000   0.000000   1.664000 (  1.617000)
B                          2.315000   0.000000   2.315000 (  2.316000)
C                          2.536000   0.000000   2.536000 (  2.536000)
D                          0.772000   0.000000   0.772000 (  0.772000)
E                          5.175000   0.000000   5.175000 (  5.175000)
7a561ec0875fcbbe3066ea8fe288ec77?d=identicon&s=25 Sebastian Hungerecker (Guest)
on 2009-06-08 22:08
(Received via mailing list)
Am Montag 08 Juni 2009 20:55:17 schrieb brabuhr@gmail.com:
> Assuming a stable sorting algorithm

Neither sort nor sort_by use a stable sorting algorithm though.
E0c987f680cd640c14912ebfbf0f0f07?d=identicon&s=25 unknown (Guest)
on 2009-06-08 22:43
(Received via mailing list)
On Mon, Jun 8, 2009 at 4:08 PM, Sebastian
Hungerecker<sepp2k@googlemail.com> wrote:
> Am Montag 08 Juni 2009 20:55:17 schrieb brabuhr@gmail.com:
>> Assuming a stable sorting algorithm
>
> Neither sort nor sort_by use a stable sorting algorithm though.

But, at least it was pretty fast even if it was not correct.  ;-)

require 'benchmark'
Infinity = 1.0/0.0
Benchmark.bm(25) do |b|
  a = (1..500000).map{|n| rand(10) - 20}
  b.report("A") {
    a.sort.sort_by{|n| n.zero? ? 1 : 0}
  }
  b.report("D") {
    tmp = a.partition{|x| x != 0 }
    tmp[0].sort + tmp[1]
  }
  b.report("F") {
    n = 0
    a.sort_by{|x| n+= 1; [x, n]}.sort_by{|n| n.zero? ? 1 : 0}
  }
  b.report("G") {
    tmp = a.sort.partition{|x| x != 0 }
    tmp[0] + tmp[1]
  }
  b.report("H") {
    tmp = a.sort.select{|x| x != 0 }
    tmp + ([0] * (a.size - tmp.size))
  }
end

ruby1.8 /tmp/z
                               user     system      total        real
A                          1.030000   0.160000   1.190000 (  1.313981)
D                          0.720000   0.170000   0.890000 (  0.996888)
F                         19.510000   1.270000  20.780000 ( 24.233460)
G                          0.800000   0.170000   0.970000 (  1.180949)
H                          0.540000   0.140000   0.680000 (  0.897509)

ruby1.9 /tmp/z
                               user     system      total        real
A                          0.440000   0.020000   0.460000 (  0.520912)
D                          0.250000   0.000000   0.250000 (  0.274845)
F                         17.720000   0.080000  17.800000 ( 19.969714)
G                          0.260000   0.000000   0.260000 (  0.299049)
H                          0.180000   0.000000   0.180000 (  0.210772)

jruby /tmp/z
                               user     system      total        real
A                          1.688000   0.000000   1.688000 (  1.641000)
D                          0.848000   0.000000   0.848000 (  0.849000)
F                         13.181000   0.000000  13.181000 ( 13.180000)
G                          0.678000   0.000000   0.678000 (  0.678000)
H                          0.591000   0.000000   0.591000 (  0.591000)
E0d864d9677f3c1482a20152b7cac0e2?d=identicon&s=25 Robert Klemme (Guest)
on 2009-06-08 23:15
(Received via mailing list)
On 08.06.2009 22:42, brabuhr@gmail.com wrote:
> On Mon, Jun 8, 2009 at 4:08 PM, Sebastian
> Hungerecker<sepp2k@googlemail.com> wrote:
>> Am Montag 08 Juni 2009 20:55:17 schrieb brabuhr@gmail.com:
>>> Assuming a stable sorting algorithm
>> Neither sort nor sort_by use a stable sorting algorithm though.
>
> But, at least it was pretty fast even if it was not correct.  ;-)

Hehe, talk about priorities. :-)

Cheers

  robert
21dd018d2954c5c1f9f2fe00a18f6d75?d=identicon&s=25 Gabriel Medina (rha7dotcom)
on 2009-06-09 05:00
(Received via mailing list)
Paganoni wrote:
> Hello, I need to sort
> [1,4,2,0,8,9] to [1,2,4,8,9,0]
>
> A simple ascending sort but with the zero values to the end
>
> I really don't see how to do
>
> Thanks for your help

Delegate the FixNum class

http://www.pastie.org/505312
E0d864d9677f3c1482a20152b7cac0e2?d=identicon&s=25 Robert Klemme (Guest)
on 2009-06-09 09:19
(Received via mailing list)
2009/6/9 Rha7 <rha7.com@gmail.com>:
>
> Delegate the FixNum class
>
> http://www.pastie.org/505312

Another good idea!  However, you can save yourself a bit of typing:

http://www.pastie.org/505471

Kind regards

robert
This topic is locked and can not be replied to.