Sorting
From
(→The Sorting Problem) |
|||
| Line 23: | Line 23: | ||
| - | <br>[[ | + | <br>[[CS2|Back to Data Structures (CS2)]] |
Revision as of 17:20, 26 March 2009
Sorting is one of the most studied areas of Computer Science. There are literally dozens of sorting algorithms. Sorting algorithms are divided along two dimensions: One dimension is simple sorts vs. advanced sorts. The other dimension is internal sorts vs. external sorts.
Internal sorts are sorting routines where the entire data to be sorted can be stored in the memory. An external sort is one where only part of the data to be sorted can fit into the memory.
A simple sort is characterized as one whose run time is O( N2 ) and which is best for small files, say 50 items or less. An advanced sort is one whose run time is O( N log2 N ) and which is best for large files.
The Sorting Problem
Given a set of records r1, r2, …, rn with keys k1, k2, …, kn respectively, arrange the records in an order S = <s1, s2, …, sn> such that records rs1 , rs2 , ..., rsn have keys obeying the property ks1 ≤ ks2 ≤ ... ≤ ksn, called ascending order or ks1 ≥ ks2 ≥ ... ≥ ksn, called descending order. Note that the sorting problem allows for duplicate keys.
A sorting algorithm is defined to be stable if the relative ordering between records with duplicate keys is maintained in the final ordering.
