Also das Video 15 Sorting Algorithms in 6 Minutes ist ja mal sau genial. Am besten hört sich der Radix Sort an ;) Sehr interessant diese vielen Sortieralgorithmen. Muss man sich unbedingt mal anschaun.
Aber der Code für dieses Projekt ist natürlich wieder .... ;)
In dem Video werden die Anzahl der Vergleiche und Array Zugriffe gezählt. Ich frage mich ob so etwas nicht einfacher zu realisieren ist. Da std::sort eine Vergleichsfunktion als Argument annimmt, sollte es sehr einfach sein, die Anzahl der Vergleiche zu zählen. Die anderen beiden Argumente sind Iteratoren. Also müsste man den indirection operator überladen. Das sollte machbar sein.
Hier mein Versuch. Ständig die Iterator Logik bei so Probleme neu zu schreiben ist nicht schön, aber zumindest kann man mit dieser Technik JEDEN Algorithmus untersuchen der Iteratoren akzeptiert. Besser als das gekrüppel was der andere da macht.
#include <vector>
#include <algorithm>
#include <iostream>
struct CounterIteratorAdapter : public std::vector<int>::iterator {
public:
using Base = std::vector<int>::iterator;
int& operator*() {
++counter;
return Base::operator *();
}
auto operator+(int rhs) const {
return CounterIteratorAdapter{Base::operator +(rhs)};
}
auto operator-(int rhs) const {
return CounterIteratorAdapter{Base::operator -(rhs)};
}
static int counter;
};
int CounterIteratorAdapter::counter = 0;
int main() {
std::vector<int> data(100);
for(int i=0; i < data.size(); ++i) {
data[i] = data.size()-i;
}
int comparisons = 0;
auto compare = [&comparisons](const int lhs, const int rhs) { ++comparisons; return lhs < rhs;};
std::sort(CounterIteratorAdapter{data.begin()}, CounterIteratorAdapter{data.end()}, compare);
std::cout << comparisons << " comparisons "<< CounterIteratorAdapter::counter << " array accesses\n";
}
Random:
830 comparisons 2223 array accesses
Reserve:
526 comparisons 1355 array accesses
Sorted:
629 comparisons 1474 array accesses