Thanks for response and clarifications.
I've played a bit with dgSort and ...
1. Assert in code:
- Code: Select all
for (; compare (&array[j - 1], &tmp, context) > 0; j --) {
_ASSERTE (j > 0); // if this assserts (compare()>0), then there was a read from array[-1], but when compare()<=0, then no assertion, but still read from array[-1]
array[j] = array[j - 1];
}
...
will not check condition (j>0) if fn. compare() returns <=0, so this assert-check might not be 'reliable'. When j==0, then compare() reads from array[j-1] (so read from 'garbage' or you can get here access violation).
Example:
Comment out //stride = stride * 2; in dgSort. You won't get assert failure, but there will be read from array[-1] so from array2[0].m_jointCount==-1234, in the end everything might look ok, because that m_jointCount = 9 will be finally stored in array[0], and validation at end of dgSort will also succeed:
- Code: Select all
dgIsland array2[10]={0};
// 'marker' for test reading array[j-1] when j=0
array2[0].m_jointCount = -1234; // value must be < 9
array2[1].m_jointCount = 10;
array2[2].m_jointCount = 10;
array2[3].m_jointCount = 10;
array2[4].m_jointCount = 10;
array2[5].m_jointCount = 10;
array2[6].m_jointCount = 21;
array2[7].m_jointCount = 10;
array2[8].m_jointCount = 10;
array2[9].m_jointCount = 9;
dgSort (&array2[1], 9, CompareIslands);
I know that it's with commented out "stride = stride * 2", and might not be important right now. I think it could be a case why it worked fine when testing before (but still could AV or asserts).
2. You have wrote:
"After the quick sort face it place the array in strides of 8 or less number of elements that satisfy the condition that all element in one stride are equal or smaller that the element in the next stride."
but as I understand in this case after first sort in "while (stackIndex)..." (which anyway doesn't change
anything in above array?!)
it's not true for above example data. I don't know how strides will look in 9-elements array (like first stride [0-7], second stride [8]), but in all cases I see that m_jointCount=9 will be in second stride, so "all element in one stride are equal or smaller that the element in the next stride" is false for above data?
Second loop "for (dgInt32 i = 1; i < stride; i ++) {" is for "What the optimization does is that checks for the first stride and place the smaller element at location zero.", but in this case, first stride was not enough, so there was a "stride = stride * 2" fix.
If possible, could you show me how strides would look like in an array of 9-elements [10,10,10,10,10,21,10,10,9] (this is an array
before and
after first sort)? This would make my doubts go away
For now I think that there might be a bug in first sorting algo, or I've misunderstood some things here (which is more likely possible).
