Sorting in C: Why the double pointers when sorting pointers? (qsort)

---
Sorting in C: Why the double pointers when sorting pointers? (qsort, mergesort, heapsort) — in this video we're looking at the built-in sorting functions in the C standard library (specifically qsort) and a common source of confusion (double pointers) when using them.

***

Welcome! I post videos that help you learn to program and become a more confident software developer. I cover beginner-to-advanced systems topics ranging from network programming, threads, processes, operating systems, embedded systems and others. My goal is to help you get under-the-hood and better understand how computers work and how you can use them to become stronger students and more capable professional developers.

About me: I'm a computer scientist, electrical engineer, researcher, and teacher. I specialize in embedded systems, mobile computing, sensor networks, and the Internet of Things. I teach systems and networking courses at Clemson University, where I also lead the PERSIST research lab.

More about me and what I do:

To Support the Channel:
+ like, subscribe, spread the word

[SpeedingFlare]

At first glance I thought the video was about sorting an array of pointers by their address value haha

[dhyey]

Much needed this video. Thank you for the detailed explanation of qsort function

[nzwgsy]

One disadvantage of using explicit types and sizes is that there's no way for someone reading the code to be sure they're correct without going and finding the definition of the array being sorted. A better approach is to use the language to derive the correct values. For example:

qsort(values, sizeof values / sizeof values[0], sizeof values[0]);

Also, your integer comparison function works fine for your example, but in the general case, it could suffer from overflow if a is a large positive number and b is a large negative number or vice versa. Better is to do explicit comparisons (and it's a good use for the ?: operator):

return a > b ? 1 : a < b : -1 : 0;

[anon_y_mousse]

My favorite sorting algorithm is quick sort, because I can write a non-recursive version from memory and it's generally very efficient.

[sseerrttww]

May the pointers be with you, my master.

[greg]

New T Shirt?
qsort()
Creating chaos since 1972

[franchausqui]

Cool, this looks like a kind of functional implementation in C, Beauty thing

[benjaminshinar]

how is the swapping performed? is it just byte copying?
I remember that in C++ you can overload the std::swap function for your type, but I don't remember much about C...
also, I can't remember how you sort a linked list.

[rosen]

There is an error in your int compare function, the subtraction can overflow (overflow term is used for both under and over) and overflow on signed integers is undefined behaviour in C.

[rob]

The fastest sorting algorithm of all is the network sort but it is different for different array lengths. It would be interesting if you could cover this algorithm for a number of fixed array lengths.

[jzxdrift]

Never say double pointer when referring to a pointer to pointer. Double pointer is naturally expected as double* which is pointer to double. It is more natural to say double pointer instead of pointer to double. You don't say pointer to character when referring to a string, you say char pointer. Same situation here

[raptoress]

I should get to using void pointers... I've just avoided them whenever possible.

[muhzulqarnaen]

excuse me. can we sort partially? like just one half of an array? thank you

[maduromaduro]

stable sorting algorithms ... i heard about spaghetti sort but i didn't find any code ... and parallel networking sort

[martijnb]

Hello Jacob, i like your videos. And i hope you appreciate some feedback on your c code. I think it is best practice to determine the size of a pointer type in this way:
MyType *p = (MyType *)malloc(sizeof(*p));
If Mytype becomes Mytype2 you always alloc the right amount of bytes. This also applies to other function calls, like qsort. The cast is for extra safety and to compile on C++. And i think you dont need the extra () to dereference a void pointer. So: int iNum = *(int *)arg;

[YilmazDurmaz]

in other words, a structure like an object or an array will be "pointed", and a structure of structures will be "double pointed", and so on. easy to say, but a maze if not taken with care.

[C-CW]

There is no such thing called double pointer. It's pointer to pointer. At least kernel developers goes with this terminology. To be more specific, double means two times of thing, so what double pointer actually means is two pointers or a pair of pointers, which is not the case here.

[maxscott]

I would definitely be interested in sorting algorithm implementations. I haven't done anything with them yet and it's about time I learned.

The standard library is great and is very helpful for quick stuff and has made an excellent introduction to C for many people, but I don't like getting too comfortable with it. For one thing, I'm here because I want to learn and every abstraction hides knowledge from me. For another, one of the best parts of C is you can quickly implement your own stuff exactly like you want it. You can do things like pass counters to functions that process or input strings or arrays so you can get exactly the information you want at exactly the point in the program where you need it without having to strlen everything or do any goofy stuff. Being able to express myself is a big part of the charm of C and assembly for me.

[obinator]

This is one where C++ can outperform C due to inlining with lambda's instead of the disgusting function pointers 😅

[noodlish]

Not my favourite by any means but sleepsort is an interesting example of lateral thinking.