From: Josh Cheek <josh.cheek@...>
Date: 2009-10-13T11:15:17+09:00
Subject: Re: manually sort array of numbers

--000e0cd2da6ef427660475c79d3a
Content-Type: text/plain; charset=ISO-8859-1

On Mon, Oct 12, 2009 at 4:29 PM, Jason Lillywhite <
jason.lillywhite@gmail.com> wrote:

> for the sake of learning, I built a sort method to sort an array of
> numbers manually rather than with the built-in Array#sort method.
>
> below is my code. Would you say this is a "good" way to do it?
>
> def sort_array(array)
>  i = 0
>  while i < array.length do
>    index_max = max_array_index(array, array.length - i)
>    temp = array[index_max]
>    array[index_max] = array[array.length - i - 1]
>    array[array.length - i - 1] = temp
>    i += 1
>  end
>  return array
> end
>
> def max_array_index(array, size)
>  i = 1
>  i_max = 0
>  while i < size do
>    if array[i] > array[i_max] then
>      i_max = i
>    end
>    i += 1
>  end
>  return i_max
> end
>
> Thank you for your comments.
> --
> Posted via http://www.ruby-forum.com/.
>
>
Hi, Jason. I probably wouldn't.

First of all, the time complexity of your sort is O(n^2) while the built in
sort's time complexity is O(n lg n)

Also, the built in sort is implemented in C, so it is much quicker.


Here is a benchmark showing that in an array of 5000 integers, your solution
takes about 20 seconds, while the built in sort completes too fast to be
recorded (about 0 seconds).

def sort_array(array)
 i = 0
 while i < array.length do
   index_max = max_array_index(array, array.length - i)
   temp = array[index_max]
   array[index_max] = array[array.length - i - 1]
   array[array.length - i - 1] = temp
   i += 1
 end
 return array
end

def max_array_index(array, size)
 i = 1
 i_max = 0
 while i < size do
   if array[i] > array[i_max] then
     i_max = i
   end
   i += 1
 end
 return i_max
end


def shuffle( array )
  (2*array.size).times do
    i = rand( array.size )
    j = rand( array.size )
    array[i] , array[j] = array[j] , array[i]
  end
  array
end

require 'benchmark'
Benchmark.bmbm do |b|
  array1 = shuffle((1..5_000).to_a)
  array2 = array1.dup

  b.report( "Jason's sort" ) do
    sort_array( array1 )
  end

  b.report( "default sort" ) do
    array2.sort!
  end

end


__END__
Here are the results I get:
Rehearsal ------------------------------------------------
Jason's sort  19.234000   0.015000  19.249000 ( 19.640000)
default sort   0.000000   0.000000   0.000000 (  0.000000)
-------------------------------------- total: 19.249000sec

                   user     system      total        real
Jason's sort  20.047000   0.000000  20.047000 ( 21.125000)
default sort   0.000000   0.000000   0.000000 (  0.000000)

--000e0cd2da6ef427660475c79d3a--