(redirected from Q sort)


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.