Looking for an edge with the classic Quicksort algorithm
Smart Sort
If you wanted to assign a flavor to the Quicksort algorithm, it would be sweet and sour. Sweet, because it is very elegant; sour, because typical implementations sometimes leave more questions than they answer.
The Quicksort sorting algorithm has been around for 60 years, and, if implemented properly, it is still the fastest option for many sorting tasks. According to the description on Wikipedia, a well designed Quicksort is "…somewhat faster than Merge sort and about two or three times faster than Heapsort."
Many Linux users today have studied Quicksort at some point in the past, through a computer science class or other training scenario, but unless you are working as a professional programmer, chances are it has been a few years since you have taken the time to ponder the elegant Quicksort algorithm. Still, sorting goes on all the time on Linux networks. You don't have to be a fulltime app developer to conjure up an occasional script to rank results or order a set of values extracted from a log file. This article explores some of the nuances of the classic Quicksort.
Quicksort ABC
The Quicksort [1] algorithm originated with Tony Hoare [2], who first developed it in 1959 and published it in 1961. Quicksort is what is known as a divideandconquer algorithm. One element in the array is chosen to be the pivot element. All elements smaller than the pivot element are then grouped in a subarray before it, and all elements larger than the pivot element are placed in a subarray after it. This process is then repeated with the subarrays: a pivot element is chosen, with smaller elements placed in a subarray before and larger elements placed in a subarray after. After a finite number of steps, the size of the subarrays becomes one, and at that point, the whole array has been sorted.
Too complicated? Figure 1 sums up the Quicksort algorithm. Boxes containing only one red number are already in the right position. In the first row, the number 6 is the pivot element. Now all of the elements are sorted in relation to 6. In the second row, the 5 and the 9 act as the new pivot elements. Now the partial arrays are sorted relative to 5 and 9. The result is the third row, where almost all of the elements are already sorted. Only the 8 (the new pivot element) has to swap places with the 7. If you would prefer an animated clip of the Quicksort algorithm, check out the Quicksort page on Wikipedia [1].
If the array contains n elements, an average of n*log(n) sorting steps are needed. The log(n) factor results from the fact that the algorithm halves the array in each step. In a worstcase scenario, Quicksort requires n*n sorting steps. To illustrate this worstcase scenario, consider that, in Figure 1, the middle element served as the pivot element. But any other element could also serve as the pivot element. If the first element is the pivot element and the array is already sorted in ascending order, the array must be halved exactly n times, which would be the (very unlikely) worst case. Note that a few lines of text are all I needed to describe the elegant and highly efficient Quicksort algorithm, along with its performance characteristics.
First Encounter
The classic Quicksort implementation in C lacks charm and is quite successful at disguising its elegant design, as Listing 1 demonstrates. I won't provide a full description of the code; however, one observation is very interesting.
Listing 1
Quicksort in C
01 void quickSort(int arr[], int left, int right) { 02 int i = left, j = right; 03 int tmp; 04 int pivot = arr[abs((left + right) / 2)]; 05 while (i <= j) { 06 while (arr[i] < pivot) i++; 07 while (arr[j] > pivot) j; 08 if (i <= j) { 09 tmp = arr[i]; 10 arr[i] = arr[j]; 11 arr[j] = tmp; 12 i++; j; 13 } 14 } 15 if (left < j) quickSort(arr, left, j); 16 if (i < right) quickSort(arr, i, right); 17 }
In Lines 9 to 11, the code overwrites the existing elements. Thus, the algorithm runs inplace and assumes mutable data. A nice expression has been established for the task of overwriting old values with new ones in functional programming: destructive assignment [3]. This takes us neatly to the next topic: in functional programming languages like Haskell, Quicksort is represented in a far more elegant way.
Second Encounter
In Haskell, data is immutable, which precludes destructive assignment by design. The Haskellbased Quicksort algorithm in Listing 2 creates a new list in each iteration, rather than acting directly on the array as in Listing 1. Quicksort in two lines? Is that all there is to it? Yes.
Listing 2
Quicksort in Haskell
qsort [] = [] qsort (x:xs) = qsort [y  y < xs, y < x] ++ [x] ++ qsort [y  y < xs, y >= x]
The qsort
algorithm consists of two function definitions. The first line applies the defined Quicksort to the empty list. The second line represents the general case, where the list consists of at least one element: x:xs
. Here, by convention, x
denotes the beginning of the list and xs
denotes the remainder.
The strategy of the Quicksort algorithm can be implemented almost directly in Haskell:
 use the first element of the list
x
as the pivot element;  insert (
(++)
) all elements inxs
that are lesser thanx
((qsort [y  y < xs, y < x])
) in front of the oneelement list[x]
;  append all elements in
xs
that are at least as large asx
to the list[x]
((qsort [y  y < xs, y >= x])
).
The recursion ends when Quicksort is applied to the empty list. Admittedly, the compactness of Haskell seems unusual. However, this Quicksort algorithm can be implemented in any programming language that supports list comprehension – which leads to the more mainstream Python programming language in Listing 3.
Listing 3
Quicksort in Python
def qsort(L): if len(L) <= 1: return L return qsort([lt for lt in L[1:] if lt < L[0]]) + L[0:1] + qsort([ge for ge in L[1:] if ge >= L[0]])
The description of the Haskell algorithm can be applied almost verbatim to Python. The subtle difference is that in Python, L[0:1]
acts as the first element and you express the list concatenation in Python with the +
symbol. The algorithm reliably performs its services in Figure 2.
Buy this article as PDF
(incl. VAT)
Buy Linux Magazine
Subscribe to our Linux Newsletters
Find Linux and Open Source Jobs
Subscribe to our ADMIN Newsletters
Support Our Work
Linux Magazine content is made possible with support from readers like you. Please consider contributing when you’ve found an article to be beneficial.
News

SUSE Offers CentOS 7 Spport with Liberty Linux Lite
SUSE's Liberty Linux support offering now includes CentOS 7, which means businesses won't be forced to migrate those servers for some time.

Ubuntu's App Center Finally Supports Local Installs Again
If you regularly download .deb files and would prefer a GUI method of installing, Ubuntu has your back.

AlmaLinux Now Supports Raspberry Pi 5
If you're looking to create with the Raspberry Pi 5 and want to use AlmaLinux as your OS, you're in luck because it's now possible.

Kubuntu Focus Releases New Iterations of Ir14 and Ir16 Laptops
If you're a fan of the Kubuntu Focus laptops or have been waiting for the right time to purchase one, that time might be now.

NixOS 24.05 Is Ready for Prime Time
The latest release of NixOS (Uakari) has arrived and offers its usual reproducible, declarative, and reliable goodness.

Linux Lite 7.0 Officially Released
Based on Ubuntu 24.04 and kernel 6.8, Linux Lite version 7 now offers more options than ever.

KaOS Linux 2024.05 Adds Bcachfs Support and More
With updates all around, KaOS Linux now includes support for the bcachefs file system.

TUXEDO Computers Unveils New Iteration of the Stellaris Laptop Line
The Stellaris Slim 15 is the 6th generation and includes either an AMD or Intel CPU

KDE Releases Plasma 6.0.5
The latest release of the Plasma desktop has arrived with several improvements and the usual bug fixes.

Gnome OS Adopting systemdsysupdate
Gnome OS is about to undergo a major underthehood change that promises enhanced security.