Quicksort

(redirected from Qsort)

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.]
Mentioned in ?
References in periodicals archive ?
These programs are qsort (which performs the algorithm of quick sort), isqrt (which is base two analogue of the square root algorithm), cubic (which solves a cubic polynomial), rad2deg (which converts between radians and degrees), crc (which computes 32-bit crc to detect accidental changes to raw data), and bitstrng (which prints bit pattern of bytes formatted to string).
Some representative tasks such as mesa, ammp, quake, bzip, mcf, math, and qsort from MiBench [26] and SPEC CPU2000 [27] are selected as the benchmarks.
Algumas das mais citadas sao: metodos financeiros, metodos de estrategia de negocio, modelos de escore, checklists, arvore de decisao, comparacao por pares, modelos de indices economicos, programacao inteira, metodos de otimizacao (programacao linear inteira), QSort, modelos de otimizacao e os metodos de apoio multicriterio a decisao, como: teoria da utilidade, metodos TODIM, electre e promethee e o metodo de analise hierarquica (analytic hierarchy process--AHP), alem dos metodos hibridos: financeiros e de estrategia de negocio; e programacao linear inteira e AHP e metodos que utilizam inteligencia artificial (Chu, Hsu, Fehling et al.
Bem and Allen (1974) used Stephenson's (1953) Q-method to develop Qsort template-matching techniques, which help to indicate differences and correlations between two value systems, such as the conceptual fitting situation (Chatman, 1989; O'Reilly, Chatman, & Caldwell, 1991) or value fitting (Staw & Clausen, 1986) of an individual to an organization.
Tendo por referencia os criterios de seguranca e dependencia relativos a uma crianca ideal, definidos por um conjunto de peritos, estes dados foram correlacionados com a informacao recolhida atraves do perfil QSort, para se alcancarem resultados em ambos os construtos.
Also, subroutines REORDR, QSORT, and PERMUT were removed from the package, since it is no longer advantageous to presort the nodes.
In our scenario, Bill is writing a sorting program called Qsort, sorting a number of unsorted elements, based on the Quicksort algorithm, which splits a list around an element into a list of lower numbers and a list of higher numbers that are then recursively sorted.
The programs rev_shrt, deriv, gauss, mtx_add, qsort, and trans were timed using a SPARCserver 670MP with four Cypress, CY605 CPUs and 64MB of RAM.
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 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.