I decided to brush up on my memory of sorting algorithms and write a small C++ library containing an implementation of every well-known algorithm. When it came to selection sort, I implemented it like this:
template<class RandomIt, class Compare>
void selection(RandomIt first, RandomIt last, Compare comp) {
for (auto it = first; it != last; ++it)
std::iter_swap(it, std::min_element(it, last, comp));
}
For the sake of interest, I began to compare the speed of my algorithm with other implementations, which I found on the Internet and found out that the implementation below is more than twice as fast:
void selectionsort_1(int* l, int* r) {
for (int* i = l; i < r; i++) {
int minz = *i, *ind = i;
for (int* j = i + 1; j < r; j++) {
if (*j < minz) minz = *j, ind = j;
}
std::iter_swap(i, ind);
}
}
I tried to find the reason for this on the internet, but without success. Later, I noticed that storing the value of the minimum element and a pointer to it does not make much sense and changed the code a bit:
void selectionsort_2(int* l, int* r) {
for (int* i = l; i < r; i++) {
int* min = i;
for (int* j = i + 1; j < r; j++) {
if (*j < *min) min = j;
}
std::iter_swap(i, min);
}
}
To my surprise, the modified algorithm ran in the same amount of time as my implementation, i.e. worse. I decided to see what assembly code the compiler generates for each of the two previous code options and did not notice much difference.
Perhaps I came to the wrong conclusion, but is it really a difference in one mov command that can slow down or speed up the code twice?
P.S. Below I attached an example of test results on an array of random integer numbers with a dimension of 100,000 elements. Project configuration: Release.
