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

Рет қаралды 7,824

6 ай бұрын

Patreon ➤ / jacobsorber
Courses ➤ jacobsorber.thinkific.com
Website ➤ www.jacobsorber.com
---
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:
www.jacobsorber.com
people.cs.clemson.edu/~jsorber/
persist.cs.clemson.edu/
To Support the Channel:
+ like, subscribe, spread the word
+ contribute via Patreon --- [ / jacobsorber ]
Source code is also available to Patreon supporters. --- [jsorber-youtube-source.heroku...]

Пікірлер: 31

@SpeedingFlare 6 ай бұрын

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

@victorgallet3174 6 ай бұрын

same haha

@justcurious1940 6 ай бұрын

Hhh same, I was like why would we even want to sort random memory addresses.

@dhyey2316 6 ай бұрын

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

@nzwgsy 6 ай бұрын

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;

@greg4367 6 ай бұрын

New T Shirt? qsort() Creating chaos since 1972

@sseerrttww 6 ай бұрын

May the pointers be with you, my master.

@anon_y_mousse 6 ай бұрын

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

@franchausqui912 6 ай бұрын

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

@rosen8757 6 ай бұрын

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.

@rob876 6 ай бұрын

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.

@yash1152 6 ай бұрын

have never heard of that before > _"fastest sorting algorithm of all is the network sort but it is different for different array lengths"_

@raptoress6131 6 ай бұрын

I thought the fastest sorting algorithm was radix?

@yash1152 6 ай бұрын

@@raptoress6131 following are all "i think": * radix sort ain't memory efficient, requires as many buckets as the symbols (alphabets, digit, etc) in the elements * it ain't very local, so, cache localization etc can't optimize it * i.e. the fastness is limited only theoretically * whereas practically, it fails on both fronts > _"fastest sorting algorithm was radix?"_

@anon_y_mousse 6 ай бұрын

@@raptoress6131 It depends on your data type. The smaller, the better, such as for strings. For integers you can use multi-tiered buckets, but cache locality is a problem for larger element sizes and things like integers are faster to just use direct comparison.

@raptoress6131 6 ай бұрын

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

@jzxdrift 6 ай бұрын

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

@yash1152 6 ай бұрын

yeah, "double pointer" is too ambiguous of a term here. i was thinking that the video would be about "sorting using two pointers" aka "sorting with double pointers approach" just for reference, current title is _"Sorting in C: Why the double pointers when sorting pointers? (qsort)"_

@benjaminshinar9509 2 ай бұрын

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.

@maduromaduro9826 6 ай бұрын

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

@muhzulqarnaen 6 ай бұрын

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

@angelcaru 2 ай бұрын

just pass in half of the length

@martijnb3381 6 ай бұрын

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 6 ай бұрын

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.

@maxscott3349 6 ай бұрын

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.

@C-CW 6 ай бұрын

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.

@noodlish 6 ай бұрын

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

@skeleton_craftGaming 6 ай бұрын

Man...

@obinator9065 6 ай бұрын

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

@redabou9al562 6 ай бұрын

outperform only for bad c developer

@MrTrollland 6 ай бұрын

6.7.4 Function specifiers Syntax 1 function-specifier: inline Constraints 2 Function specifiers shall be used only in the declaration of an identifier for a function. 3 An inline definition of a function with external linkage shall not contain a definition of a modifiable object with static storage duration, and shall not contain a reference to an identifier with internal linkage. 4 In a hosted environment, the inline function specifier shall not appear in a declaration of main. Semantics 5 A function declared with an inline function specifier is an inline function. The function specifier may appear more than once; the behavior is the same as if it appeared only once. Making a function an inline function suggests that calls to the function be as fast as possible.120) The extent to which such suggestions are effective is implementation-defined.121) 🤔🤔