From: Brian Candler <lists@...>
Date: 2012-07-30T03:21:24+09:00
Subject: Re: Help with exercise from Chris Pine's Ruby Book: Sort without using .sort

Lars Haugseth wrote in post #1070091:
>> You might want to reduce the problem to a smaller task first. For
>> example, you could write a method that finds the minimum of an array and
>> returns both the minimum and the rest of the array. You can then use
>> this simple method to recursively build a sorted array:
>
> Though that might defeat the purpose of the exersize, there already
> exists such a method, Array#min.
>
> If using Array#min (or some self-implemented version of min) is
> permitted, sorting can be done as simple as:
>
>    sorted = unsorted.size.times.map { unsorted.delete unsorted.min }

Ugh... Array#delete is an operation which modifies the source array. 
Mixing functional-style with side effects is pretty horrible IMO.

Anyway, that code doesn't even work properly:

>> unsorted = [9,7,5,5,3,1]
=> [9, 7, 5, 5, 3, 1]
>> sorted = unsorted.size.times.map { unsorted.delete unsorted.min }
=> [1, 3, 5, 7, 9, nil]

However, picking one lowest element each time (a "selection sort") is a 
reasonable approach to solve the problem, albeit not an efficient 
algorithm in practice.

You might also like to try a "quicksort"-style approach: partition array 
into two parts, where all elements of one are lower than all elements of 
the other; sort each part recursively; then concatenate the sorted 
parts.

>> unsorted=[9,7,5,5,3,1]
=> [9, 7, 5, 5, 3, 1]
>> pivot = unsorted[rand unsorted.size]
=> 5
>> sub1, sub2 = unsorted.partition { |e| e < pivot }
=> [[3, 1], [9, 7, 5, 5]]

-- 
Posted via http://www.ruby-forum.com/.