handmade.network » Forums » STB Quick Sort Implementation Question
Blkerf
4 posts
#16951 STB Quick Sort Implementation Question
4 months, 1 week ago Edited by Blkerf on Dec. 12, 2018, 12:27 p.m.

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!!!


mrmixer
Simon Anciaux
580 posts
#16956 STB Quick Sort Implementation Question
4 months, 1 week ago

For the second part of your question the comment above the function explains it:
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.
Blkerf
4 posts
#16957 STB Quick Sort Implementation Question
4 months, 1 week ago Edited by Blkerf on Dec. 12, 2018, 10:44 p.m.

hmmm that makes sense to me, but is there any reason the inline expression couldn't just operate on two regular TYPE variables? why would we ever need a pointer into the actual array as opposed to just 2 value copies?

thanks for the help btw. i appreciate it.
mrmixer
Simon Anciaux
580 posts
#16959 STB Quick Sort Implementation Question
4 months, 1 week ago Edited by Simon Anciaux on Dec. 13, 2018, 1:08 a.m.

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.
Blkerf
4 posts
#16960 STB Quick Sort Implementation Question
4 months, 1 week ago

makes sense. thanks! i'm still confused with my 1st question, but you definitely clarified my second one completely.