Re: sorts that are good when a vector is largely sorted
Juha Nieminen ha scritto:
Giuliano Bertoletti wrote:
for(int i=1;i<n;i++) {
for(int j=0;j<i;j++) {
if(v[i] < v[j]) {
tmp = v[i];
v[i] = v[j];
v[j] = tmp;
}
}
}
Thinking about how that algorithm works, it's actually insertion sort,
but implemented in a way that does not benefit in any way from the array
being almost sorted or having lots of repetition. Basically what it does
is that it searches the place for the element at i by doing a linear
search from the beginning of the array, and then uses the ith element as
the placeholder for doing the insertion in the inner loop.
[snip]
I guess you're right. Bubble sort is characterized by the adjacency pair
comparison (v[i],v[i+1]) which is what lifts the bubble up, where in
mine, i and j are independent and possibly afar and at each round of the
outer loop the i-th element is put in the correct position with the
subvector [0,i) sorted as a side effect.
I do not even remember where I learnt it and I know for sure it's
greately inefficient. Still the triangular matrix sweep and the compare
and swap are easy to remember, at least to me (indeed I typed it
straight away without even testing it, knowing that despite being slow,
it works).
When I have a few objects addressed with pointers I prefer to use this
rather than defining a class container with a < operator which
derefernces pointers and picks the right container:
es.
class MyClass {
public:
int value;
}
std::vector<MyClass *> v;
I prefer using the algorithm above writing:
for(int i=1;i<n;i++) {
for(int j=0;j<i;j++) {
if(v[i]->value < v[j]->value) {
tmp = v[i];
v[i] = v[j];
v[j] = tmp;
}
}
}
rather than using the holder class:
class MyClassPtr {
public:
MyClass *_ptr;
bool operator<(const MyClass &T) const
{
return _ptr->value < T._ptr->value;
}
}
and then filling the auxiliary vector and call:
std::sort(...)
There're probably better ways to the 2nd option, but to me the first is
clearer.
(typed on the fly so there may be errors)
Regards,
Giuliano Bertoletti