I'm trying to implement a basic quicksort algorithm, I've understood the basic concept behind quicksort and now I'm looking online for a step by step guide.
I've followed through about 7/8 guides and what I've found is that every guide has different ways of using the pivot and different ways of using the two pointers/counters.
Some follow these steps for the pivot:
1.Decide a pivot
2.Swap the pivot with the last element of the array
3.Search the element from the left that is greater than pivot and element that is smaller than pivot from right
4.Swap those elements
5.etc...
Others do this:
1.Choose a pivot
2.Put left pointer to 0, a right pointer to the last element of the array
3.Start comparing left pointer to pivot, if left is smaller than pivot move pointer forward
etc...
Let's just say that before reading the guides I think I knew more about the quicksort algorithm.
What guide do you recommend?
Edit: there's some kind of problem with text formatting, I'm sorry
Top comments (4)
So to be honest, if you're struggling with the implementation then you probably don't understand Quicksort. I could be wrong, but I'm going to give you some resources here. I'll also answer your question directly. However, for me personally I self learned everything I know about Algorithms and it was not an easy process. And a lot of what made is difficult was not having a correct foundation and starting in the wrong place.
I get the feeling that what's happening to you. If this isn't the case I apologize, but I figure in the worst case, the resources (and most of this reply) can just be ignored. But having a good understanding of the class of Algorithm Quicksort fall under will probably help a lot.
There's a lot of background knowledge that if you don't have a strong foundation in will make it really frustrating to start out with Algorithms. I'm sure people have gotten by without, so take this for what it is, which is just a set of personal recommendations, but hopefully this will save you some time in the long run.
Math
So first thing that will make Algorithms a hell of a lot easier to understand is a good foundation in Math. Understanding the Mathematical process and Discrete Mathematics in particular. If you already do great, if not, then these are resources that helped me out a lot.
What I would personally recommend being most comfortable with is how Mathematical proof works, especially induction. Recursion is such a core aspect of programming and induction is the huge backbone that most proofs surrounding it rely on.
Understanding these principles makes it a lot of easier to grasp Algorithm correctness which plays a key role usually in their time costs.
In general I've personally always found this an incredible tool to have for programming. One key aspect that I've never really heard mentioned outside of Math + Algorithms is invariants. Understanding how invariants allow you to guarantee outcomes of recursive Algorithms is incredibly helpful. And applying it in an inductive way makes it much easier for writing Algorithms, basically induction from n to 0.
By proving that an invariant holds across an iteration and results in the desired n-1 state combined with a proven terminating state you've basically shown your Algorithms will complete as expected. Obviously there always bugs and things you'll run into when programming, but I've found applying this principle can really reduce some of the debugging headaches when first starting out with Algorithms.
It's also useful as a primer for property based testing, which can be very useful for confirming Algorithms. Example for Quicksort a key testing invariant
is that next value is greater than of equal to the current value.
In the case above the assertion would fail because 5 should be after 4.
Anyways now that I've made an argument for Math here's a bunch of resources:
Personally I recommend the following:
Introduction to Mathematical Thinking (Dr. Keith Devlin) (Coursera)
If you've never really studied formal mathematics this is a great primer and a very gentle introduction. However if you're already comfortable with Mathematical notation, rational vs real, etc. then this might be a bit too elementary.
Mathematics for Computer Science (MIT Open Courseware)
Great primer on mathematics needed for Algorithms, highly recommend this course. Biggest downside, is it's not a formal course so testing yourself can be a bit tricky.
Introduction to proof in abstract mathematics
This book really helped fill in some practical gaps for creating proofs that I felt I hadn't fully grasped via other resources. So if you find you're still really struggling to create proofs this might be a good book to reference.
Concrete Mathematics / Discrete Mathematics with Application
Both are just really good resources to have available if you're trying to self-learn Math.
Algorithms
There's other higher level aspects of Algorithms that personally I find really help in understanding a Algorithms better. The class of Algorithms gives you a huge hint into what underlying principle allows it to work.
In the case of Quicksort knowing that it's a Divide and Conquer Algorithms already tells a lot of what you need to know about the Algorithm. It's also the key that really makes the Algorithm work.
In the case you outlined above for Quicksort there are all kinds of methods for choosing a pivot. But the pivot choices isn't really the key ingredient that makes a Quicksort a Quicksort Algorithms, it's a detail. And once you grasp that fundamental aspect of a Quicksort it will make it a lot easier to understand each "flavor" of it in turn.
So here's the resources I would recommend:
Python Algorithms: Mastering Basic Algorithms in the Python Language
This is an amazing book for learning Algorithms. I would highly recommend it. It goes beyond implementation details and explains the fundamental principle behind certain Algorithms. I don't remember if it covers Quicksort explicitly but either way a really good resource for learning Algorithms.
Algorithms Specialization (Coursera, Standford)
Good primer on Algorithms, with the added benfit of weekly excerises etc. to test yourself.
Introduction to Algorithms (MIT Open Courseware)
This tackles a lot of the same things as the Algorithms Specialization above. But last time I checked there's not material for testing yourself, etc. So it's a much more DIY approach.
The Algorithm Design Manual
This one is a classic and worth having around for reference. It has great explanations and tons of example code on Algorithms, but less introductory than some of the other resources above.
Design and Analysis of Algorithms (MIT Open Courseware)
This is more of an intermediate level course, but might still be useful.
Back to the question
So to answer the top question (and as I tackled in Algorithms section) they are different because there are a bunch of different ways you can implement Quicksort, usually it's just the method for selecting a pivot that changes. The Algorithm Design Manual has a good primer on Quicksort, so that's probably a good place to start.
But the essence of what makes Quicksort work is the Divide and conquer nature of it.
What to learn
Obviously there's a lot of resources here so here's the course of action I would probably take, but obviously feel free to take or not take whatever you want from this reply.
A good starting point is the book Python Algorithms. I've come back to this book again and again, it's really a great resource for learning Algorithms.
If you find yourself struggling with it. I would probably try out the Algorithm Specialization courses next, having a concrete assignment each week that can be verified can really go a long way and you get the added benefit of being able to seek help from people grappling the same content as you.
If you find you can't grasp the Mathematical principles in the course or just feel like you'd like to fill in more details, then I would turn to Mathematics for Computer Science. If you're lost in that, then start with Introduction to Mathematical Thinking.
And if you feel like you know all this and it really is just implementation details tripping you up then I'd recommend the Algorithm Design Manual. In general it's just a great resource to have around.
The other book you could try is Algorithms by Robert Sedgewick. He has a lot of great Algorithm books and videos that could be worth checking out.
Anyways, so that's my list, hopefully it helps and if not I apologize. Again these are just resources that have helped me so I would say find what works for you, but hopefully this give you some stepping stones.
Goodluck!
Yeah, I think this defines perfectly my struggle with algorithms, I'm currently in my second year at university but couldn't pass some of the math courses and I'm having issues following the online lectures with all of this covid stuff.
At this point, I'm asking myself if it makes sense with continuing studying CS, I feel like I could even implement a quicksort (and everything else) without having the mathematical concepts but that would just make me a code monkey and I don't know if I want that.
I've watched the introduction of the course "introduction to mathematical thinking", looks like it's a really interesting course but I don't think I'll have the time.
Thank you for taking the time to answer me, I really appreciate it, you really made me think about my math gaps.
No problem! I will say it mostly likely depends on your end goals.
Personally I have quite a few friends who are very successful in games and web development and do not have strong math or algorithmic skills. So if your concern is lacking knowledge in Algorithms will somehow make you unemployable that's definitely not the case. While helpful, they are not really necessary in a lot of areas of programming.
If you goal in academic then that could be different, a lot of CS is heavy in math and from what I've seen a lot of graduate CS work does require it. But you're probably best to verify for yourself.
My goal wasn't to dissuade you from exploring Algorithms either, just to try and point out materials that I personally found really helped me understand Algorithms a lot better.
Personally I'm somebody who understands better when I understand the fundamental reasons behind something. I found this a lot with classes like Calculus and Linear Alegbra. I didn't necessarily do terrible in them, but I didn't really grasp the fundamental ideas behind things like complex numbers, integrals, etc. And I found once I understand things like sets, the types of numbers systems, etc. it really helped things fall into place. And at least for me this wasn't something really covered in highschool either, so it was something I really ended having to explore myself.
If that is part of your struggles then I do think Introduction to Mathematical Thinking will be really helpful. I'll also point out he has a book too, if you're low on time, but I didn't find the book as good as the lectures themselves.
I find with Math and Algorithms there's also a lot of eureka moments too. It just takes finding the right angle to really get it. And they are both not easy subject matters, so I wouldn't to get too down if you're struggling either, pretty much everybody does.
I would give Python Algorithms a try first though. A lot of Algorithm books focus mostly on implementation rather than fundamental concepts, but Python Algorithms does a really good job of explaining the why it works part.
Also don't be afraid to ask questions to professors, online, etc. I think a lot of people are afraid of looking stupid, but there's nothing stupid about not understanding. These are tough subject matters and everybody learns in different ways. And there are plenty of people happy to help you learn (and who have probably struggled through the same material as well).
Anyways like I said I would check out Python Algorithms, I think it will probably help.
Also if you need a more in-depth explanation of Quicksort just let me know. I'm happy to try and explain it to you as best I can.
hmm, I think I may not be understanding the issue you see. I'll take a shot. Lets call the left pointer "i" and right pointer "j"
There are different ways to select the pivot. Some will select a random element, others index 0 or last or the middle. Regardless, i will keep moving right and j will keep moving left...until they meet.
In the end, you want elements divided into two groups. The dividing point of the two arrays is where index when i and j meet. Algorithms treat the meeting differently. Some will stop the i and j progression when i==j. Others will stop before. But this is just a implementation detail.
Some algorithms will put the pivot in the middle as a final swap, then recursively quick sort the two halves (not including the pivot in the middle -as this element is in the correct final position).
They key is to understand regardless of the partitioning specifics, the two arrays will be partitioned into two groups. The left group will be less than the pivot and the right side will be larger. Again, it's an implementation detail if the pivot is included in the group, in the right side or left side.
I can understand why it's complicated though. In particular this video is pretty helpful (and is how I think of quicksort).
Another method is explained in the hackerrank video below, however, the explanation misses the key point of how the meeting of i and j is dealt with...so I can see how it's confusing to follow. Though it is talked about in the code writeup. A lot of people in the comments are also frustrated too.