Hi,
I am currently looking into the source of Sean Barrett's STB library, and while I think I generally understand what is going on, I have some questions about some of the decisions.
Below, you can find a link to Pastebin with the relevant "stb.h" Quick Sort code.
https://pastebin.com/gpfXTuL8
I have a few questions:
1. on lines 69 and 70, Sean writes:
/* handling of equality is crucial here */
/* for sentinels & efficiency with duplicates */
I don't really get what the comments on 69 and 70 are saying; what does Sean mean by handling of equality and sentinels? in what sense is this important for efficiency with duplicates? is he talking about the user supplied comparison function? i don't really get what he's saying here.
2. why does Sean use pointers for variables a & b. for example, he does
TYPE *a,*b, t;
a = &p[m];
b = &p[n-1];
instead of just a = p[m] and b = p[n - 1] with TYPE a, b. I don't see any reason for having an extra level of indirection with the pointer.
hopefully, i explained my questions well; I'm not very good at English, so if more clarification is needed I can certainly do that.
thanks alot!!!
I am currently looking into the source of Sean Barrett's STB library, and while I think I generally understand what is going on, I have some questions about some of the decisions.
Below, you can find a link to Pastebin with the relevant "stb.h" Quick Sort code.
https://pastebin.com/gpfXTuL8
I have a few questions:
1. on lines 69 and 70, Sean writes:
/* handling of equality is crucial here */
/* for sentinels & efficiency with duplicates */
I don't really get what the comments on 69 and 70 are saying; what does Sean mean by handling of equality and sentinels? in what sense is this important for efficiency with duplicates? is he talking about the user supplied comparison function? i don't really get what he's saying here.
2. why does Sean use pointers for variables a & b. for example, he does
TYPE *a,*b, t;
a = &p[m];
b = &p[n-1];
instead of just a = p[m] and b = p[n - 1] with TYPE a, b. I don't see any reason for having an extra level of indirection with the pointer.
hopefully, i explained my questions well; I'm not very good at English, so if more clarification is needed I can certainly do that.
thanks alot!!!
Edited by Blkerf
on
For the second part of your question the comment above the function explains it:
The function doesn't use a comparison function, it use inline expression. Forcing the pointers to always be 'a' and 'b' allows to write one expression (a macro) that will work everywhere without worrying what the actual element indices are in the array.
1 2 3 4 | // When you define the compare expression, you should assume you have // elements of your array pointed to by 'a' and 'b', and perform the comparison // on those. OR you can use one or more statements; first say '0;', then // write whatever code you want, and compute the result into a variable 'c'. |
The function doesn't use a comparison function, it use inline expression. Forcing the pointers to always be 'a' and 'b' allows to write one expression (a macro) that will work everywhere without worrying what the actual element indices are in the array.
We avoid the copy because we want the quick sort to be fast. If TYPE is a basic type, less than 64bit (char, short, int, float...) it doesn't matter since a pointer is 64bit. But TYPE could be a big struct and you want to avoid copying it if it's not necessary. Also the comparison doesn't always require the full object so making a copy would just be a waste.
Edited by Simon Anciaux
on