Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

comment on

( #3333=superdoc: print w/replies, xml ) Need Help??
In QBASIC and JavaScript, the QSort algorithm is by far the fastest. It is even faster than the builtin sort() algorithm in JS. I tried to rewrite it to Perl, but I am not sure how to precisely measure its speed in Perl. The algorithm is designed to sort numbers:

#!/usr/bin/perl -w use strict; use warnings; print "Quick Sort algorithm ported from QBASIC to Perl.\n\n"; my @SAMPLE = ( 384, 12, 44, 847, 66, -324, 217, 550, -3, 18302, 136, 255, 441, 4.5, -5, 77, 101, -2, 12, 74, 3, 933, 50, -7, 61, 52, 902, 74, -23, 8, 32, 31, 32, 81, 22, -9, 65, 258, 71, -33, 433, 985, 164, -19, 0, 1, 0.2, 783, 92, 10, 343, 195, -1); PrintList("Unsorted list", @SAMPLE); my $START_TIME = time; QSort(@SAMPLE); # Sort list my $END_TIME = time; PrintList("Sorted List", @SAMPLE); print "This operation took ", ($END_TIME - $START_TIME), " second(s)\n +"; exit; sub PrintList { print shift, ":\n"; print '-' x 78 . "\n"; my $N; for (my $i = 1; @_; $i++) { $N = shift; print $N . "\t"; if (($i % 9) == 0) { print "\n"; } } print "\n", '-' x 78, "\n"; } # # QuickSort algorithm ported from QBASIC to Perl. # # Usage: QSort(ARRAY_OF_NUMBERS) # sub QSort { @_ or return; my $First = 0; my $Last = @_ - 1; my @QStack; my $StackPtr = 0; my $temp; my $i; my $j; for (;;) { do { $temp = $_[int(($Last + $First) / 2)]; $i = $First; $j = $Last; do { while ($_[$i] < $temp) { $i++; } while ($_[$j] > $temp) { $j--; } if ($i < $j) { @_[$i, $j] = @_[$j, $i]; } if ($i <= $j) { $i++; $j--; } } while ($i <= $j); if ($i < $Last) { $QStack[$StackPtr++] = $i; $QStack[$StackPtr++] = $Last; } $Last = $j; } while ($First < $Last); $StackPtr or return; $Last = $QStack[--$StackPtr]; $First = $QStack[--$StackPtr]; } }

In reply to Re: Fastest way to sort a list of integers into 0,1,2,3,-3,-2,-1 by harangzsolt33
in thread Fastest way to sort a list of integers into 0,1,2,3,-3,-2,-1 by haukex

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others exploiting the Monastery: (1)
As of 2021-10-21 03:25 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    My first memorable Perl project was:







    Results (82 votes). Check out past polls.

    Notices?