manually sort array of numbers

[Jason Lillywhite]

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 > array[i_max] then
i_max = i
end
i += 1
end
return i_max
end

Thank you for your comments.

 

[Josh Cheek]

[Note: parts of this message were removed to make it a legal post.]

On Mon, Oct 12, 2009 at 4:29 PM, Jason Lillywhite <

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 > array[i_max] then
i_max = i
end
i += 1
end
return i_max
end

Thank you for your comments.

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 > 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 , array[j] = array[j] , array
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)

 

[Jason Lillywhite]

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.

 

[Josh Cheek]

[Note: parts of this message were removed to make it a legal post.]

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.[/QUOTE]
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 n*n/2 + n/2, and in Big-O notation, we are
just concerned with which factors have the greatest impact. You can see the
n*n/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

 

[Gary Wright]

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 Wright

 

[Rob Biedenharn]

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.
--=20
Posted via http://www.ruby-forum.com/.

It's really not a zero but a capital Omicron (greek). You can get much =20=

more than you need at http://c2.com/cgi/wiki?OrderNotation or asking =20
Google about "big o notation".

As for your selection sort[1], for each position, i, you need to look =20=

through i-1 other elements to find the max. So the number of =20
comparisons is =E2=88=91i where 0<=3Di<n and n is the size of your =
array. =20
That's n*(n-1)/2 comparisons. One swap for positions 1 to n-1. Some =20
initialization (call that c).

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

-Rob

Rob Biedenharn http://agileconsultingllc.com
(e-mail address removed)

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