Sort (C++)


Sort (C++)

sort is a function in C++ Standard Template Library that takes two random-access iterators, the start and the end, as arguments and performs a comparison sort on the range of elements between the two iterators, front-inclusive and end-exclusive. The underlying algorithm is (usually) introsort, which is a combination of quicksort and heapsort (the implementation details are not mandated). Whatever the implementation, the complexity is guaranteed to be O("n" log "n") comparisons in the worst case.

sort is specified in the algorithm header file.

Usage

The sort function is included from the algorithm header of the Standard Template Library, and carries three arguments: iterator start, iterator end, function compare. The third argument has default value - the "less-than" (<) operator to compare elements.

This code sample sorts given array of integers (in ascending order) and print it out. Pointers into the array serve as iterators.

#include #include int main() { int array [] = { 23, 5, -10, 0, 0, 321, 1, 2, 99, 30 }; int elements = sizeof(array) / sizeof(array [0] ); std::sort(array, array + elements); for (int i = 0; i < elements; ++i) std::cout << array [i] << ' '; }

The same functionality using vector container:

#include #include #include int main() { std::vector vec; vec.push_back(10); vec.push_back(5); vec.push_back(100); std::sort(vec.begin(), vec.end()); for (int i = 0; i < vec.size(); ++i) std::cout << vec [i] << ' '; }

Other types of sorting

sort is not stable: equivalent elements that are ordered one way before sorting may be ordered differently after sorting. stable_sort ensures stability of result at expense of worse performance (in some cases). Result of partial_sort is N sorted elements from M, the rest (M - N) is left in undefined order. Depending on design this may be faster than complete sort.

Some containers, among them list (part of STL), provide specialised version of sort as a member function. This is because linked lists don't have random access (and therefore can't use the regular sort function); and the specialised version also preserves the values list iterators point to.

Comparison to qsort()

sort() can be compared to the qsort() function in the C standard library (in stdlib.h), which performs a quicksort. sort is guaranteed to be O(N log N) in the worst case, which is better than qsort, which has O(N^2) worst case. (quick sort algorithm has O(N log N) complexity at average.) sort is templated, so it uses the correct comparison function for whatever data type you are sorting, which is already implemented for standard data types. Otherwise you can specify your own comparison function, which can be type-checked by the compiler; whereas for qsort, you must manually cast pointers to the desired type in an unsafe way. Also, qsort accesses the comparison function using a function pointer, necessitating large numbers of repeated function calls, which can take a lot of time; whereas in C++, comparison functions are usually inlined, removing the need for function calls. In practice, C++ code using sort is often many times faster at sorting simple data like integers than equivalent C code using qsort.

ee also

*Standard Template Library

External links

* [http://www.sgi.com/tech/stl/sort.html SGI STL specification of sort() function]


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • sort — sort …   Dictionnaire des rimes

  • sort — [ sɔr ] n. m. • 1080; lat. sors, sortis 1 ♦ Effet magique, généralement néfaste, qui résulte de certaines opérations de sorcellerie. ⇒ 2. charme, ensorcellement, jettatura, maléfice, sortilège (cf. Mauvais œil). Jeter un sort à qqn. ⇒ ensorceler …   Encyclopédie Universelle

  • Sort — Sort, n. [F. sorie (cf. It. sorta, sorte), from L. sors, sorti, a lot, part, probably akin to serere to connect. See {Series}, and cf. {Assort}, {Consort}, {Resort}, {Sorcery}, {Sort} lot.] 1. A kind or species; any number or collection of… …   The Collaborative International Dictionary of English

  • sort — Sort, Cleros, siue Clerus. Sort ou fortune, Sors sortis. Le sort et principal d une somme d argent, Sors. Faire sort, ou jetter le sort, Sortiri, Sortem ducere. Jetter le sort entre aucuns, lequel d entre eux aura quelque chose, Sortiri aliquibus …   Thresor de la langue françoyse

  • sort — [sɔːt ǁ sɔːrt] noun [countable] COMPUTING if a computer does a sort, it puts things in a particular order: • If you do a sort on the computer, it will list entries in alphabetical order. sort verb [intransitive, transitive] : • You can sort these …   Financial and business terms

  • sort — UNIX‐утилита, выводящая сортированное слияние указанных файлов на стандартный вывод с использованием установленной в среде локали. Использование sort [ m][ o output][ bdfinru][ t char][ k keydef]… [file…] sort c [ bdfinru][ t char][ k… …   Википедия

  • Sort — may mean * Sorting, any process of arranging items in sequence or in sets ** In conveyor lines sortage is the term for a checkweigher sorting products. ** Sorting algorithm, a computer process for arranging elements in lists ** Sort (Unix), a… …   Wikipedia

  • Sort — UNIX‐утилита, выводящая сортированное слияние указанных файлов на стандартный вывод с использованием установленной в среде локали. Использование sort [ m][ o output][ bdfinru][ t char][ k keydef]… [file…] sort c [ bdfinru][ t char][ k… …   Википедия

  • sort — ► NOUN 1) a category of people or things with a common feature or features. 2) informal a person with a specified nature: a friendly sort. 3) Computing the arrangement of data in a prescribed sequence. ► VERB 1) arrange systematically in groups.… …   English terms dictionary

  • SORT — steht für Sort (Lleida), eine Kleinstadt in Katalonien Sort (Unix), ein Unix Programm zum Sortieren Sort (Windows), ein Windows Programm zum Sortieren SORT steht als Abkürzung für: Special Operations Response Team, eine Spezialeinheit des US… …   Deutsch Wikipedia


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.