Sorting
From
(Created page with 'Sorting is one of the most studied area of Computer Science. There are literally dozens of sorting algorithms. Sorting algorithms are divided along two dimensions: One dimension ...') |
(→The Sorting Problem) |
||
| Line 11: | Line 11: | ||
which is best for large files. | which is best for large files. | ||
| - | ==The Sorting Problem== | + | == The Sorting Problem == |
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
| - | A sorting algorithm is defined to be '''stable''' if the relative ordering between records with | + | Given a set of records r<sub>1</sub>, r<sub>2</sub>, …, r<sub>n</sub> with keys k<sub>1</sub>, k<sub>2</sub>, …, k<sub>n</sub> respectively, arrange the records in an order S = <s<sub>1</sub>, s<sub>2</sub>, …, s<sub>n</sub>> such that records r<sub>s1</sub> , r<sub>s2</sub> , ..., r<sub>sn</sub> have keys obeying the property k<sub>s1</sub> ≤ k<sub>s2</sub> ≤ ... ≤ k<sub>sn</sub>, called '''ascending order''' or k<sub>s1</sub> ≥ k<sub>s2</sub> ≥ ... ≥ k<sub>sn</sub>, called '''descending''' order'''. '''Note that the sorting problem allows for duplicate keys. |
| - | duplicate keys is maintained in the final ordering. | + | |
| + | A sorting algorithm is defined to be '''stable''' if the relative ordering between records with duplicate keys is maintained in the final ordering. | ||
Revision as of 14:54, 24 March 2009
Sorting is one of the most studied area 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.
