Quicksort Algorithm Implementation | C Programming Example
Vložit
- čas přidán 24. 07. 2024
- How to implement the quicksort algorithm in C. This algorithm notably uses a randomly selected pivot. Source code: github.com/portfoliocourses/c.... Check out www.portfoliocourses.com to build a portfolio that will impress employers!
See Quicksort Algorithm Wikipedia article: en.wikipedia.org/wiki/Quicksort - Jak na to + styl
Thank you so much for this video! I'm in the middle of a very intense bootcamp and they gave us an assignment to implement a generic quicksort for all types (like qsort in the linux man page). It was really hard for me but then I came across this tutorial and step by step I was finally able to understand the algorithm and make it work with the correct adjustments (pointer arithmetic and generic swap function). :)
I'm so glad to hear this video was able to help you out! :-) Good luck with the rest of your bootcamp!
It's Infinity Labs am I right? I'm doing it as well.
Thank you so much. Initially I was struggling with the partition implementation but you make it clear.
You’re welcome, I’m really glad to hear the video cleared that up for you! :-)
Thank you so much bro! You make look this algorithms like a walk in the park! Your explanations are so good :)
clear and well explained, your tutorials are beautiful!
Thank you Em Hu! 😀
Love your videos man, you explaining everything one by one, i am glad i found this channel, thank you.
I'm glad to hear you love the videos Burkay! 🙂 And you're very welcome, thank you for the kind feedback.
I needed to sort an array and move elements of others arrays conforming to order to the first array. Your crystal clear vidéo was a great help for me. Thank you sir, you got a new subscriber.
You're very welcome, I'm glad the video was helpful for you! :-)
Crystal clear explanation. Thank you.
Thanks for the video so much. You really broke it down to the bear minimum
your awsome..every video you make just make everything super clear.. thank you!!!! :)
You're welcome Idan! :-) Thanks so much for the kind feedback too!!
Thank you very much for your videos! They have helped me a lot all along the way in learning C.
You're very welcome Sophia, I'm glad to hear the videos are helping you to learn C! :-)
Thank you so much..after watching your explanation quick sort was crystal clear to me..
Good structure and very understandable. Thank you ❤
Nice topic, nice explanation. Keep up in this direction.
Thank you! I’m hoping to do some more sorting videos over the next while.
Thanks, this is awesome. Just what I needed.
You’re welcome Netanel, I’m glad it was helpful for you! :-)
just thnx. no words to describe how good u explained it.
Thank you for the kind feedback, and you're welcome! :-)
Very clear explanation!
I'm glad you enjoyed it! :-)
This Chanel is awesome ❤ I learn a lot from it especially c language
Excellent, I'm glad to hear that! ❤️
Very well explained!👍🏽👍🏽
I'm glad that you enjoyed it Enmanuel! 😀
you awesome at teaching c programming man!
Thank you very much Francis! :-D
Best explanation i could get in youtube
Awesome, I'm glad you enjoyed the explanation! :-)
nice specialized version of qsort(). clear explanation of partition.
I'm glad you enjoyed it Dimitrios! :-)
Clear explanation, thank you.
You're welcome, I'm glad you found the explanation clear! :-)
I love your videos and watch playlists, it would be cool if the tasks were more difficult!)
I'm glad you enjoy the videos! :-) The focus of the channel is helping beginner programmers so most of the content is covering easier tasks, but that said I do hope to cover more advanced topics and problems too. You might enjoy the videos on topics like function pointers, pthreads, structure padding and others if you're looking to learn some more advanced topics.
So I used this video as an exercise to port your quicksort implementation to Rust for a bit of fun and learning. I tried to maintain the logic of the C version as best as I could (only the swap function and random number generation are different), but ran into a similar issue as the other comments here that make mention of using size_t instead of int where they were getting underflow problems. I was getting this issue where the partition function would return 0 after several recursions, and the next recursive call to quicksort would try to subtract 1 from that 0. I "fixed" this by wrapping the first quicksort recursive call in an if statement that checks if the pivot_index > 0. The output seems to always be correct. My question is, does that change break the quicksort in a way my potato brain is just not seeing?
Many thanks for the video.
You're welcome, I'm glad you enjoyed it! :-)
good job!
using data type size_t for low, high and size of array, i get segmentation fault(core dumped)..
why ???
One possible reason is that size_t is an unsigned integer type. When we mix unsigned and signed types together in C, we can get some behaviours that we did not intend. For example when mixing unsigned int with int, the int may get converted to an unsigned int: riptutorial.com/c/example/6573/mixing-signed-and-unsigned-integers-in-arithmetic-operations. If you're trying to use something that can store larger values than "int", maybe using "long" instead, as long allows us to store larger signed integers values. :-)
What if I want the pivot to be the middle number of the array what would I type in the code?
I have not tested this, but I think this should work:
int pivot_index = low + ((high - low) / 2);
That should find the midway point between the high and low indexes. If you give that a try, I would be curious to know if it works. :-)
Thanks a lot. But I agree with the previous point that indexes in C must be of size_t type. Then, let us imagine we have an array [3] = {3,3,1}, and we have no random pivot var. Pivot == 1, and in the end of the partition function we return index 0. Calling recursievly quicksort_recursion function with ''pivot_index - 1 , we receive : 0 -1 == 77737182319123178 " ( because pivot index is size_t)
No, indexes in C do not need to be of type size_t. What you've written is a bit difficult to understand, but if I'm understanding correctly it's pointing out a situation where size_t would actually cause a problem because it is unsigned.
when the code is explained, the picture is very clear. But my issue, how myself can think like the way it is explained. and there, where I got stuck all the time. I mean the thinking problem. Thank you for the effort deployed from your side to bring knowledge to us with simple way.
That's a good question Naboulsi. :-) I would say a couple things... coming up with something clever like the quicksort algorithm is a very hard problem. Most programmers don't "invent" algorithms like quicksort. So I wouldn't worry about being able to invent something like quicksort. But programms will study them and understand algorithms like these, so that part of the "thinking problem" is important. Unfortunately there is not an easy answer either. When programmers learn more and more solutions to problems, they gradually build up a toolbox of prior solutions in their mind. Then when they see a new but similar problem they are able to pull from the features of past solutions to help solve the new problem. So a lot of getting better at the thinking problem is studying lots and lots of code, for years at a time. Over time, you develop better and better problem solving skills and have a larger and larger library of past solutions in the back of your mind. :-)
@@PortfolioCourses it seam you just answer to my question dilemma. I will keep practicing to build my pyramid of solution. Thank you for your Gold answer.
You're welcome! :-)
Hello, do you have a video for Shell sort?
No, but I *really* want to do a video on shell sort, so hopefully one day I can do it. :-)
thanks ,sir ❤
why use &array
very nice
Thank you! :-)
Hi, great video as always. Is it a good idea to calculate the median of the array and pick it as the pivot value?
Great question Nathan! We could choose the median as the pivot, but the issue is that the "cost" of determining the median is too high as we need to examine each element in that portion of the array: cs.stackexchange.com/a/33600. Choosing a random pivot is faster. One similar thing we could do though is choose the "median/middle" element between the first, middle and last elements in the portion of the array we are looking at. That way we are only looking at 3 elements, and not all elements in the portion of the array. I believe that strategy is actually about as good as choosing a random pivot: en.wikipedia.org/wiki/Quicksort#Choice_of_pivot. :-)
@@PortfolioCourses Thanks a lot for the quick answer, you are such a good instructor. May love and happiness surround you and your family
@@natevaub Thank you so much Nathan, I wish the same for you and your family too! 🙂
To generate random number between low and high the equation is
A) rand() % (high + 1 - low) + low
so is it ok to use rand() % (high + 1 - low) ?
Love the way you explained, your tutorials are amazing.
Thank you for the kind feedback! :-) The problem with rand() % (high + 1 - low) is that it will only give us numbers in the range of 0 .... (high - low). So that wouldn't work. rand() % (high + 1 - low) will give us numbers in the range of 0 ... (high - low), and then we we add low to this range we get low ... high, which is what we want, so that's why we do it that way. :-)
@@PortfolioCourses
Thank you very much for your answer, I'm very sorry, I wrote the equation wrong, I meant the following:
bottom + ( rand() % (top - bottom + 1) ) has a range of [bottom, top]
In the code:
low + (rand() % (high - low) ) has a range of [low, high -1]
the real question is should we change the equation for?
low + (rand() % (high - low + 1) ) which has a range of [low, high]
Testing sorting algorithms from this playlist
(videos 36, 44, 73, 121, 126) on a raspberry-pi 4,
measure-function from video 244, length of sort-array: 100000
> quick-sort: 0.086109 sec (on my other computers quick-sort is faster than merge-sort)
> merge-sort: 0.045641 sec
> insertion-sort: 23.990210 sec
> selection-sort: 29.300313 sec
> bubble-sort: 74.007234 sec
Cool, thanks for sharing this! :-)
w creator w video w explanation
Thank you very much for the positive feedback! :-)
Sir,awesome algorithm.
Can You please make a video about this task:
Delete all fruits which are equal with a fruit enter by user.
For example if array is:
"apple pineapple apple strawberry apple"
The array will be:
"pineapple strawberry"
For some reason CZcams held your comment in review, I've just noticed this and published it now. Are all of the fruits in one string? i.e. a 1D char array Or are all of the fruits in an array of strings? i.e. a 2D char array
I loooooveeee your explanation. I know that you teach in Canada colleges. (from previous comments) Could you please recommend some colleges in Canada with decent Computers and Information Technology level? Currently I am doing Electrical Eng. in Germany but it is tooooo long and I do not like the way how it is there. I am thinking to move to Canada and take 2years diploma in IT.
Best regards
I'm gad you enjoyed the explanation! :-) In terms of 2 year college programs in Canada... here the government heavily regulates post-secondary programs like college programs. And all the schools are 'public sector', i.e. they're all funded by the government too. So the quality of various college programs is pretty even across different schools by design. Unlike say the USA where you have many public and private institutions with more varying quality. I would suggest picking a school based on where you would like to live. And if you want to immigrate to the country one day to stay long term, you could pick a school some place where you would like to work one day too. 🙂 But in terms of colleges in Canada, you can't really go wrong, so picking one based on location is probably you best bet.
did you use randomized pivoting here with that optimization at the end?
Yes! :-)
@@PortfolioCourses I tried to implement this using a random number generator and wasn’t too sure if I was using that optimization correctly I was able to use basic quicksort though
When testing run time to go through the random array I wasn’t seeing too much of a difference obviously there won’t be but still wasn’t sure if it was working properly either way thank you for this video
hi, do you have linked list implementation of quick sort? wanna know and learn to
Sorry Francis I don't have a video on a linked list implementation of quicksort.
nice!
Thank you! :-)
if no swaps occur during partitions, the index stays zero. Whether you use size_t or int, the resulting value would be invalid, causing a buffer-overflow. So, be careful of that. Add guards *!
Nothing breaks if the index of i is still 0 because no swaps occur.
if you're wonder why your code doesn't work when you did exactly what this guy did, check if you're returning the end of all of the lower values in partitition and not the pointer to the divider.
I just want to make sure I understand Gabie, are you saying that the code has a bug in it? Or are you saying that this is a bug you made when you coded it, and you're giving people a heads up to help them avoid it? :-)
If there is a bug in the code I would want to fix it is all, but there shouldn't be a bug in it: github.com/portfoliocourses/c-example-code/blob/main/quicksort.c. :-)
I thought this would be easier than merge sort but I was completely wrong
If you're a beginner, is it even possible to figure out how to do quicksort without watching and basically copy-pasting code from a tutorial like yours?
Quicksort and other harder algorithms like merge sort are known as being trickier for beginners to understand. It might technically be possible as a beginner to just read how the algorithm works and then implement it, but in practice I think virtually all beginners will at first copy and run code to help understand the algorithm. Maybe later on, once they know the algorithm better and how it is implemented, then they can get more comfortable with writing the code themselves. But even then to be honest with you experienced teachers before teaching quicksort will have to remind themselves of how quicksort works, including the implementation/code (....I know I did !). :-)
@PortfolioCourses thanks a lot for your encouraging and fast reply!
@@PortfolioCourses from my experience it is a good way to use paper and pencil and follow the algorithm.
@10:28 isn't that supposed to be J ? Nice algorithm. Thank you.
You're welcome! And yes that's true, I fix that later in the video before running it. :-)
Who up quicking their sort?
this is harder than it looks...
Agreed, Quicksort is considered trickier than Bubble Sort, Selection Sort, and Insertion Sort by most people.
yes baby:0
If first element less than initial pivot value this code has a bug
That's not true, you might be misunderstanding the algorithm or something. If you explain why you think that will occur, I might be able to help. :-)
This is so hard you could explain it deliberately.
Quicksort is definitely tricky!
@@PortfolioCourses yea exactly and the thing is I have to apply it in stacks and queues which make it worst!
Ah that is trickier, for sure.
MK
You're welcome Amber! :-)
thank you man
you are talking super fast
Sorry to hear you find the talking fast, I hope you’re able to find another video where the talking is slower. :-)
Just use 0.75x if ya have feel it's too fast,
theres literally an option where you can make the video speed slower
Then why am i listening at 1.5x😂
can you tell me haw can in use the fonction srand plz🥲
This video covers random number generation in C: czcams.com/video/Mp3eGLX-OpY/video.html. :-)
@@PortfolioCourses Thanks 🙏🏻😊
@@ahmedbr4926 You're welcome! 🙂