Perl Guru Forums: Perl Programming Help: Beginner: sorting numbers and string

CGI/Perl Guide | Learning Center | Forums | Advertise | Login

Site Search: in


	MAIN INDEX	SEARCH POSTS	WHO'S ONLINE	LOG IN

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

jazzo
Novice

Aug 25, 2012, 2:16 PM

Post #1 of 7 (737 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 (735 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
Enthusiast

Aug 26, 2012, 12:55 AM

Post #3 of 7 (733 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 (726 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 (722 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
Enthusiast

Aug 27, 2012, 12:35 AM

Post #6 of 7 (720 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 (715 views)

Re: [Laurent_R] sorting numbers and string [In reply to]	Can't Post

fantastic thanks you all for your help

Search for (options)

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