Dropsort
Introduction
Dropsort is a fast, one-pass sorting algorithm suitable for many applications.
Algorithm Description
Dropsort is run on a list of numbers by examining the numbers in sequence, beginning with the second
number in the list. If the number being examined is less than the number before it, drop it from the list.
Otherwise, it is in sorted order, so keep it. Then move to the next number.
After a single pass of this algorithm, the list will only contain numbers that are at least as large as the
previous number in the list. In other words, the list will be sorted!
Analysis
Dropsort requires exactly n-1 comparisons to sort a list of length n, making this an O(n) algorithm,
superior to the typical O(n logn) algorithms commonly used in most applications.
Dropsort is what is known in the computer science field as a lossy algorithm. It produces a fast result that is
correct, but at the cost of potentially losing some of the input data. Although to those not versed in the arts of
computer science this may seem undesirable, lossy algorithms are actually a well-accepted part of computing. An
example is the popular JPEG image compression format, which enjoys widespread use because of its versatility and
usefulness. In similar fashion, dropsort promises to revolutionise the sorting of data in fields as diverse as
commercial finance, government record-keeping, and space exploration.
Resources
Jeremy Kent has implemented Dropsort! Well, sort of. (Pun intended.) In his own words:
It's an implementation of
a sorting algorithm with your DropSort at the core -- basically call
dropsort, keeping the dropped items... then reverse that list and call
dropsort again recursively. (Because obviously anything that wasn't in
ascending order before must be in descending order now.)
Get the python code here!
There is a dropsort implementing competition on Stack Exchange's Code Golf site.
Abram Jackson and Ryan McCulloch presented a paper on "Item Retention Improvements to Dropsort, a Lossy Sorting Algorithm", at the 2011 Midwest Instruction and Computing Symposium.
Emil Ernerfeldt has an implementation of the above-mentioned Drop-Merge Sort on GitHub.
Home | Esoteric Programming Languages
Last updated: Tuesday, 27 December, 2016; 14:43:03 PST.
Copyright © 1990-2022, David Morgan-Mar. dmm@dangermouse.net
Hosted by: DreamHost