Looking for an edge with the classic Quicksort algorithm

Smart Sort

© Lead Image © Olga Yastremska, 123RF.com

© Lead Image © Olga Yastremska, 123RF.com

Article from Issue 246/2021
Author(s):

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.

[...]

Use Express-Checkout link below to read the full article (PDF).

Buy this article as PDF

Download Article PDF now with Express Checkout
Price $2.95
(incl. VAT)

Buy Linux Magazine

SINGLE ISSUES
Print Issues
Digital Issues
SUBSCRIPTIONS
Print Subscriptions
Digital Subscriptions

Related content

  • Sorted

    Whether alphabetical or numerical, bubble sort or quicksort, there is no escape from sorting in computer science. In this month's column, Mike Schilli sorts out the pros and cons of various sorting algorithms in Go.

    more »
  • Julia

    Parallel processing is indispensable today – particularly in the field of natural sciences and engineering. Normal desktop users, however, can also benefit from higher performance through parallel execution with at least four calculation cores.

    more »
  • LibreOffice Calc Pivot Tables

    Pivot tables let you sort, rearrange, group, and perform calculations on your spreadsheet data. We help you get started with this powerful tool.

    more »
  • KNIME

    They say data is "the new oil," but all that data you collect is only valuable if it leads to new insights. An open source analysis tool called KNIME lets you analyze data through graphical workflows – without the need for programming or complex spreadsheet manipulation.

    more »
  • Developing a Trojan Horse

    Malicious Trojan horse programs have been part of the IT landscape for decades. It is easier than you think to create an application with a secret purpose. We'll show you how.

    more »
comments powered by Disqus
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.

Learn More

News

Tag Cloud

Administration Community Desktop Events Hardware Linux Mobile Programming Security Software Ubuntu Web Development Windows free software open source