Quicksort algorithm
ฝัง
- เผยแพร่เมื่อ 21 ก.ค. 2013
- See complete series on sorting algorithms here:
• Sorting Algorithms
In this lesson, we have explained Quick sort algorithm and implemented it in C++. Quick sort is a divide and conquer algorithm that has an average case time complexity of O(nlogn).
For more such videos and updates, subscribe to our channel.
You may also like us on facebook:
/ mycodeschool
![ขายสมบัติ Ferrari 488 ลูกรักก!! l [Nickynachat]](http://i.ytimg.com/vi/pwF1Il1Uevw/mqdefault.jpg)
Yesterday I saw all your videos on sorting. Today in interview they asked me to explain quick and bubble sort. I got selected.
You are a good man.
Thank you.
Which Company Brother?
A company duit
He passed away in 2014. Very few people can do good even when they aren't around. This is one such guy.
@@srivatsav9 how could you be so sure
@@srivatsav9 I have also heard about it.
But one thing I don't get is why are there uploads in the year 2016?
7 years ago still the best explanation out there!!
Yeah man ur right
True 👍
@@cyborg9910 thank you
Open code school in your college.
You might also enjoy th-cam.com/video/jUTcsLD6RDQ/w-d-xo.html.
Man, by freaking far the best and most simple 101 explanation of QuickSort algorithm ... what can I say, I've become a fan!
We are becoming a fan so give me hawa
@@be-b-57-omkarshimpi4 LAME XD
@@be-b-57-omkarshimpi4 poor joke
Tereko puchaa kisnee 😂
This is a public form and whatever you write is visible to all. Maybe you don't mean it for someone specific but its the way things work. Peace☺
Composed voice,patient visualization,clear depiction, you are a rock star of computer science..an Indian genius
Man ...I was in college 2nd year grad 4 years ago watching this on my way to college in bus... Im watching this again to change my job .. This is the best sorting series in TH-cam crystal clear ☺️☺️
Thanks to your series, I've been able to implement selection-, bubble-, insertion-, merge- and now the quicksort algorithm in the Rust programming language, through your excellent and descriptive explanation of the core concept of the algorithms, as well as the in-depth technical details. I am very grateful for your videos, much thanks.
Oh...Dear sir,ii'm almost your student on youtube!!! all time appreciate your videos....you have a great skill which is helpful to most of us....thanks.
You are most welcome Rebecca becky :)
go to ur country and study..
Beleive in Jesus Christ!!
He is the true God!!!
Beleive in God Jesus!!Amen!!
Beleive in Jesus Christ!!
He is the true God!!!
Beleive in God Jesus!!Amen!!
You act as someone who never went abroad....
Try to take a plan and travel out of India, you gonna meet nice people even your behavior gonna change!
Globalisation means ;having an open mind and stop thinking in a traditional way!!
We all need each other in today life!
You should first seek upon Jesus Christ !!
God Jesus loves you!
This man passed away but his voice still helps us and he is alive in our hearts.
how do u know that he is passed away man!
@@bestchannel8056 www.freecodecamp.org/news/mycodeschool-youtube-channel-history/
Actualy its his friend. Not him. He works in google since sometime.
@@saifulhasan2532 HUMBLE FOOL IS PASSED AWAY NOT HE HE WORK IN GOOGLE NOW
The explanations are so crisp and clear. I always wanted someone to make videos this precise. Looking forward to more such videos in your channel.
Thanks mycodeschool. One of the best part of your videos is that the writing and explanation are quick unlike other video lectures which spend most of the time in writing/erasing/repeating. One of the best teaching method I have ever seen with digital aid. Keep up the good work! Thanks a lot!
I somehow found your video in my first year of college (2020) and today i have graduated (2024), still when i have to revise algorithms i watch your tutorials.
I know you are no more in this world, but your contribution to community will always be remembered sir.
Hi Anthony,
We are building a queue where we are logging all the video requests. Your video request is already in this queue. We cannot promise a timeline because video creation takes time and we only have one mentor doing it right now. We are hoping to speed up by pulling in more contribution.
You're most welcome :)
Hello, I just watched your video, it didn't explain many things to me, but most of them are still not clear to me. And I have one question. Why Q(A, 1, 1) ? Why not Q(A, 2, 1) ? Time: 12:54
@@sainthentai7763 Because pindex was 0,and end index was 1,
so Quicksort(A,pindex+1,end)=Quicksort(A,1,1)
U made indians proud sir!
Awesome explanation
Finally somebody who actually fully explains how this algorithm works and does not skip any details. Thank you so so much! 🙏🏻
Man, huge respect to all of your tutorials. Always appreciate your hard works!!!
I've learned more about Quick Sort here than 3 books I've read on it.
Great job @mycodeschool!
What books did you read? Twilight?
Why would you read three books on Quicksort? Quicksort is not even applicable to the real world.
@@SkillUpMobileGaming It is, that's why we learn it, silly.
@@SkillUpMobileGaming wtf are you talking about
@@SkillUpMobileGaming It is literally the algorithm that is implemented in most sort functions in many language libraries
love u man!!!! seriously.... the world needs more teachers like u!!
@BeautifulDrugs Lover how do u know ?
@@paragrane5676 you can go through this answer, even his mother has commented there. qr.ae/TUnAzM
@@paragrane5676 because he is humblefool.
Well known personality in Indian coding community.
finished first year 2 years ago but i find myself back here to brush up on some basics before a final exam. This man will forever be relevant mycodeschool keep up the good work
As a Profesional Full Stack Software Developer; I always come back to mycodeschool just to listen to your voice again. Thank you master; your reward is in haven...
He really did pass away in 2014 in a accident.
*that moment when he shows the code at the end*
Less than 18 hours from my exam its good to watch this video
lmao yuh tell us plz
@rocky rawlo don't fuck with me nigga
@rocky rawlo On TH-cam?
@rocky rawlo 😂😂
This channel needs to get more recognition. Without this I wouldn't have sound knowledge on different sorting techniques. Thank you!
Thank you so much for this video - this is the only one I've found that was really clear on both the concept and, more importantly, the implementation of the algorithm.
You have real talent as an educator, and I'm sure there are many people who appreciate your tutorials - hope to see more in the future, if you have time!
You're welcome Luisa :)
i really love this guy, he's the very good at making something really complicate understandable
Explaining the tracing of the algorithm helps sooo much especially with recursion. So helpful!
Wow! I couldn't find a single video that explains quicksort better. Thank you so much for such a thorough and easy to understand tutorial!
"Think about it and you will get it" - well said my friend, well said.
You do great job, thank you!
This particular way of choosing the end point as pivot has an interesting side effect to learn for beginners. If you try to sort some already sorted array like {1,2,3,...,100000}, you get the stack overflow error. It's almost obvious, because pIndex will be 99999, 99998, 99997 and so on. So after some recursions the program crashes.
Been going over all your videos over the past several weeks - the content and presentation is amazing. I've learned so much and now I have much better intuition of all these algorithms.
I've been trying to get quick sort down for 3 days, read tons of posts on it, this is the 4th or 5th video I've watched. This was better than any of the short ones I watched and goes in depth and actually works well. Thanks!
Just wondering, do you write your own Subtitles/Closed Captions? Because they seem to be unusually spot on.
Colt Wilson We get help from some volunteers.
almost 9 years ago still the best explanation out there!!
I have not come across a single video on quick sort which explains the working as well as the pseudo code so much clearly, thank you!
I love how you really explain and show the base case in action
Thank you so much for this video! I was stuck on understanding the implementation and your video helped me understand the logic we use when writing the code. Thank you!!!!
Nice video .., Explaining in-detail. this is best video to understand quick sort algorithm.
There can not be a better explanation for quick sort than this one, hands down!
THIS MAKES SO MUCH SENSE THANK GOD. i spent a whole two hours trying to figure out things with another video that was way more confusing than this. thank you!!! you sir, have saved me from like two more hours of stress. much appreciated.
Excellent tutorial. Combining code with visualization is incredibly great. Keep up the good work. Could you please post a video on building a heap data structure, with all its operations (insert, delete etc.) including heap sort ?
Wow, great explanation! I thought I would need more time to get this. Thank you =))
After watching like 100 different videos I finally understand this, implemented in both python and java works as expected. Good job dude!
Thank you, this was incredibly helpful! Good breakdown from the basic idea to the implementation. Every other video I tried did a shoddy job of explaining what quicksort actually is - they just jumped into doing it and meaninglessly telling you what to do.
sir, seriously, u r awesome. thank you so much for the playlists!
Absolutely wonderful tutorial, thank you very much! I couldn't find any video that explained this as clearly as you did. Your annotations and colors are great.
the only guy who has been able to make me understand quicksort this easy
Simply, great buddy, I have been looking around for a simple explanation as this for a very long time now and yours is the only one that matches. keep it up bro.
I Wish you were my professor of my CS department. I would top my classes after taking classes from you. So neatly explained! Loved it! 🥰😎😍
indian tutorials are the best xD
+wenigmehl i know lol! the depth of their knowledge and ability to explain things simply is so awesome :P
+wenigmehl sarcastic
oh lol that went over my head. once i get past the different accent i have actually learned a lot from them XD
go to ur country...
thank u brother..
its due to the simple english followed by us
Well done, you made it so easy to visualise what is happening on the surface as well as when you dive into the code. Not many people can pull that off
This video really clarifies the concept of quicksort for me. Thank you for the explanation!
Done thanks
Todo take notes
The partition function starts off with the pivot at the midpoint but ends up returning an index for the pivot AFTER all the smaller elements have been moved left of the pivot and all the larger elements right of the pivot
15:00 logic for moving elements before the pivot
Thanks mycodeschool.very nice video
By far the best and most simplest explanation of quick sort algo and code.
Best explanation of Quick Sort I've ever seen in my life. Thanks, man!! This video deserves way more likes
I finnaly understood this sort :D .. Thank you so much
"Just think about it and you should be able to get it. " towards the end hahaha
I just came back to hear your voice again. People don’t understand that unlike today, the computer science in the 2010s hit a different feel.
I was trying to look up for the quick sort codes in Java, and I stumbled upon your tutorial and by following the whole tutorial I was able to write the quick sort in Java myself. Thank you very much
Good explanation! Very helpful! now i just need to implement this in assembly....not so easy lol
Excellent lectures.....love ur teaching methodology....can u post the video on Shell sorting technique...?
Best tutorial you'll find on quick sort, explains EVERYTHING you need to know clearly and correctly.
Wrote my data structures and algorithms exam and I got 0 for using this method, specifically refering to the graph showing how the numbers are sorted as that is what was asked.
This is probably due to that fact that my text book handles the quick sort algorithm differently, for instance the pivot in my text book is found through ( first element + last element ) / 2
What an excellent tutorial! I didn't have a clue how quicksort worked until watching this. Thanks for the video :D
Nice video as always.
But may I know which softwares do you use for writing and recording? Also do you use a stylus for writing?
I believe there is a condition that can be added to the logic to avoid unnecessary swaps. For instance, if we have the following array 7 2 1 6 4 5 3 8 where the pivot is the last and highest element 8, we would be calling the swap function unnecessarily because all the elements are less than the pivot (probably the necessary logic in this case would be just to increment the pIndex because the element is less than the pivot and is correct to be placed on the left side, hence increment the pIndex ). Adding a check to swap only if the pIndex != than i would help. Something like:
for( i
yes - you are absolutely correct
I'm sorry, I cant get the last condition. Whats right? Is it end-1? And do you mean (Pindex!=end)?
thanks brother...you saved me...i was going wrong with the pseudo code explained a lot !!...thanks a lottt !!!
if(pindex != i )
{
swap(A[pindex],A[end])
return pindex
}
else return end
I think it is better to have a single unnecessary swap than to have a longer code as a longer code will require more time to process, won't it?
you are helping even after you left your body man hats off
What happened to him :( can you name his profile?
I must have watched at least 10 videos today, but this was the one that helped me to understand it the best. Thank you so much for this explanation
Best tutorials out there! Better than my lectures man thank you!
facts
THIS SORTING WILL TAKE SOME TIME TO UNDERSTAND
Watching it twice did the trick!
It takes 20 minutes and 38 seconds to be precise ;)
Thanks for saving the day, legit one of the best and simplest explanation. This is sort of the best sudo code one is looking for with complete understanding.
I am watching this tutorial ....just 4 hours before my exam ( I am a Btech student and today is my practical exam on Data Structure and Algorithms).... Thank you so much sir....
We really miss you sir 😢😔💔 #rip #humblefool
how about if a[0] is smaller than pivot, the a[0] and a[index] (that start with zero) will change place while i++ and index++ it will swap the same index
I got confused at first too. But it's just extra operation and doesn't affect the correctness of Algorithm.
@@dasgoood2811 nothing happens even if u r swapping(i , pIndex) even they are in the same position only it is considered as an extra step that's it....
The BEST explanation of Quick Sort Ever!!!
Thanks for this wonderful video.
Can we take a moment to appreciate your explaining skills. Great Job!
wishing the legened is still alive
rip humblefool
//QUICKSORT
#include
#include
void QuickSort(int A[],int start,int end);
int Partition(int A[],int start,int end);
int main()
{
int A[50],n,i;
printf("Enter the number of elements: ");
scanf("%d",&n);
printf("
Enter the elements: ");
for(i=0;i
Thanks man !
thnx bro and btw why dont u keep c programme for all the sorting explanation as some of them dont no c++ and it ll be useful to everyone too pls take it as a request
Why u need 2 temp variables you can use the same one for both the purposes in partition function
Not all heroes wear capes.
Program takes inputs but does not sort :(
This is the best and easiest partition function i ve seen in quick sort implementation. simply too good
You have done a fantastic Job! my friend. Your tutorial is so good and a complete one. I have gone through so many articles, but nothing was like this one. Explanations were crystal clear and precise as well, straight to the point, really feels good when we go through your tutorial video playlist. Well done!
Very cool! The best video explaining Qucik Sort.
Im going to win a medal at IOI 2020 in your memory Lord Harsh.R.I.P
The guy explaining the video is not Harsha but it's Animesh and he's still alive.
Hi Soumyajit,
In randomized quick sort, instead of choosing pivot as last index, choose any random index (using a library function to generate random number) and first swap the number at this random index with element at last index. Rest remains the same. Try and let me know if you are not able to do it on your own.
Best digital explanation of quick sort. Your videos are very rich and make use of technology amazingly to make sure that viewers understand the algorithm perfectly. Thanks a lot for creating and sharing these videos.
Really great tutorial.
I have one question, why do we need the last swap(..) method before the return statement?. If we can run the loop till the pivot element, then the pivot element will automatically come to its position after the swap. Please let me know if I am wrong.
wow i did not realize that
Did you get the answer to that?
Very nice and descriptive video keep up the good work.
But this case I have some criticism I feel is necessary since I implemented the algorithm and it doesn't work. The code presented in this video is for demonstration purposes only. The code as presented in the video works in the given case only and probably in some others but not in the general case.
I just tried it and it doesn't work. The problem is in the partition function. For example: suppose under index 0 there is number less than four then there would be swapping of index 0 with itself since both 'i' and 'pIndex' are 0 at this point. And that swapping of the elements with themselves will continue until a bigger number is met, since both i and pIndex are incremented synchronously. The main problem however is that the algorithm can only "push" rightwards only one number. Suppose for example that at index 1 there was number 8 the first swap would change the positions of 7 and 8 and 8 would remain at index 0... And that would continue as long as the algorithm is busy pushing 7 rightwards, any other element bigger than 4 would remain in its previous place relative to the other elements. A number of passes is needed to push all numbers bigger than 4 right of the pivot.
P.S. I only mean this as a constructive criticism, sorry If my comment sounds rude or something.
There is a complete and working implementation of the algorithm: (look at the first answer not the question)codereview.stackexchange.com/questions/77782/quick-sort-implementation
I agree, with your analysis.
I implemented the algorithm in C and it does seem to work correctly:
Have a look at my code in C (for a better version of code gist.github.com/syedsouban/230ad57f79b81a90812f9ba4d275d8da )
#include
void swap(int* x,int* y)
{
int t;
t=*x;
*x=*y;
*y=t;
}
int partition(int* a,int start,int end)
{
int pivot=a[end];
int pIndex=start,i,t;
for(i=start;i
MrStarTraveler, you say, " Suppose for example that at index 1 there was number 8 the first swap would change the positions of 7 and 8 and 8 would remain at index 0". That is not possible since the partition index would be advanced. The whole point is to push *only* elements less than the pivot to left and then *protect* those smaller values by advancing the pivot index, cannot see how this can be broken. cheers
Can you give me an array input for which this doesn't work, please? I tried with duplicates and it works. Just curious.
@@kaipulla77 5 4 3 2 1
Not yet Ozgur ! Adding more in data structures series right now. We are prioritizing based on requests. we'll get back to this one after few more videos in data structures series.
Man I've watched this video (and the mergesort video from this channel) before every exam, technical interview, etc for the last four years through university and whilst applying for jobs. Really excellent presentation. Thanks so much.
Guys this alghoritm is a mess
Did you consider negative scenario where all the elements on the left of the pivot are less than the pivot in the decreasing order ?
it doesn not matter . we just want that elemnts on left of the pivot are less than the elements on its right . WE DONT CARE ABOUT THE ORDER OF ELEMENTS. THATS WHAT WE DO IN FURTHER CALLS OF QUICKSORT AND PARTITION METHODS. Finally the array gets sorted.
This may get reflected while calculating the time complexity
what does "O" and "n" in "O(nlogn) " refers to?
Ali Zafar it is known as the big Oh notation, to calculate the complexity and efficiency of the program. read about it.
O refers to the worst-case scenario, and n would be just a specific variable, depending on what action you're performing.
For example, traversing an array would be O(n). n in this case would be the number of items in the array. O(n) indicates the amount of time, basically how many steps, it would take in the worst-case to traverse through that array. O(n) means that it would take n steps to traverse the array. So in this case the scalability of the method is linear. if you have 6 items in the array it would take 6 steps, if you have 12 items it would take 12 steps.
In the case of O(nlogn), if you have 6 items in the list it would take 6*log(6) steps to implement that method. Specific numbers are not necessary for big O notation, what matters is the shape of the curve, so nlog(n) would have a logarithmic looking curve. What you're interested in is how much your function would scale depending on the input.
This is really great!! I just learn programming and your video get me to understand the concept , and then I can figure the function out myself!! This is a great way of learning. Your video really deserves more views!!
Super clear, best instructor ever! Thank you, sir!
when you are doing swap(A[i],A[partitionIndex]); does the swapping happen since you are just passing variables and not the memory locations. so swapping will happen in the swa function and when you come out the original status of both the variables is returned!
Manikanta Raju Good catch.. the swap function can have a signature like void swap(int &a, int &b); Now , here we are taking a and b as reference variables. Reference variable concept is available in C++ (not in C). Its different from pointer. Now, here instead of local variables, actual arguments will be swapped. BTW, in the pseudo-code, the intent was just to say that, we should swap. In Pseudo-code, we ignore compilation and other errors.
mycodeschool Thanks for the reply! yeah, so its reference variable in c++. I am new to c++ , thanks for the info! By the way you are simply awesome man, making algos look simple and straight! Also can you please do a video on converting a prefix string to infix string, not computing the string, but want the infix string from prefix!
sir could you provide the code link?
//QUICKSORT
#include
#include
void QuickSort(int A[],int start,int end);
int Partition(int A[],int start,int end);
int main()
{
int A[50],n,i;
printf("Enter the number of elements: ");
scanf("%d",&n);
printf("
Enter the elements: ");
for(i=0;i
thank u Muhammad Zain Zaheer
best quicksort explanation I've seen. thank you
I'm watching this in Feb 2020. The best explanation on quick sort algorithm.
how come there are 71 unlike for this helpful video...
One guess would be the accent.
Now It's 79...they rotated their Display 180* and thought the unlike button is the like button :)
may be some beginners didn't get that
I used not to like the accent either, but that's okay for me now. BTW, his accent is not that strong. His clear explanantion makes great complement to his accent.
🐰
Is there any link to learn Heap sort which is explained by you ?
SAINATH D'LEH Not yet,, we need to create one.
mycodeschool yeah, bro make some heap sort video ASAP. thanks again.
+mycodeschool IT will be very helpful ..btw gr8 work!!!
+mycodeschool no heap yet ):
+Hiimgosu My name is Animesh and I am the one who you listen to in most of these videos. Harsha who was my co-founder passed away in an unfortunate accident. But Harsha was mostly into other aspects of MyCodeSchool. I am the one who created (and still wish to create more) videos. The only problem is that I was doing mycodeschool full time earlier, but now I have taken a job and it's getting difficult to find time. But I want to get back. Hopefully, I will upload some videos soon. :)
omg...finally..... the best quick sort explanation on the internet. THANK YOU
i am lil puzzled your voice sounds like you are a engineering student but you knowledge matches to that of a professional software engineer....what is it in real?
Before founding MyCodeSchool, I have worked in the industry for about 4 years. blog.mycodeschool.com/2013/12/the-story-of-mycodeschool.html-AnimeshCo-fonder, MyCodeSchool.
Cool