Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
PerlMonks  

Re: Fastest way to sort a list of integers into 0,1,2,3,-3,-2,-1

by harangzsolt33 (Friar)
on Feb 05, 2019 at 22:25 UTC ( #1229450=note: print w/replies, xml ) Need Help??


in reply to Fastest way to sort a list of integers into 0,1,2,3,-3,-2,-1

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]; } }

Replies are listed 'Best First'.
Re^2: Fastest way to sort a list of integers into 0,1,2,3,-3,-2,-1
by Corion (Pope) on Feb 06, 2019 at 03:59 UTC

    This thread, especially the top post, already contains the Benchmark and the usual scaffolding so you can easily test the speed (and correctness) of your implementation. Maybe consider using that.

    Also, I highly doubt that an implementation of Quicksort will beat the built-in sort keyword at least for the short lists that we are talking about here. Even though Perl sort uses a Mergesort, it will be hard for Perl code to beat the C code simply due to the amount of time spent in the Perl runloop.

Re^2: Fastest way to sort a list of integers into 0,1,2,3,-3,-2,-1
by haukex (Bishop) on Feb 08, 2019 at 04:12 UTC
    I am not sure how to precisely measure its speed in Perl.

    As Corion said, you can use Benchmark as I showed in the root node, and I also think that the built-in sort will always be faster. In fact, roughly 19 times faster:

    Rate custom qsort sort custom 10697/s -- -83% -95% qsort 62127/s 481% -- -70% sort 209474/s 1858% 237% --

    Where qsort is from List::MoreUtils.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://1229450]
help
Chatterbox?
and the web crawler heard nothing...

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







    Results (82 votes). Check out past polls.

    Notices?