Sorting Algorithm Tutorials - Herong's Tutorial Examples - 6.12, by Herong Yang
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) 2015 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
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
ß