Understanding the problem
The sorting problem often arises in programming practice when we must to order a sequence of elements. The required order can be ascending or descending. Often, the ascending order is considered as default.
To represent sequences of elements many languages support arrays or/and lists.
Here is an array of six elements:
As a sorting result, we get another array of the same size:
What can be sorted?
It is possible to sort data of different types:
- numbers in accordance with the arithmetic order;
- unicode characters in accordance with their order in the Unicode character table;
- strings in accordance with the lexicographical order or their sizes;
- dates and time in accordance with the chronology order.
Also, it's possible to sort data of more complex types if we know how to compare items (often, but not always!). As a rule, such data has one or more fields, called the sorting key/keys, by which sorting is performed.
In this course, we will often sort integers because it's very simple and intuitive.
Key features of sorting algorithms
The following list contains several key features of sorting algorithms:
- Time efficiency. The size of an array to sort is very important for efficiency. If we want to sort an array consisting of several tens of elements, we can use any sorting algorithms. But what if the array contains a lot of data? In this case, we should use only effective sorting algorithms, otherwise, we cannot wait for the result.
- Stability. An array to sort can contain several identical elements. Stable sort algorithms always sort identical elements in the same order as they appear in the input. Otherwise, a sorting algorithm is unstable. The stability is important when we sort complex structures such as objects, tuples or something else.
- In-place/out-of-place sorting. An algorithm performs an in-place sorting if it requires only a constant amount of an additional space, otherwise, the algorithm performs an out-of-place sorting. The more size of an input array, the more additional memory is required by the out-of-place algorithms.
- Internal or external sorting. An algorithm performs an internal sorting if sorting data are placed entirely within the main memory of a computer. External sorting is required when the data being sorted do not fit into the main memory of a computing device and instead, they must reside in the slower external memory (usually a hard drive).
We will consider sorting algorithms with different properties.