Partially Sort Struct Vector

[lweunice]

hi,
I need to partially sort a struct vector and I have written a function that looks like:

void AxisSort(int start, int end){
sort(prims.begin() + start, prims.begin() + end-start+1, compare);
}

"prims" here is a struct vector

The function works fine when start=0 and end=prims.size()-1
However, with other values the function simply stuck there as if entering an infinitive loop
I wonder if the sort function can only be used to sort the whole vector, but I cannot confirm if that is really the case.

Another choice is qsort, and it works. However, theoretically it is slower than sort. Does any one have better idea to partially sort a struct vector? Thanks.

[Banfa]

If start is the index of the first item to sort and end is the index of the last item to sort then

prims.begin() + end-start+1

is wrong and will only work correctly if start == 0 and in the case (end < 2 * start - 1) then the end point will be before the start point and this is likely to cause trouble.

[lweunice]

Thanks a lot! It works now.

And the interesting is that, contrary to what I had expected, my program runs faster with qsort than with sort.

[Banfa]

Thanks a lot! It works now.

And the interesting is that, contrary to what I had expected, my program runs faster with qsort than with sort.

np :-)

The speed of a sort is not entirely dependent on the algorithm used but is also dependent on the data input into it, i.e. the items to be sorted and the order they are already in.

The question which is the fastest sorting algorithm is not valid, you have to ask which is the fastest sorting algorithm given this set of data to be sorted. Obviously you do not want to implement multiple sorting algorithms or the complex algorithm required to decide which is the right one (you would probably spend more time deciding which is the right algorithm than you would actually doing the sort). So in a real life situation you select an algorithm that is fast given the data you are most commonly going to have to sort and accept that now and then you will get cases where you algorithm will not be efficient.

Whatevery you decide to do sorting wise remember that choosing the Bozo Sort algorithm is always the wrong choice :D