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

Подписаться 165 тыс.

Просмотров 8 тыс.

50% 1

Patreon ➤ / jacobsorber
Courses ➤ jacobsorber.th...
Website ➤ www.jacobsorbe...
---
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.jacobsorbe...
people.cs.clem...
persist.cs.clem...
To Support the Channel:
+ like, subscribe, spread the word
+ contribute via Patreon --- [ / jacobsorber ]
Source code is also available to Patreon supporters. --- [jsorber-youtub...]

Опубликовано:

1 окт 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 31

@SpeedingFlare 8 месяцев назад

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

@victorgallet3174 8 месяцев назад

same haha

@justcurious1940 8 месяцев назад

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

@dhyey2316 8 месяцев назад

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

@greg4367 8 месяцев назад

New T Shirt? qsort() Creating chaos since 1972

@C-CW 8 месяцев назад

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.

@nzwgsy 8 месяцев назад

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;

@jzxdrift 8 месяцев назад

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 8 месяцев назад

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 4 месяца назад

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.

@rosen8757 8 месяцев назад

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.

@sseerrttww 8 месяцев назад

May the pointers be with you, my master.

@maduromaduro9826 8 месяцев назад

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

@skeleton_craftGaming 8 месяцев назад

Man...

@raptoress6131 8 месяцев назад

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

@anon_y_mousse 8 месяцев назад

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

@YilmazDurmaz 8 месяцев назад

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.

@franchausqui912 8 месяцев назад

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

@obinator9065 8 месяцев назад

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

@redabou9al562 8 месяцев назад

outperform only for bad c developer

@MrTrollland 8 месяцев назад

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) 🤔🤔

@rob876 8 месяцев назад

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 8 месяцев назад

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

@raptoress6131 8 месяцев назад

I thought the fastest sorting algorithm was radix?

@yash1152 8 месяцев назад

@@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 8 месяцев назад

@@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.

@muhzulqarnaen 8 месяцев назад

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

@angelcaru 4 месяца назад

just pass in half of the length

@martijnb3381 8 месяцев назад

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;

@maxscott3349 8 месяцев назад

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.