Quicksort

(redirected from Qsort)
Also found in: Acronyms.

Quicksort

A sorting algorithm with O(n log n) average time complexity.

One element, x of the list to be sorted is chosen and the other elements are split into those elements less than x and those greater than or equal to x. These two lists are then sorted recursively using the same algorithm until there is only one element in each list, at which point the sublists are recursively recombined in order yielding the sorted list.

This can be written in Haskell:

qsort :: Ord a => [a] -> [a] qsort [] = [] qsort (x:xs) = qsort [ u | u<-xs, u<x ] ++ [ x ] ++ qsort [ u | u<-xs, u>=x ]

[Mark Jones, Gofer prelude.]
This article is provided by FOLDOC - Free Online Dictionary of Computing (foldoc.org)

quick sort

A sorting technique that sequences a list by continuously dividing the list into two parts and moving the lower items to one side and the higher items to the other. It starts by picking one item in the entire list to serve as a pivot point. The pivot could be the first item or a randomly chosen one. All items that compare lower than the pivot are moved to the left of the pivot; all equal or higher items are moved to the right. It then picks a pivot for the left side and moves those items to left and right of the pivot and continues the pivot picking and dividing until there is only one item left in the group. It then proceeds to the right side and performs the same operation again. See sort algorithm.


Quick Sorting a List
This quick sort uses randomly chosen pivots (in red) to keep dividing the list into two until there is only one item on each side of the pivot left.
Copyright © 1981-2019 by The Computer Language Company Inc. All Rights reserved. THIS DEFINITION IS FOR PERSONAL USE ONLY. All other reproduction is strictly prohibited without permission from the publisher.
Mentioned in ?
References in periodicals archive ?
* Clicks on the topmost Qsort node, causing the fine-grained information:
call: qsort ([4, 1, 2, 3], _ans) exit: qsort ([4, 1, 2, 3], [3, 1, 2, 4])
should be exit: qsort ([4, 1, 2, 3], [1, 2, 3, 4]).
qsort. This is one of the five benchmarks in Warren [1977].
Reuse Code Program Total Data Flow Analysis Synthesis app 8.7 - 8.9 2.2 - 2.3 2.1 - 2.6 3.7 - 3.8 deriv 15.9 - 16.1 3.6 - 3.7 6.5 - 6.6 5.7 - 5.8 gauss 7.6 - 7.7 1.7 - 1.9 2.2 - 2.9 3.1 - 3.6 trans 14.6 - 16.5 4.1 - 4.7 7.2 - 7.7 5.8 - 5.9 qsort 14.6 - 15.2 3.7 - 3.9 5.5 - 5.8 5.8 - 6.0 9.4 Scheme
For the purposes of this article, it is unnecessary to provide the code of this procedure (see [44]); qsort (L, S) sorts an input list L by constructing the sorted list S.
empty unreachable Definition lines size factor time factor time map 5 221 3 <10 6 20 reverse 6 287 4 <10 8 20 substring 8 579 12 10 64 10 qsort 41 1387 15 <10 15 30 unify 89 2921 10 10 11 80 hopcroft 201 8429 25 10 42 100 check 237 21854 4 50 4 1150 escher-fish 493 30509 187 10 678 40 scanner 1209 59215 3 180 17 840 [Epsilon-removal] Hopcroft Definition factor time factor time map 11 30 13 30 reverse 20 10 20 30 substring 64 10 96 20 qsort 58 50 66 40 unify 55 120 65 150 hopcroft 118 100 124 200 check 26 370 168 540 escher-fish 678 40 678 80 scanner 45 2450 57 2120 The results demonstrate the effectiveness of our simplification algorithms.
The initial 5 hours included a false start: The first version sorted the words by making list (in function printwords) an array of pointers to words and calling the C library function qsort to sort them.
Normalized CPU Times for Executing Standard Prolog Benchmarks deriv qsort nreverse WAM 1 1 1 SLG-WAM: WJM-trail 1.10 1.10 1.04 SLG-WAM: Definite 1.16 1.11 1.05 SLG-WAM: LRD 1.16 1.11 1.05 serialise query Mean WAM 1 1 1 SLG-WAM: WJM-trail 1.04 1.09 1.08 SLG-WAM: Definite 1.09 1.13 1.13 SLG-WAM: LRD 1.09 1.13 1.13 For qsort, nreverse, and query the increase in time appears to be due to the addition of the freeze registers, while for serialise it is due to writing trail cells.