[По полочкам] Sorting algorithms. Part 1
Introduction
There are a large number of different sorts that are used everywhere in programs. Sorting algorithms help save resources such as the running time of some part of the code and, accordingly, the human time and memory used to execute your program. For example:
When editing a file, it is not necessary to keep the entire file in RAM. Each line is assigned a serial number, and after making changes, it is enough to sort the updated lines and insert them into the file itself.
Grouping elements according to features that are characterized by a certain number or text value (characters can also be ordered, for example, by their location in the alphabet or by number in the Unicode character table)
When comparing two or more tables or files, it is enough to sort them to save time. Thus, there is no need to “run” from one line to another, and the analysis will be more convenient and structured.
Sorting algorithms are used in various fields, the reason for their use is the ordering of certain structures for ease of understanding by a person, and the optimization of the program in relation to computer resources.
Each sorting algorithm has characteristics such as complexity (worst, average, and best cases) and robustness.
stable sort – sorting that does not change the relative order of sorted elements that have the same keys, by which sorting occurs.
The article publishes program codes for sorting in the C ++ language, in which there is a function that swaps elements in an array:
template <typename T>
void swap(std::vector<T>& arr, unsigned int A, unsigned int B) {
T temp = arr[A];
arr[A] = arr[B];
arr[B] = temp;
}Simple sorts
In this part, we will get acquainted with some algorithms that are not used in the general case due to their not very high speed, however, they allow us to delve into some sorting principles used in more complex algorithms.
Exchange Sort
First, the first element is compared with all subsequent ones and swapped with the compared one, if necessary (depending on the condition: sorting is performed in ascending or descending order). Then a similar procedure is performed for the second, third, and so on.
C++ code:
template <typename T>
void exchangeSort(std::vector<T>& arr) {
for (unsigned int i = 0; i < arr.size() - 1; i++) {
for (unsigned int j = i + 1; j < arr.size(); j++) {
if (arr[i] > arr[j])
swap(arr, i, j);
}
}
}Complexity: O(n^2) (in all cases)
Is not sustainable
Advantages and disadvantages:
+ Ease of implementation
– Slow
Selection Sort
The minimum (or maximum, if sorting is in descending order) element is found on the entire segment of the array and rearranged to the beginning of this segment. After that, the length of the segment decreases by one on the left and the procedure is repeated.
C++ code:
template <typename T>
void selectionSort(std::vector<T>& arr) {
for (unsigned int i = 0; i < arr.size(); i++) {
unsigned int j_min = i;
unsigned int j = i + 1;
for (; j < arr.size(); j++) {
if (arr[j] < arr[j_min])
j_min = j;
}
if (j_min != j)
swap(arr, i, j_min);
}
}Complexity: O(n^2) (in all cases)
Is not sustainable
Advantages and disadvantages:
+ Ease of implementation
– Slow
Bubble Sort
Iterates through the array, swapping adjacent elements if required (depending on the condition: sorting is in ascending or descending order), until the array is completely sorted.
C++ code:
template <typename T>
void bubbleSort(std::vector<T>& arr) {
bool swapped;
do {
swapped = false;
for (unsigned int i = 0; i < arr.size() - 1; i++) {
if (arr[i] > arr[i + 1]) {
swap(arr, i, i + 1);
swapped = true;
}
}
} while (swapped);
}Complexity: O(n) – best case
O(n^2) – average and worst cases
Is sustainable
Advantages and disadvantages:
+ Ease of implementation
– Slow
Insertion Sort
The first element is considered the sorted part of the array. Subsequent elements are transferred to the sorted part at the desired position. Thus, with each transfer, the sorted part is increased by one element.
C++ code:
template <typename T>
void insertionSort(std::vector<T>& arr) {
for (unsigned int i = 1; i < arr.size(); i++) {
if (arr[i] < arr[i - 1]) {
unsigned int j = i;
while ((j > 0) && (arr[j] < arr[j - 1])) {
swap(arr, j, j - 1);
j--;
}
}
}
}Complexity: O(n) – best case
O(n^2) – average and worst cases
Is sustainable
Advantages and disadvantages:
+ Ease of implementation
+ Fast on partially ordered sequences
– Slow in general
Mini Conclusion
The considered algorithms have rather low sorting speeds, so projects should use, for example, Shell Sort or Quick Sort. These sorts will be discussed in the next section.
