# Manually sort array of numbers

**URL:** <https://www.ruby-forum.com/t/manually-sort-array-of-numbers/177182>\
**Category:** Ruby\
**Created:** [October 12, 2009, 11:29pm UTC](https://www.ruby-forum.com/t/manually-sort-array-of-numbers/177182 "2009-10-12T23:29:21Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![leveille](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/l/a88e57/32.png) [@leveille](https://www.ruby-forum.com/u/leveille)\
**Post date:** [October 12, 2009, 11:29pm UTC](https://www.ruby-forum.com/t/manually-sort-array-of-numbers/177182/1 "2009-10-12T23:29:21Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![leveille](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/l/a88e57/32.png) [@leveille](https://www.ruby-forum.com/u/leveille)\
**Post date:** [October 13, 2009, 4:15am UTC](https://www.ruby-forum.com/t/manually-sort-array-of-numbers/177182/2 "2009-10-13T04:15:39Z")

</div>

On Mon, Oct 12, 2009 at 4:29 PM, Jason L. \<  
removed\_email\_address@domain.invalid\> 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)

---

<div class="post-metadata">

**Author:** ![leveille](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/l/a88e57/32.png) [@leveille](https://www.ruby-forum.com/u/leveille)\
**Post date:** [October 13, 2009, 4:46am UTC](https://www.ruby-forum.com/t/manually-sort-array-of-numbers/177182/3 "2009-10-13T04:46:53Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![leveille](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/l/a88e57/32.png) [@leveille](https://www.ruby-forum.com/u/leveille)\
**Post date:** [October 13, 2009, 5:23am UTC](https://www.ruby-forum.com/t/manually-sort-array-of-numbers/177182/4 "2009-10-13T05:23:32Z")

</div>

On Mon, Oct 12, 2009 at 9:46 PM, Jason L. \<  
removed\_email\_address@domain.invalid\> 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/](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 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

---

<div class="post-metadata">

**Author:** ![leveille](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/l/a88e57/32.png) [@leveille](https://www.ruby-forum.com/u/leveille)\
**Post date:** [October 13, 2009, 5:28am UTC](https://www.ruby-forum.com/t/manually-sort-array-of-numbers/177182/5 "2009-10-13T05:28:13Z")

</div>

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/](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](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).

(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  
long enough) will be within a constant factor of n**2 therefore O(n**2)

-Rob

Rob B. [http://agileconsultingllc.com](http://agileconsultingllc.com)  
removed\_email\_address@domain.invalid

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

---

<div class="post-metadata">

**Author:** ![leveille](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/l/a88e57/32.png) [@leveille](https://www.ruby-forum.com/u/leveille)\
**Post date:** [October 13, 2009, 5:24am UTC](https://www.ruby-forum.com/t/manually-sort-array-of-numbers/177182/6 "2009-10-13T05:24:07Z")

</div>

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](http://en.wikipedia.org/wiki/Big_O_notation)

Gary W.