Sorting Algorithm Tutorials - Herong's Tutorial Examples - 6.12, by Herong Yang
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 #- Copyright (c) 2015 HerongYang.com. All Rights Reserved. #- 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
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