Quicksort algorithm
Вставка
- Опубліковано 26 вер 2024
- 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
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 ua-cam.com/video/jUTcsLD6RDQ/v-deo.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☺
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
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!
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 UA-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.
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.
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.
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.
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! 🙏🏻
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!
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)
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.
*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 UA-cam?
@rocky rawlo 😂😂
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.
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.
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....
you are helping even after you left your body man hats off
What happened to him :( can you name his profile?
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.
Done thanks
Todo take notes
The partition function starts off with the pivot at the midpoint (or any other pivot location) and returns the new 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
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
Who is still in 2024 ?hit like
I m in 2025
Explaining the tracing of the algorithm helps sooo much especially with recursion. So helpful!
You're welcome Luisa :)
i really love this guy, he's the very good at making something really complicate understandable
Man, huge respect to all of your tutorials. Always appreciate your hard works!!!
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!
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!
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
"Think about it and you will get it" - well said my friend, well said.
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! 🥰😎😍
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
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.
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.
By far the best and most simplest explanation of quick sort algo and code.
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.
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.
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?
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.
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! I couldn't find a single video that explains quicksort better. Thank you so much for such a thorough and easy to understand tutorial!
Nice video .., Explaining in-detail. this is best video to understand quick sort algorithm.
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.
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!!!!
There can not be a better explanation for quick sort than this one, hands down!
sir, seriously, u r awesome. thank you so much for the playlists!
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
This channel needs to get more recognition. Without this I wouldn't have sound knowledge on different sorting techniques. Thank you!
We really miss you sir 😢😔💔 #rip #humblefool
I'm watching this in Feb 2020. The best explanation on quick sort algorithm.
THIS SORTING WILL TAKE SOME TIME TO UNDERSTAND
Watching it twice did the trick!
It takes 20 minutes and 38 seconds to be precise ;)
Thank God for sending this great teacher to us, even for such a short time.
Excellent lectures.....love ur teaching methodology....can u post the video on Shell sorting technique...?
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
Wow, great explanation! I thought I would need more time to get this. Thank you =))
the only guy who has been able to make me understand quicksort this easy
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.
Best explanation of Quick Sort I've ever seen in my life. Thanks, man!! This video deserves way more likes
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....
best quicksort explanation I've seen. thank you
Best tutorials out there! Better than my lectures man thank you!
facts
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?
This is the best tutorial I have seen for QuickSort
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
Rest In Peace sir. Thank you for such amazing videos. Will always look up to you
what happened to him can you name his profile?
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?
MyCodeSchool should publish tutorial videos of all subjects in Computer Science in the similar fashion.... They are so so so easy to understand and helpful!
I finnaly understood this sort :D .. Thank you so much
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!
Thanks mycodeschool.very nice video
Thank you very much, bro. I have some difficulty in trying to understand the logic of Quick Sort algorithm but your teaching really helped me understand very well and my code is working. May God reward you
//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 :(
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.
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.
🐰
your are the best teacher for DSA over internet
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
It the toturial no. 10 or 12 and now I'm understand queck sort 😅😅 .
Best tutorial on quick sort .
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.
u r simply awesome...ur teaching skills is great...
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!
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.
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
First of thanks a lot for so good videos.You're just awesome bro.
At 18:49 we can avoid this extra swaping opreation by taking condition in for loop as i
"Just think about it and you should be able to get it. " towards the end hahaha
This is the best and easiest partition function i ve seen in quick sort implementation. simply too good
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
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. :)
This guy and Abdul Bari is among the best teachers.
Can we take a moment to appreciate your explaining skills. Great Job!
My guy, you are absolutely GOATED.
nicely explained, each step is clear and deep, thank you for this sir 👍👍🙂👍
Sirji aap idhar 👌
After 9 years as well...best tutorial
serious this video is just the perfect explanation. None is unclear. Ty very much
omg...finally..... the best quick sort explanation on the internet. THANK YOU