Question understanding SORT function? 5

[garymgordon]

I am looking at a Subroutine and short script that goes like this.

#!/usr/bin/perl -w

@array = (1,24,8,144,72,288);
foreach (sort sort_by_number(@array))
{
print ("$_ "
}


sub sort_by_number
{
if ($a < $b)
{
return -1;
}

elsif ($a == $b)
{
return 0;
}

else
{
return 1;
}
}

OUTPUT: 1 8 24 72 144 288


Now ....

The question is ...

I don't understand how the sort_by_number routine is performing its check on the @array??

I must be missing something in my thinking process.

When the subroutine runs, ... can you please help by explaining exactly the flow of what is being SORTED, how it is being sorted, and what is being assigned to $a and $b as the SORT PROCESS goes through.

I guess I don't understand how the SORT function is looking at the values contained in @array ... in order to sort the numbers and make any comparisons?

For example ... is the number 1 being compared to all the other numbers ... and if so, then what?

Please explain this process of how it works.

Thanks...

(PS .. the sooner you can reply to this question the better. I would greatly appreciate your help.)

Gary

Gary M. Gordon, LLC
webmaster@garymgordon.com
Certified Web Developer ::
Application Programmer

http://www.garymgordon.com/

 

[stillflame]

sorting lesson

i don't know the actual sorting algorithm for perl's sort, but i have a basic understanding.
basically, perl needs to compare the items to each other, to see which one goes before the next. $a and $b are arbitrary elements of the array, and, after the sort is over, they will have been every element. i'll try to show it with a sample run of a sorting algorithm i do know.

our array will be this: @array = (2, 5, 1, 3, 4).
now, lets start at the beginning. first, it will compare the first element to the last. it will set the first to $a, the last to $b. it puts those two variables through the subroutine provided (which i should point out in this case is just a longer version of '$a<=>$b'), and that subroutine has to return -1, 0, or 1, depending on the relationship.
since 2 < 4 is true, the subroutine returns a -1. this tells the sort that the 2 and the 4 are in the correct position relative to each other(2 is less than 4, so 2 should go before 4), so doesn't do anything.
then sort compares 2 to 3, reasigning those values to $a and $b, and sending them through the subroutine. again, it returns a -1, and sort leaves them alone.
next it compares 2 and 1. since 2 is greater than 1, the subroutine retuns a 1. the sorting algorithm then knows that the 1 is less than the 2, and switches their positions to account for this, thus making the array look like:
(1, 5, 2, 3, 4).
now the sort compares 1 and 5(since the 1 is now in the first position). the subroutine returns another '-1', so nothing is moved.
now it knows that the 1 is the least valued element, and it doesn't need to look at it again. next, it'll start with the second position, and compare it to the other elements, starting with the last.
5 compared to 4 yields a 1, meaning their positions will be switched:
(1, 4, 2, 3, 5)
4(now in the second position) compared to 3 yields a 1, so their positions get switched, making it: (1, 3, 2, 4, 5)
3 compared to 2 yields a 1, so their positions get switched, making it: (1, 2, 3, 4, 5).
then it knows that the 2 is the second least value.

now, even though it looks sorted, my sorting algorithm would still then go on to compare the last three numbers against each other, to make sure they were in the right places. i know perl's sort is alot more effecient than this, and will rip it apart in a speed test, but i hope this has explained a little about how it works.

HTH &quot;If you think you're too small to make a difference, try spending a night in a closed tent with a mosquito.&quot;

 

[garymgordon]

That was wonderful!!!!!

Thank you ... very, very much. I didn't understand that the flow of the thinking process.

So ... my hat is off to you!!

Gary
Gary M. Gordon, LLC
webmaster@garymgordon.com
Certified Web Developer ::
Application Programmer

http://www.garymgordon.com/

 

[garymgordon]

One more question about this ...

If -1 tells the sort function not to do anything and leave it alone ...

And 1 tell is that it must switch the values ...

What happens if the two numbers (or values being compared) are EQUAL returning a 0 ? What happens then ?

Gary
Gary M. Gordon, LLC
webmaster@garymgordon.com
Certified Web Developer ::
Application Programmer

http://www.garymgordon.com/

 

[stillflame]

I don't know for sure :-( my guess is it leaves them the same, because that would preserve their order as they moved them along. when comparing these two elements(without the a or b):[tt]
(1, 4(a), 3, 2, 4(b), 5)[/tt]
if it left them alone, it would then go on to compare these two:[tt]
(1, 4(a), 3, 2, 4(b), 5)[/tt]
and it would switch them, making it:[tt]
(1, 2, 3, 4(a), 4(b), 5)[/tt]
and their order is preserved...

that's just a guess, but i know that in the end, it makes sure that they're in the same relative order, and that the array is sorted. if anyone else knows better (or can confirm my answer), i'd be happy to know.

&quot;If you think you're too small to make a difference, try spending a night in a closed tent with a mosquito.&quot;

 

[pishans]

According to &quot;A Fresh Look at Efficient Perl Sorting&quot; (

http://conferences.oreilly.com/cd/perl3/user_papers/uguttman/sorting.html)

the perl sort function is implemented with a standard QuickSort algorithm.


Søren

 

[garymgordon]

pishans,

Thank you. That was a lot of help.



Gary
Gary M. Gordon, LLC
webmaster@garymgordon.com
Certified Web Developer ::
Application Programmer

http://www.garymgordon.com/

 

[tsdragon]

DO NOT THINK OF IT AS &quot;leave it alone&quot;, &quot;switch the values&quot; or whatever. The way it works is: if $a should be sorted as LESS THAN $b return -1, if $a should be sorted as EQUAL TO $b return 0, if $a should be sorted as GREATER THAN $b return 1. For a numeric sort you should simply return $a <=> $b. For a string sort return $a cmp $b.

To see what happens you could try printing $a and $b in your sort routine. You would probably see the same value pop up for $a several times with different values of $b (or vice versa) and probably even see a value appear as $a AND as $b (or vice versa) depending upon the sort method used and the sequence of the original list of values. The important thing is that IT DOESN'T MATTER! Just compare the values of $a and $b and return the appropriate value based on the comparison. Here's a sort routine that takes an list of names, entered as &quot;firstname lastname&quot; and sorts it by lastname then firstname:

sub sort_by_name {
   # Split first compare value into firstname and lastname
   my($first_a, $last_a) = split(' ', $a);
   # Split 2nd compare value into firstname and lastname
   my($first_b, $last_b) = split(' ', $b);
   # If lastnames are not equal return compare of last names
   # If lastnames are equal return compare of first names
   return $last_a cmp $last_b or $first_a cmp $first_b;

Here's what's happening in the return statement:
If $last_a is less than $last_b the cmp returns -1, if $last_a is greater than $last_b the cmp returns 1, either of which is TRUE, which short-circuits the 'or' and the return statement returns either -1 (sort $a BEFORE $b) or 1 (sort $a AFTER $b). If $last_a is equal to $last_b the cmp returns 0, which is FALSE, so the other half of the 'or' is executed. This cmp returns either -1, 0, or 1 depending on the sort sequence of the FIRST names, which becomes the value returned by the return statement. So if the last names are equal the sort is based on the first names.

Clear as mud, right?

You can extend this basic technique to sort arrays of arrays, arrays of hashes, etc. as long as your just keep in mind that you don't really care in your sort routine what the values of $a and $b actually ARE, only HOW THEY COMPARE to each other (or how the things they reference compare to each other).
Meddle not in the affairs of dragons,
For you are crunchy, and good with mustard.

 

[garymgordon]

Thank you very much!!!

Gary
Gary M. Gordon, LLC
webmaster@garymgordon.com
Certified Web Developer ::
Application Programmer

http://www.garymgordon.com/