Looking for an edge with the classic Quicksort algorithm
Smart Sort
© Lead Image © Olga Yastremska, 123RF.com
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 full-time 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 divide-and-conquer 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 sub-array before it, and all elements larger than the pivot element are placed in a sub-array after it. This process is then repeated with the sub-arrays: a pivot element is chosen, with smaller elements placed in a sub-array before and larger elements placed in a sub-array after. After a finite number of steps, the size of the sub-arrays becomes one, and at that point, the whole array has been sorted.
[...]
Buy this article as PDF
(incl. VAT)
Buy Linux Magazine
US / Canada
UK / Australia
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
-
New Linux Tool for Security Issues
Seal Security is launching a new solution to automate fixing Linux vulnerabilities.
-
Ubuntu 25.04 Coming Soon
Ubuntu 25.04 (Plucky Puffin) has been given an April release date with many notable updates.
-
Gnome Developers Consider Dropping RPM Support
In a move that might shock a lot of users, the Gnome development team has proposed the idea of going straight up Flatpak.
-
openSUSE Tumbleweed Ditches AppArmor for SELinux
If you're an openSUSE Tumbleweed user, you can expect a major change to the distribution.
-
Plasma 6.3 Now Available
Plasma desktop v6.3 has a couple of pretty nifty tricks up its sleeve.
-
LibreOffice 25.2 Has Arrived
If you've been hoping for a release that offers more UI customizations, you're in for a treat.
-
TuxCare Has a Big AlmaLinux 9 Announcement in Store
TuxCare announced it has successfully completed a Security Technical Implementation Guide for AlmaLinux OS 9.
-
First Release Candidate for Linux Kernel 6.14 Now Available
Linus Torvalds has officially released the first release candidate for kernel 6.14 and it includes over 500,000 lines of modified code, making for a small release.
-
System76 Refreshes Meerkat Mini PC
If you're looking for a small form factor PC powered by Linux, System76 has exactly what you need in the Meerkat mini PC.
-
Gnome 48 Alpha Ready for Testing
The latest Gnome desktop alpha is now available with plenty of new features and improvements.