Quicksort - Implementation in Perl

This section provides a tutorial on how to implement the Quicksort algorithm in Perl.

Quicksort is a complex and fast sorting algorithm that repeatedly divides an un-sorted section into a lower order sub-section and a higher order sub-section by comparing to a pivot element. The Quicksort algorithm was developed in 1960 by Tony Hoare while in the Soviet Union, as a visiting student at Moscow State University.

The basic idea of Quicksort algorithm can be described as these steps:

1. Select an element as a pivot element.

2. Data elements are grouped into two sections: one with elements that are in lower order than the pivot element, one with element that are in higher order than the pivot element.

3. Sort the two sections separately by repeating step 1 and 2.

Obviously, this is a recursive idea, where a problem is divided into smaller problems. And the division will be repeated to make the smaller problems even smaller, until they are smaller enough so that the solution is obvious.

Here is my Perl implementation of Quicksort algorithm:

```#- Sort_Function.pl
#-
sub quickSort {
my (\$a, \$fromIndex, \$toIndex) = @_;
if (\$toIndex-\$fromIndex<=1) {        # only 1 elements
return;
} elsif (\$toIndex-\$fromIndex==2) {   # 2 elements
if ((\$a->[\$fromIndex])>\$a->[\$toIndex-1]) {
\$d = \$a->[\$toIndex-1];
\$a->[\$toIndex-1] = \$a->[\$fromIndex];
\$a->[\$fromIndex] = \$d;
}
} else {                             # 3 or more elements
\$p = \$a->[\$fromIndex];             # the pivot value
\$iLeft = \$fromIndex + 1;
\$iRight = \$toIndex - 1;
while (\$iLeft<\$iRight) {
while (\$iLeft<\$toIndex-1 && \$p>=\$a->[\$iLeft]) {
\$iLeft++;                      # most left element that > pivot
}
while (\$iRight>\$fromIndex+1 && \$p<=\$a->[\$iRight]) {
\$iRight--;                     # most right element that < pivot
}
last if (\$iLeft>=\$iRight);       # stop condition
\$d = \$a->[\$iRight];              # swap them and continue
\$a->[\$iRight] = \$a->[\$iLeft];
\$a->[\$iLeft] = \$d;
}
if (\$p>\$a->[\$iRight]) {           # have elements < pivot
\$d = \$a->[\$iRight];              # swap a[iRight] with pivot
\$a->[\$iRight] = \$a->[\$fromIndex];
\$a->[\$fromIndex] = \$d;
} else {                           # no element < pivot
\$iRight--;
}
quickSort(\$a, \$fromIndex, \$iRight) if (\$fromIndex<\$iRight-1);
quickSort(\$a, \$iLeft, \$toIndex) if (\$iLeft<\$toIndex-1);
}
}

# Functions for other sorting algorithms ...

#- End
1;
```

Here are the performance test results of quickSort() function using Perl 5.18

```Array size: 10000
Average sorting time: 68.74150390625 milliseconds
Number of tests: 10
Performance: 6.874150390625 O(N) microseconds
Performance: 0.51733136557085 O(N*Log2(N)) microseconds
Performance: 0.0006874150390625 O(N*N) microseconds

Array size: 20000
Average sorting time: 150.018408203125 milliseconds
Number of tests: 10
Performance: 7.50092041015625 O(N) microseconds
Performance: 0.524991000021291 O(N*Log2(N)) microseconds
Performance: 0.000375046020507812 O(N*N) microseconds

Array size: 30000
Average sorting time: 240.884765625 milliseconds
Number of tests: 10
Performance: 8.0294921875 O(N) microseconds
Performance: 0.539882183409492 O(N*Log2(N)) microseconds
Performance: 0.000267649739583333 O(N*N) microseconds
```

Here is the comparison of quickSort() performance with other sorting functions. As you can see, Quicksort is much faster than other sorting functions.

```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
Quicksort            69     150     241
Insertion Sort     4125   16015   37098
Selection Sort     8054   31249   68985
Bubble Sort       19344   78360  177353
```