One line sorting

Hi.

I would like to implement a sorting algorithm in one line of code if
possible.

n=[7,4,9,55,98,11,42]
n.inject(n[0]) {|min, i| min=i if i<min; min}

I first find lowest number in list and then would like to replace it with
first element. After that I need to start from the second element, find the
lowest element, replace it with that second element and so on till I reach
the end of a list.
I don't know how this sorting algorithm is called ?

I managed to find the minimum in the above code. What next ? How to replace
two elements ?
The result is a number object. Where do I (in general) put a dot in above
expression to perform some methods on that object (when expression has a
block {} of code in itself ) ?

Can you also show me that for a quick sort ?

Thanks
Haris

Well, you could just do

    [7,4,9,55,98,11,42].sort

:wink: That's much more optimized than anything else you can do in one line...

What you described is called a "Selection sort" (
http://en.wikipedia.org/wiki/Selection_sort)
If you really must implement it yourself (why in one line?)
You could try something like this:

0.upto(n.size-1) do |i|
    lowest_idx = i + n[i..-1].index(n[i..-1].min)
    n[lowest_idx], n[i] = n[i], n[lowest_idx]
end

Which is already pretty hackishly short and inefficient. :wink:
Greetz!

···

2009/7/11 Haris Bogdanović <fbogdanovi@xnet.hr>

Hi.

I would like to implement a sorting algorithm in one line of code if
possible.

n=[7,4,9,55,98,11,42]
n.inject(n[0]) {|min, i| min=i if i<min; min}

I first find lowest number in list and then would like to replace it with
first element. After that I need to start from the second element, find the
lowest element, replace it with that second element and so on till I reach
the end of a list.
I don't know how this sorting algorithm is called ?

I managed to find the minimum in the above code. What next ? How to replace
two elements ?
The result is a number object. Where do I (in general) put a dot in above
expression to perform some methods on that object (when expression has a
block {} of code in itself ) ?

Can you also show me that for a quick sort ?

Thanks
Haris

Haris Bogdanoviæ wrote:

Hi.

I would like to implement a sorting algorithm in one line of code if possible.

n=[7,4,9,55,98,11,42]
n.inject(n[0]) {|min, i| min=i if i<min; min}
  

Do you actually need to implement the specific algorithm? [2,3,1].sort will sort it quite efficiently, or .sort! which will replace the array with the sorted version, and you can pass it a block to tell it what should be classed as "bigger", so that

[2,3,1].sort { |a, b| b <=> a }

would give equivalent results to

[2,3,1].sort.reverse

If you do need to implement that exact algorithm, my best guess is something along the lines of

q = [7,4,9,55,98,11,42]
a = [];
until q.empty? ; a << q.delete(q.min) ; end

There's probably a better way though (there always is!) Array#min is a method of Enumerable.

The result is a number object. Where do I (in general) put a dot in above expression to perform some methods on that object (when expression has a block {} of code in itself ) ?
  

You can put it at the end of the block, ruby's nice like that. So you could do:

[2,3,1].sort { |a, b| a <=> b }.reverse

Regards,
Matthew

PS: Haris pipped me to the post! Still, this might be useful anyway...

In general, how do I combine collect, inject and detect in one line of code
to create functional expressions ?

"Haris Bogdanoviæ" <fbogdanovi@xnet.hr> wrote in message
news:h39ttc$279$1@gregory.bnet.hr...

···

Hi.

I would like to implement a sorting algorithm in one line of code if
possible.

n=[7,4,9,55,98,11,42]
n.inject(n[0]) {|min, i| min=i if i<min; min}

I first find lowest number in list and then would like to replace it with
first element. After that I need to start from the second element, find
the lowest element, replace it with that second element and so on till I
reach the end of a list.
I don't know how this sorting algorithm is called ?

I managed to find the minimum in the above code. What next ? How to
replace two elements ?
The result is a number object. Where do I (in general) put a dot in above
expression to perform some methods on that object (when expression has a
block {} of code in itself ) ?

Can you also show me that for a quick sort ?

Thanks
Haris

I managed to do selection sort in ruby in one line:

a=[7,4,9,55,98,11,42]

a.each_index {|i| a.each_index {|i2| a[i], a[i2]=a[i2], a[i] if a[i]<a[i2]}}

Pretty elegant.

I think that selection sort is faster if inner loop goes from last to first
element.
There is reverse_each but is there reverse_each_index or something ?

You can see various sorting algorithms implemented for Ruby (among other
languages) at http://rosettacode.org/wiki/Category:Sorting_Algorithms

···

At 2009-07-11 07:43AM, "Haris Bogdanoviæ" wrote:

Hi.

I would like to implement a sorting algorithm in one line of code if
possible.

--
Glenn Jackman
    Write a wise saying and your name will live forever. -- Anonymous

def quick_sort(array)
  return array if array.length <=1
  pivot=array[array.length/2]
  return quick_sort(array.select {|i| i<pivot}) + array.select {|i|
i==pivot} + quick_sort(array.select {|i| i>pivot})
end

I hope that's pure functional version of quick sort.
No list is changed but how many temporary lists are created before the final
result comes up ?
I guess that's job for garbage collector.
And I doubt this could be closer to one line as it is.

Matthew Bennett wrote:

PS: Haris pipped me to the post! Still, this might be useful anyway...

Oops! Sorry, I meant Fabian...

Well, I saw one line Haskell sort and thought, maybe it's possible in Ruby.
I'm just trying out functional programming in Ruby.
Could you just tell me how to do methods on my expression which has block {}
and evaluates to number object;
do I put () parenthesses around the whole expression and dot after them or
somethin else ?

Thanks

"Fabian Streitel" <karottenreibe@googlemail.com> wrote in message
news:2569cf860907110914udbd2981w70e553eb6c74f492@mail.gmail.com...
Well, you could just do

    [7,4,9,55,98,11,42].sort

:wink: That's much more optimized than anything else you can do in one line...

What you described is called a "Selection sort" (
http://en.wikipedia.org/wiki/Selection_sort)
If you really must implement it yourself (why in one line?)
You could try something like this:

0.upto(n.size-1) do |i|
    lowest_idx = i + n[i..-1].index(n[i..-1].min)
    n[lowest_idx], n[i] = n[i], n[lowest_idx]
end

Which is already pretty hackishly short and inefficient. :wink:
Greetz!

I managed to do selection sort in ruby in one line:

I'm sorry to disappoint you, but that is bubblesort, not selectionsort
See wikipedia for more information.

I think that selection sort is faster if inner loop goes from last to first

element.

The bubblesort you did here will not be faster, no matter what order
you traverse the items in. After all, you will look at each item in the
outer loop and again at each item in the inner loop again.
That makes it n-squared no matter what order you traverse them in.

There is reverse_each but is there reverse_each_index or something ?

Not that I know of, but you could just do

[1,2,3,4].reverse.each_with_index

But I still don't get what you're trying to achieve here...?

Greetz!

···

2009/7/11 Haris Bogdanović <fbogdanovi@xnet.hr>

def quick_sort(array)
return array if array.length <=1
pivot=array[array.length/2]
return quick_sort(array.select {|i| i<pivot}) + array.select {|i|
i==pivot} + quick_sort(array.select {|i| i>pivot})
end

Why not use:

quick_sort(array.select {|i| i<=pivot}) + quick_sort(array.select {|i|

···

On Jul 13, 5:47 am, "Haris Bogdanoviæ" <fbogdan...@xnet.hr> wrote:

pivot})

you mean like

[1, 2, 3, 4].find { |x| x >= 3 }.odd?

(which would return true if the first number found in the array >= 3 is odd)

you don't need to put parentheses around those things, ruby is smart enough
to
figure out that you want to call #odd? on the result of #find, which uses
that block.

But you have to put parenthesis around the arguments to find if you use {
... }:
[1,2,3,4].inject(0) { some code } # will work
[1,2,3,4].inject 0 { some code } # will not

Greetz!

···

2009/7/11 Haris Bogdanović <fbogdanovi@xnet.hr>

Well, I saw one line Haskell sort and thought, maybe it's possible in Ruby.
I'm just trying out functional programming in Ruby.
Could you just tell me how to do methods on my expression which has block
{}
and evaluates to number object;
do I put () parenthesses around the whole expression and dot after them or
somethin else ?

Thanks

"Fabian Streitel" <karottenreibe@googlemail.com> wrote in message
news:2569cf860907110914udbd2981w70e553eb6c74f492@mail.gmail.com...
Well, you could just do

   [7,4,9,55,98,11,42].sort

:wink: That's much more optimized than anything else you can do in one line...

What you described is called a "Selection sort" (
http://en.wikipedia.org/wiki/Selection_sort)
If you really must implement it yourself (why in one line?)
You could try something like this:

0.upto(n.size-1) do |i|
   lowest_idx = i + n[i..-1].index(n[i..-1].min)
   n[lowest_idx], n[i] = n[i], n[lowest_idx]
end

Which is already pretty hackishly short and inefficient. :wink:
Greetz!

The bubblesort you did here will not be faster, no matter what order
you traverse the items in. After all, you will look at each item in the
outer loop and again at each item in the inner loop again.
That makes it n-squared no matter what order you traverse them in.

Just think. If you go from biggest to smallest in inner loop then
if you put smaller number at the beginning then bigger number
goes somewhere in the list. If you find even smaller number then exchange
repeats but the two numbers you exchanged are in better place, the smaller
number
stands before bigger.
That means that there will be less exchanges needed if you traverse inner
loop
from last to first. Reversing elements will not help.
So it's true that there will be same number of times going through loops but
there will be less exchanges needed so that is why it would be faster.

[1,2,3,4].reverse.each_with_index

As I said that will not help.
But there is a way to get that speed increment.
The list has to be sorted from biggest to smallest and then do reverse, but
then, reverse takes some time.

I'm sorry to disappoint you, but IMHO this behaves more like
selection
sort than bubble sort. Bubble sort swaps adjacent elements,
"bubbling" the
ith largest (smallest) to the end at iteration i. If it were bubble
sort
you would see something like if elem[i] < elem[i+1] swap(i,i+1).

Consider the case where the largest element is at the start
of the list, and should be at the other end. You would get one swap
with this algorithm on the first pass through the list, whereas
bubble
sort would have n-1 swaps in bubbling it into place.

Selection sort swaps the ith largest directly into the ith place on
the ith
iteration, which is what we're seeing here, but rather than store the
index
of the ith largest, he's just swapping any element into position i
that is
larger than the current element. Same intended result at each
iteration,
with some extra swapping along the way.

I can understand your confusion because Haris is making a lot of
unnecessary
swaps in his implementation, and this extra work does move elements
closer
to their final positions, but there's no bubbling going on. I'd say
it's
neither selection nor bubble, but clearly n^2.

···

On Jul 11, 6:00 pm, Fabian Streitel <karottenre...@googlemail.com> wrote:

2009/7/11 Haris Bogdanović <fbogdan...@xnet.hr>

> I managed to do selection sort in ruby in one line:

I'm sorry to disappoint you, but that is bubblesort, not selectionsort
See wikipedia for more information.

It turns out that I was right about having different number of exchanges but
I was wrong about direction.
If you sort numbers from lowest to biggest you need smaller number of
exchanges than if you sort in opposite direction.
I made a test and in this particullar list [7,4,9,55,98,11,42] it's 11
exchanges for smallest to biggest number and 18 for biggest to smallest..

"Haris Bogdanoviæ" <fbogdanovi@xnet.hr> wrote in message
news:h3ciqh$rv8$1@gregory.bnet.hr...

···

>The bubblesort you did here will not be faster, no matter what order

you traverse the items in. After all, you will look at each item in the
outer loop and again at each item in the inner loop again.
That makes it n-squared no matter what order you traverse them in.

Just think. If you go from biggest to smallest in inner loop then
if you put smaller number at the beginning then bigger number
goes somewhere in the list. If you find even smaller number then exchange
repeats but the two numbers you exchanged are in better place, the smaller
number
stands before bigger.
That means that there will be less exchanges needed if you traverse inner
loop
from last to first. Reversing elements will not help.
So it's true that there will be same number of times going through loops
but
there will be less exchanges needed so that is why it would be faster.

[1,2,3,4].reverse.each_with_index

As I said that will not help.
But there is a way to get that speed increment.
The list has to be sorted from biggest to smallest and then do reverse,
but then, reverse takes some time.

You're right, I'm sorry. It looked like a bubblesort, and I didn't want to
get any more into that, since it seems fairly pointless to me :wink:

Greetz!

I also looked in wikipedia and there is no such exact algorithm.
Maybe I should register it somewhere as Haris sort even though it's not very
fast.
But there are many sort algorithms out there that are slow.

It turns out that I was right about having different number of exchanges
but
I was wrong about direction.
If you sort numbers from lowest to biggest you need smaller number of
exchanges than if you sort in opposite direction.
I made a test and in this particullar list [7,4,9,55,98,11,42] it's 11
exchanges for smallest to biggest number and 18 for biggest to smallest..

Alright buddy, now try it with some other list, e.g.
[5,4,3,2,1]

When sorting from lowest to biggest, you'll get a lot of exchanges
when sorting from biggest to lowest, you'll have no exchanges.

No matter what direction you sort in, I'm always able to give you
an array of number so you will need the maximum number of exchanges.
That's the <sarcasm>"beauty"</sarcasm> of bubblesort.

It is n-squared and it will always be, no matter what direction you sort in.
You should probably read more about effective sorting, instead of trying
to figure out how to optimize your bubblesort here. It is ineffective, no
matter what you do! If you want a more effective sorting algorithm, try
Quicksort or Mergesort, but please stop trying to optimize your n-squared
bubblesort here...
I really can't get what it is you're trying to do here?

Greetz!

Ok, I guess you are right. It really depends on a list.

I really can't get what it is you're trying to do here?

Just practicing functional programming in Ruby.

Your sort method isn't really what most people would consider functional
programming, being that it relies on mutating the array (and the each-method
which isn't even present in purely functional languages being that it needs
side-effects to have any effect at all).
If you want to implement a sort method in functional style, you should
consider doing a recursive quick sort, which is quite simple and can be done
in one line if you don't count the "def foo()" and "end" as their own lines.
Also functional programming does not equal "one line". There's nothing wrong
with spreading it out over multiple lines for readability.

HTH,
Sebastian

···

Am Sonntag 12 Juli 2009 20:20:09 schrieb Haris Bogdanovic:

>I really can't get what it is you're trying to do here?

Just practicing functional programming in Ruby.