Manually sort array of numbers

Ruby
1

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.

2

On Mon, Oct 12, 2009 at 4:29 PM, Jason L. <
[email protected]> wrote:

array[index_max] = array[array.length - i - 1]
if array[i] > array[i_max] then

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)

3

Josh C. wrote:

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)

Wow. That is interesting. Thank you for sharing. I really just want to
learn how to sort something on my own before using the Array#sort
method. I learned to write this function in my intro to Java class at
school.

What does the zero in “O(n^2)” mean and how did you figure that out?

Thanks again.

4

On Mon, Oct 12, 2009 at 9:46 PM, Jason L. <
[email protected]> wrote:

What does the zero in “O(n^2)” mean and how did you figure that out?

Thanks again.

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

Hi, Jason, the 0 is an uppercase letter ‘o’, it is called Big-O
notation. It
represents the manner in which the number of steps grow as the size of
the
problem increases. O(n^2) means that the number of steps grows in a
quadratic fashion. In other words, after some given value of n is
reached,
if we were to graph the number of steps involved, it would be increasing
as
if it were squared.

In this case, n is the length of the array. So O(n^2) means that if you
cut
everything else out, the greatest impact to the number of steps follows
n*n
while the built in sort follows n * log(n)

There can be other factors, but when n gets large enough, the other
factors
don’t matter any more.

Why do we say that yours is O(n^2) instead of some other time
complexity?
Well if you look at the algorithm, you can see that in the sort_array
function, you have
i = 0
while i < array.length do
…
i += 1
end

So that is the first n, it goes through each of the n indexes in the
array.
But, for each of these indexes, it calls max_array_index, which also
goes
through the indexes, as you can see in
def max_array_index(array, size)
i = 1
while i < size do
…
i += 1
end

So, that is the second n. It will go through the n indexes in the
sort_array
function, and for each of these indexes, goes through the indexes in the
mas_array_index function. So it is n*n, or n^2.

Now, there are other steps in there, too, but they aren’t really that
important when the size of the array gets large. And yes, the
max_array_index function doesn’t go through all of the indexes, but
rather
goes through 1 fewer than the previous iteration, each time, but given
this
knowledge, we can say that the actual time complexity would be closer to
n(n+1)/2, but that comes out to nn/2 + n/2, and in Big-O notation, we
are
just concerned with which factors have the greatest impact. You can see
the
nn/2 will grow much faster than n/2, so we ignore n/2. And you can see
that
squaring it’s value every time will cause it to increase much faster
than
dividing it by 2 will slow it’s increase, so we discard the coefficient
and
are just left with n*n, so it is O(n^2)

Hope that wasn’t too poorly worded.
-Josh

5

On Oct 12, 2009, at 10:46 PM, Jason L. wrote:

school.

What does the zero in “O(n^2)” mean and how did you figure that out?

Thanks again.

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

It’s really not a zero but a capital Omicron (greek). You can get much
more than you need at http://c2.com/cgi/wiki?OrderNotation or asking
Google about “big o notation”.

As for your selection sort[1], for each position, i, you need to look
through i-1 other elements to find the max. So the number of
comparisons is ∑i where 0<=i<n and n is the size of your array.
That’s n*(n-1)/2 comparisons. One swap for positions 1 to n-1. Some
initialization (call that c).

(n2)/2 - n/2 + (n-1) + c
(n2)/2 + n/2 + (c-1)
which for all sufficiently large values of n (i.e., arrays that are
long enough) will be within a constant factor of n2 therefore O(n2)

-Rob

Rob B. http://agileconsultingllc.com
[email protected]

[1] It’s not a bubble sort because, iirc, you were only making the
swap once per position.

6

On Oct 12, 2009, at 10:46 PM, Jason L. wrote:

What does the zero in “O(n^2)” mean and how did you figure that out?

Here is a place to start on ‘big oh notation’:
http://en.wikipedia.org/wiki/Big_O_notation

Gary W.