Re: 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];
  }
}
[download]

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

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 (Patriarch) on Feb 06, 2019 at 08: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.	[reply] [d/l]
Re^2: Fastest way to sort a list of integers into 0,1,2,3,-3,-2,-1 by haukex (Archbishop) on Feb 08, 2019 at 09: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% --` [download] Where `qsort` is from List::MoreUtils. Read more... code (5 kB)	[reply] [d/l] [select]


The stupid question is the question not asked
	PerlMonks