CGI/Perl Guide | Learning Center | Forums | Advertise | Login
Site Search: in

  Main Index MAIN
INDEX
Search Posts SEARCH
POSTS
Who's Online WHO'S
ONLINE
Log in LOG
IN

Home: Perl Programming Help: Beginner:
sorting numbers and string

 



jazzo
Novice

Aug 25, 2012, 2:16 PM

Post #1 of 7 (1059 views)
sorting numbers and string Can't Post

Hi all, here's a sorting script, not quite sure I understandthe mechanism though:

Code
 
#!/usr/bin/perl
#sort3.plx
use warnings;
use strict;
my @unsorted = (1, 2, 11, 24, 3, 36, 40, 4);
my @string = sort { $a cmp $b } @unsorted;
print "String sort: @string\n";
my @number = sort { $a <=> $b } @unsorted;
print "Numeric sort: @number\n";

Now first thing is: where are $a and $b coming from?
also not quite sure I understand how the number sorting works.
The <=> operator from what I have read returns -1 0 or 1 depending whether the first number is smaller, equal or greater than the second one. So how does the comparison work? let's take the first 2 numbers: 1 and 2.

Code
1<=>2

returns -1 and then what?
thanks


BillKSmith
Veteran

Aug 25, 2012, 8:41 PM

Post #2 of 7 (1057 views)
Re: [jazzo] sorting numbers and string [In reply to] Can't Post

Please read the documentation perldoc -f sort. Your example is using the BLOCK LIST form. Braces {} surround the BLOCK. The LIST is the values of the unsorted array. The variables $a and $b are special global variables in perl. They are only used in block part of sort. The sort routine assigns values from the list to $a and $b. It executes the block to find out which should come first in the sorted list (This is done many times in a single run of sort)

The operators cmp and <=> are rarely used anywhere but in a sort block. They both return -1 to tell sort that $a belongs before $b, 0 if we do not care which is first, and 1 if $a belongs after $b. Your example is designed to demonstrate the difference between them. Cmp puts strings in order and <=> puts numbers in order. (cmp would but 10 before 2 because it puts the one before the two.)
Good Luck,
Bill


Laurent_R
Veteran / Moderator

Aug 26, 2012, 12:55 AM

Post #3 of 7 (1055 views)
Re: [jazzo] sorting numbers and string [In reply to] Can't Post

Not much to add, but just a couple of examples.

If you try this:


Code
 print 1 <=> 2;


this will print -1 because 1 should be before 2 un a numerical sort. If you do it the other way arounf, it will print 1.

The main point is that the sort function expects a negative value is $a should be before $b, a positive value is $a should be after $b and a zero value if $a and $b should be considered equal. You can write your own block for specific comparisons, provided it return positive, zero and negative values as described above.

For example, you could rewrite


Code
my @number = sort { $a <=> $b } @unsorted;


as:


Code
my @number = sort { $a - $b } @unsorted;

and get the same results, since $a - $b will be negative if a < $b, nought if $a = $b and positive if $a > $b.


jazzo
Novice

Aug 26, 2012, 3:07 PM

Post #4 of 7 (1048 views)
Re: [Laurent_R] sorting numbers and string [In reply to] Can't Post

thanks guys. Needless to say, I am very happy to read the documentation, but I have no idea where to find, could you kindly let me know how to get to it? Sorry I am really really new to perl.

Also, to get back to the script: what it does in in theory clear, and it is better now that you added more info to it, but practically, I don't understand how many times this line

Code
my @number = sort { $a <=> $b } @unsorted;

runs. It must compare 2 numbers at each pass, so I assume it runs 4 times comparing respectively the 1st and 2nd, the 3rd and 4th, 5th and 6th, 7th and 8th number, or not? so comparison between 1 and 2 returns -1 because as you have said

Quote
a belongs before b

, then 11 and 24 returns -1 again and then what happens? 3 is smaller than 11 so does it get compared against it?
thanks


BillKSmith
Veteran

Aug 26, 2012, 5:24 PM

Post #5 of 7 (1044 views)
Re: [jazzo] sorting numbers and string [In reply to] Can't Post

Perl comes with extensive documentation and a tool (perldoc) to access it. To get directions for perldoc, at the command line of your computer, type:

Code
perldoc perldoc

I already gave you the command to access the documentation for sort.

Code
perldoc -f sort


The line containing the call to sort only runs once. However, the block portion of it is called many more than four times. It is not at all necessary to know how many.

Nor is it necessary to know how sort works. The documentation tells us that it uses the quicksort algorithm. You would have to consult a computer science text to find a description of that algorithm. The algorithm dictates which pairs of values must be compared. (Note: the algorithm does not work at all the way you seem to think it does)

All you have to do to use sort is to write a block that returns the right number (-1, 0, or +1) for any pair of values.
Good Luck,
Bill


Laurent_R
Veteran / Moderator

Aug 27, 2012, 12:35 AM

Post #6 of 7 (1042 views)
Re: [BillKSmith] sorting numbers and string [In reply to] Can't Post

From Perl 5.8 on, the sorting algorithm used is actually mergesort (it was quick sort until version 5.6). Well, at least, mergesort is the default, you can still ask for quicksort if so you wish.

The number of times the block is executed is typically in the order of n log n for an array of n elements. That could be something like 3,000 to 5,000 times for an array of 1,000 elements.


(This post was edited by Laurent_R on Aug 27, 2012, 12:38 AM)


jazzo
Novice

Aug 27, 2012, 4:57 AM

Post #7 of 7 (1037 views)
Re: [Laurent_R] sorting numbers and string [In reply to] Can't Post

fantastic thanks you all for your help

 
 


Search for (options) Powered by Gossamer Forum v.1.2.0

Web Applications & Managed Hosting Powered by Gossamer Threads
Visit our Mailing List Archives