Sort_Test.pl - Sorting Performance Test

This section describes a sample test program, Sort_Test.pl, which can be used to test any sorting algorithm for data elements stored an array in Perl language.

If you like to program in Perl language, you may want to try to implement sorting algorithms in Perl. Here is my example of the sorting algorithm test program in Perl:

#- Sort_Test.pl
#- Copyright (c) HerongYang.com. All Rights Reserved.
#-
  use Time::HiRes qw(time);
  use Data::Dumper;
  do 'Sort_Function.pl';

  my ($arraySize, $numberOfTests) = @ARGV;
  $arraySize = 10 unless $arraySize;
  $numberOfTests = 1000 unless $numberOfTests;

  my $sortTime = 0;
  for (my $j=0; $j<$numberOfTests; $j++) {
    @dataArray = ();
    for (my $i=0; $i<$arraySize; $i++) {
      $dataArray[$i] = rand();
    }

    my $startTime = 1000*time();
    @dataArray = sort(@dataArray);
#    insertionSort(\@dataArray, 0, $arraySize);
#    selectionSort(\@dataArray, 0, $arraySize);
#    bubbleSort(\@dataArray, 0, $arraySize);
#    quickSort(\@dataArray, 0, $arraySize);
#    mergeSort(\@dataArray, 0, $arraySize);
#    heapSort(\@dataArray, 0, $arraySize);
#    shellSort(\@dataArray, 0, $arraySize);

#    print(Dumper(@dataArray));
    $sortTime += 1000*time() - $startTime;
  }
  $sortTime = $sortTime/$numberOfTests;

  print("Array size: $arraySize\n");
  print("Average sorting time: $sortTime milliseconds\n");
  print("Number of tests: $numberOfTests\n");
  printTimeInfo($sortTime, $arraySize);

sub printTimeInfo {
  my ($t, $n) = @_;
  my $nFactor = $t/($n/1000);
  my $nnFactor = $t/(($n/1000)*$n);
  my $log2n = log($n)/log(2.0);
  my $ngFactor = $t/(($n/1000)*$log2n);
  print("Performance: $nFactor O(N) microseconds\n");
  print("Performance: $ngFactor O(N*Log2(N)) microseconds\n");
  print("Performance: $nnFactor O(N*N) microseconds\n");
}

Note that:

Before implementing my own versions of different sorting algorithms, I used the above test program to get some performance results with the built-in sort() function provided by Perl 5.18. Here are the results:

herong> perl -version
This is perl 5, version 18, subversion 2 (v5.18.2) built
for darwin-thread-multi-2level
Copyright 1987-2013, Larry Wall

herong> perl Sort_Test.pl 10000
  Array size: 10000
  Average sorting time: 10.6218154296875 milliseconds
  Number of tests: 1000
  Performance: 1.06218154296875 O(N) microseconds
  Performance: 0.0799371263185609 O(N*Log2(N)) microseconds
  Performance: 0.000106218154296875 O(N*N) microseconds

herong> perl Sort_Test.pl 20000
  Array size: 20000
  Average sorting time: 21.9370893554687 milliseconds
  Number of tests: 1000
  Performance: 1.09685446777344 O(N) microseconds
  Performance: 0.0767690753170121 O(N*Log2(N)) microseconds
  Performance: 5.48427233886719e-05 O(N*N) microseconds

herong> perl Sort_Test.pl 30000
  Array size: 30000
  Average sorting time: 36.1204841308594 milliseconds
  Number of tests: 1000
  Performance: 1.20401613769531 O(N) microseconds
  Performance: 0.0809549154666525 O(N*Log2(N)) microseconds
  Performance: 4.01338712565104e-05 O(N*N) microseconds

herong> perl Sort_Test.pl 100000
  Array size: 100000
  Average sorting time: 170.799684570313 milliseconds
  Number of tests: 1000
  Performance: 1.70799684570313 O(N) microseconds
  Performance: 0.102831656611221 O(N*Log2(N)) microseconds
  Performance: 1.70799684570313e-05 O(N*N) microseconds

The result was not very impressive comparing the Java and PHP languages. For example, the Java version took 25 milliseconds for array size of 100000, but the Perl version took 171 milliseconds for the same array size. So I lower the array size to 10000, 20000 and 30000 to build the performance baseline.

Array Size        10000   20000   30000   100000   200000   300000
----------        -----   -----   -----   ------   ------   ------
JDK Arrays.sort                               25       66      112
PHP sort()            3       7      13       75
Perl sort()          11      22      36      171

Table of Contents

 About This Book

 Introduction of Sorting Algorithms

 Java API for Sorting Algorithms

 Insertion Sort Algorithm and Java Implementation

 Selection Sort Algorithm and Java Implementation

 Bubble Sort Algorithm and Java Implementation

 Quicksort Algorithm and Java Implementation

 Merge Sort Algorithm and Java Implementation

 Heap Sort Algorithm and Java Implementation

 Shell Sort Algorithm and Java Implementation

 Sorting Algorithms Implementations in PHP

Sorting Algorithms Implementations in Perl

Sort_Test.pl - Sorting Performance Test

 Insertion Sort - Implementation in Perl

 Selection Sort - Implementation in Perl

 Bubble Sort - Implementation in Perl

 Quicksort - Implementation in Perl

 Merge Sort - Implementation in Perl

 Heap Sort - Implementation in Perl

 Shell Sort - Implementation in Perl

 Sorting Algorithms Implementations in Python

 Performance Summary of All Implementations

 References

 Full Version in PDF/EPUB

ß