laziness, impatience, and hubris PerlMonks

### Re: Pugs now works - but how?

by pernod (Chaplain)
 on Feb 18, 2005 at 22:56 UTC ( #432561=note: print w/replies, xml ) Need Help??

in reply to Pugs now works - but how?
in thread Hello Perl 6. Running pugs on Windows

Can someone explain me very briefly how the code in the reply of autrijus (It now works. :)) operates?

I'll give it a shot :)

```1: multi sub quicksort ( ) { () }
2: multi sub quicksort ( *\$x, *@xs ) {
3:     my @pre  = @xs.grep{ \$_ < \$x };
4:     my @post = @xs.grep{ \$_ >= \$x };
5:     (@pre.quicksort, \$x, @post.quicksort);
6: }
7: (1, 5, 2, 4, 3).quicksort.say;

I'll assume you're familiar with the quicksort algorithm already, and the way it uses pivots. The first line states how we sort an empty list. Which is simply to return the empty list. This serves as the case for breaking recursion and avoiding infinite looping.

Line two defines a head and a tail, where the head \$x is the first element in the list ('1' in the case of the call at line 7), while the tail @xs contains the remaining elements. Line 3 declares a list which contains all the elements from the tail that have a value smaller than \$x.

@pre = @xs.grep{ \$_ < \$x } applies the built-in function grep to the tail. grep returns only the elements in @xs that are smaller than \$x and puts them into @pre. This list is still unordered, but we now know that all the values in @pre are smaller than the pivot \$x. Similarily for @post, but here we have all the bigger elements.

The magic kicks in at line 5, where we assemble the parts into a new list with the pivot in the middle. Remember though, that @pre and @post are as yet unsorted, so we apply quicksort to them recursively before we return the concatenated list.

Line 7 applies quicksort to a list, and then prints it to screen with the say. Say, I presume, is something similar to Haskell's show and Java's toString().

Clear as ink :D

pernod
--
Mischief. Mayhem. Soap.

Replies are listed 'Best First'.
Re^2: Pugs now works - but how?
by awwaiid (Friar) on Feb 18, 2005 at 23:20 UTC

Perhaps also helpful is the close equivalent in Perl5. No magical multi-methods, and a bit more verbose... but not too shabby. Come to think of it this should work fine in Perl6 as well, eh?

```sub quicksort {
return unless @_;
my (\$x, @xs) = @_;
my @pre  = grep{ \$_ < \$x } @xs;
my @post = grep{ \$_ >= \$x } @xs;
(quicksort(@pre), \$x, quicksort(@post));
}

my @a = quicksort(1, 5, 2, 4, 3);
print "@a\n";
or more on a node, then I would immediately upvote both parents multiple times! These two were just the kind of enlightning nodes for which I like and regularly visit Perl Monks. This opened up a completely new way of thinking of programming for me...

Starting along the reply of awwaiid and pernod I have just finished the refactoring of one of my previous modules. The code is now much more concise, short and, perhaps most importantly, efficient as before. Thank you very much...

rg0now

Create A New User
Node Status?
node history
Node Type: note [id://432561]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others drinking their drinks and smoking their pipes about the Monastery: (4)
As of 2019-08-18 19:08 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
If you were the first to set foot on the Moon, what would be your epigram?

Results (135 votes). Check out past polls.

Notices?