One line sorting

Ruby
1

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

2

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” (
Selection sort - Wikipedia)
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ć [email protected]

3

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…

4

Matthew Bennett wrote:

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

Oops! Sorry, I meant Fabian…

5

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 S.” [email protected] wrote in message
news:[email protected]…
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” (
Selection sort - Wikipedia)
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!

6

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

“Haris Bogdanoviæ” [email protected] wrote in message
news:[email protected]…

7

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ć [email protected]

8

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 ?

9

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.

You can see various sorting algorithms implemented for Ruby (among other
languages) at Category:Sorting Algorithms - Rosetta Code

10

2009/7/11 Haris Bogdanović [email protected]

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!

11

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.

12

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æ” [email protected] wrote in message
news:[email protected]…

13

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 “beauty” 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!

14

Am Sonntag 12 Juli 2009 20:20:09 schrieb Haris B.:

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

15

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.

16

On Jul 11, 6:00Â pm, Fabian S. [email protected]
wrote:

2009/7/11 Haris Bogdanović [email protected]

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’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.

17

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!

18

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

Ok, but it does look elegant and in one line.
That’s how programs should look.
'The ‘each’ method can give me index of an element. I would use ‘map’
instead
but it can’t give me index, just the element so I would have to create a
new
list.
I guess that would be pure functional and maybe more efficient in this
case…
What are side-effects in this case ?

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.

Just what I was going to try next.

19

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.

20

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.