Quicksort algorithm

  Рет қаралды 1,859,372

mycodeschool

mycodeschool

11 жыл бұрын

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

Пікірлер: 997
@KarthikRaja-bq7pk
@KarthikRaja-bq7pk 5 жыл бұрын
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.
@SumitKumar-fn3gj
@SumitKumar-fn3gj 5 жыл бұрын
Which Company Brother?
@chaitanyavelagapudi1164
@chaitanyavelagapudi1164 4 жыл бұрын
A company duit
@srivatsav9
@srivatsav9 4 жыл бұрын
He passed away in 2014. Very few people can do good even when they aren't around. This is one such guy.
@aakashprasad9777
@aakashprasad9777 4 жыл бұрын
@@srivatsav9 how could you be so sure
@tushargahlaut5812
@tushargahlaut5812 4 жыл бұрын
@@srivatsav9 I have also heard about it. But one thing I don't get is why are there uploads in the year 2016?
@SudhanshuKumar-lp1nr
@SudhanshuKumar-lp1nr 3 жыл бұрын
7 years ago still the best explanation out there!!
@chennayaianjc3306
@chennayaianjc3306 3 жыл бұрын
Yeah man ur right
@cyborg9910
@cyborg9910 2 жыл бұрын
True 👍
@allwell8570
@allwell8570 2 жыл бұрын
@@cyborg9910 thank you
@anjalikhobragade7063
@anjalikhobragade7063 2 жыл бұрын
Open code school in your college.
@TrulyUnderstandingAlgorithms
@TrulyUnderstandingAlgorithms 2 жыл бұрын
You might also enjoy kzbin.info/www/bejne/oIa3lKaCeZuFerM.
@miguelmenindez6826
@miguelmenindez6826 8 жыл бұрын
Man, by freaking far the best and most simple 101 explanation of QuickSort algorithm ... what can I say, I've become a fan!
@be-b-57-omkarshimpi4
@be-b-57-omkarshimpi4 5 жыл бұрын
We are becoming a fan so give me hawa
@HarshPatel-iy5qe
@HarshPatel-iy5qe 4 жыл бұрын
@@be-b-57-omkarshimpi4 LAME XD
@097_shashanksahu6
@097_shashanksahu6 4 жыл бұрын
@@be-b-57-omkarshimpi4 poor joke
@be-b-57-omkarshimpi4
@be-b-57-omkarshimpi4 4 жыл бұрын
Tereko puchaa kisnee 😂
@097_shashanksahu6
@097_shashanksahu6 4 жыл бұрын
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☺
@vibhavsharma2980
@vibhavsharma2980 6 жыл бұрын
Composed voice,patient visualization,clear depiction, you are a rock star of computer science..an Indian genius
@anjanobalesh8046
@anjanobalesh8046 2 жыл бұрын
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 KZbin crystal clear ☺️☺️
@rebeccakipanga478
@rebeccakipanga478 9 жыл бұрын
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.
@mycodeschool
@mycodeschool 9 жыл бұрын
You are most welcome Rebecca becky :)
@SonuSonu-tk5pk
@SonuSonu-tk5pk 7 жыл бұрын
go to ur country and study..
@rebeccakipanga478
@rebeccakipanga478 7 жыл бұрын
Beleive in Jesus Christ!! He is the true God!!! Beleive in God Jesus!!Amen!!
@rebeccakipanga478
@rebeccakipanga478 7 жыл бұрын
Beleive in Jesus Christ!! He is the true God!!! Beleive in God Jesus!!Amen!!
@rebeccakipanga478
@rebeccakipanga478 7 жыл бұрын
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!
@turing_machine544
@turing_machine544 8 күн бұрын
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.
@saifulhasan2532
@saifulhasan2532 3 жыл бұрын
This man passed away but his voice still helps us and he is alive in our hearts.
@bestchannel8056
@bestchannel8056 2 жыл бұрын
how do u know that he is passed away man!
@saifulhasan2532
@saifulhasan2532 2 жыл бұрын
@@bestchannel8056 www.freecodecamp.org/news/mycodeschool-youtube-channel-history/
@chickmagnet2067
@chickmagnet2067 2 жыл бұрын
Actualy its his friend. Not him. He works in google since sometime.
@ankurchaudhary7892
@ankurchaudhary7892 2 жыл бұрын
@@saifulhasan2532 HUMBLE FOOL IS PASSED AWAY NOT HE HE WORK IN GOOGLE NOW
@marrom6808
@marrom6808 2 жыл бұрын
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.
@patil88ganesh
@patil88ganesh 8 жыл бұрын
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!
@anusuyarangasamy
@anusuyarangasamy 10 жыл бұрын
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.
@cafafans
@cafafans 4 жыл бұрын
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...
@bhuvanesharasu
@bhuvanesharasu 4 жыл бұрын
He really did pass away in 2014 in a accident.
@mycodeschool
@mycodeschool 10 жыл бұрын
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.
@kaiauden4195
@kaiauden4195 7 жыл бұрын
Man, huge respect to all of your tutorials. Always appreciate your hard works!!!
@sophies2103
@sophies2103 4 жыл бұрын
Finally somebody who actually fully explains how this algorithm works and does not skip any details. Thank you so so much! 🙏🏻
@dance2die
@dance2die 7 жыл бұрын
I've learned more about Quick Sort here than 3 books I've read on it. Great job @mycodeschool!
@erikrusso9808
@erikrusso9808 4 жыл бұрын
What books did you read? Twilight?
@SkillUpMobileGaming
@SkillUpMobileGaming 4 жыл бұрын
Why would you read three books on Quicksort? Quicksort is not even applicable to the real world.
@Onomandah
@Onomandah 4 жыл бұрын
@@SkillUpMobileGaming It is, that's why we learn it, silly.
@RAHULTMNT100
@RAHULTMNT100 4 жыл бұрын
@@SkillUpMobileGaming wtf are you talking about
@rayaanhussain7279
@rayaanhussain7279 4 жыл бұрын
@@SkillUpMobileGaming It is literally the algorithm that is implemented in most sort functions in many language libraries
@ultimatehuzefa
@ultimatehuzefa 8 жыл бұрын
U made indians proud sir! Awesome explanation
@mycodeschool
@mycodeschool 11 жыл бұрын
You're most welcome :)
@sainthentai7763
@sainthentai7763 4 жыл бұрын
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
@ganapatibiswas5858
@ganapatibiswas5858 4 жыл бұрын
@@sainthentai7763 Because pindex was 0,and end index was 1, so Quicksort(A,pindex+1,end)=Quicksort(A,1,1)
@pauliewalnuts6734
@pauliewalnuts6734 7 жыл бұрын
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
@indrasishbanerjee5115
@indrasishbanerjee5115 8 жыл бұрын
This channel needs to get more recognition. Without this I wouldn't have sound knowledge on different sorting techniques. Thank you!
@rishijain7171
@rishijain7171 7 жыл бұрын
love u man!!!! seriously.... the world needs more teachers like u!!
@paragrane5676
@paragrane5676 5 жыл бұрын
@BeautifulDrugs Lover how do u know ?
@nikhilraghute6560
@nikhilraghute6560 5 жыл бұрын
@@paragrane5676 you can go through this answer, even his mother has commented there. qr.ae/TUnAzM
@udaykadam5455
@udaykadam5455 5 жыл бұрын
@@paragrane5676 because he is humblefool. Well known personality in Indian coding community.
@AlexanderMcNulty92
@AlexanderMcNulty92 7 жыл бұрын
*that moment when he shows the code at the end*
@jenna4523
@jenna4523 3 жыл бұрын
Explaining the tracing of the algorithm helps sooo much especially with recursion. So helpful!
@CaptainSlowbeard
@CaptainSlowbeard 7 жыл бұрын
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!
@newbiedevtons
@newbiedevtons 4 жыл бұрын
i really love this guy, he's the very good at making something really complicate understandable
@sethigoldy
@sethigoldy 10 жыл бұрын
Less than 18 hours from my exam its good to watch this video
@spyrex3988
@spyrex3988 4 жыл бұрын
lmao yuh tell us plz
@spyrex3988
@spyrex3988 4 жыл бұрын
@rocky rawlo don't fuck with me nigga
@varsh5192
@varsh5192 4 жыл бұрын
@rocky rawlo On KZbin?
@dineshsidh9370
@dineshsidh9370 3 жыл бұрын
@rocky rawlo 😂😂
@nipunb20
@nipunb20 5 жыл бұрын
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.
@Tyler1986
@Tyler1986 6 жыл бұрын
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!
@nikolaichichulin
@nikolaichichulin 9 жыл бұрын
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.
@chayarenathomas1847
@chayarenathomas1847 7 жыл бұрын
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!!!!
@danish_m_m
@danish_m_m Жыл бұрын
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!
@karantiwari9328
@karantiwari9328 3 жыл бұрын
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!
@amarputsala4090
@amarputsala4090 9 жыл бұрын
Nice video .., Explaining in-detail. this is best video to understand quick sort algorithm.
@venkarri8534
@venkarri8534 10 жыл бұрын
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 ?
@ArjunPatel-hi5eq
@ArjunPatel-hi5eq 9 жыл бұрын
I love how you really explain and show the base case in action
@gabrielahernandez4236
@gabrielahernandez4236 2 жыл бұрын
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.
@tyli8698
@tyli8698 8 жыл бұрын
sir, seriously, u r awesome. thank you so much for the playlists!
@hovhadovah
@hovhadovah 6 жыл бұрын
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.
@krishnachamarti1256
@krishnachamarti1256 7 жыл бұрын
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.
@laurenp2701
@laurenp2701 9 жыл бұрын
This video really clarifies the concept of quicksort for me. Thank you for the explanation!
@mycodeschool
@mycodeschool 10 жыл бұрын
You're welcome Luisa :)
@kingstonmocktail7744
@kingstonmocktail7744 5 жыл бұрын
"Think about it and you will get it" - well said my friend, well said.
@sandeepreddy8859
@sandeepreddy8859 4 жыл бұрын
By far the best and most simplest explanation of quick sort algo and code.
@kennylee6972
@kennylee6972 6 жыл бұрын
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
@Abhi-eo6jy
@Abhi-eo6jy 2 жыл бұрын
almost 9 years ago still the best explanation out there!!
@coltwilson3271
@coltwilson3271 9 жыл бұрын
Just wondering, do you write your own Subtitles/Closed Captions? Because they seem to be unusually spot on.
@mycodeschool
@mycodeschool 9 жыл бұрын
Colt Wilson We get help from some volunteers.
@rutwikhiwalkar9583
@rutwikhiwalkar9583 4 жыл бұрын
After watching like 100 different videos I finally understand this, implemented in both python and java works as expected. Good job dude!
@ruanlehanie5851
@ruanlehanie5851 6 жыл бұрын
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
@Paul-yw4yr
@Paul-yw4yr 10 жыл бұрын
Wow, great explanation! I thought I would need more time to get this. Thank you =))
@arpityadav2268
@arpityadav2268 2 жыл бұрын
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! 🥰😎😍
@umarusman2
@umarusman2 2 жыл бұрын
There can not be a better explanation for quick sort than this one, hands down!
@bob_factory
@bob_factory 6 жыл бұрын
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.
@phantuanngoc
@phantuanngoc 6 жыл бұрын
Thanks mycodeschool.very nice video
@mostinho7
@mostinho7 3 жыл бұрын
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
@dhrubo619
@dhrubo619 7 жыл бұрын
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
@alanespinet8423
@alanespinet8423 Жыл бұрын
Best explanation of Quick Sort I've ever seen in my life. Thanks, man!! This video deserves way more likes
@wenigmehl
@wenigmehl 9 жыл бұрын
indian tutorials are the best xD
@lincolnchafee9602
@lincolnchafee9602 8 жыл бұрын
+wenigmehl i know lol! the depth of their knowledge and ability to explain things simply is so awesome :P
@vidhursavyasachin7797
@vidhursavyasachin7797 8 жыл бұрын
+wenigmehl sarcastic
@lincolnchafee9602
@lincolnchafee9602 8 жыл бұрын
oh lol that went over my head. once i get past the different accent i have actually learned a lot from them XD
@SonuSonu-tk5pk
@SonuSonu-tk5pk 7 жыл бұрын
go to ur country...
@adilismail3593
@adilismail3593 7 жыл бұрын
thank u brother.. its due to the simple english followed by us
@pranavkotteswaran4093
@pranavkotteswaran4093 8 жыл бұрын
Excellent lectures.....love ur teaching methodology....can u post the video on Shell sorting technique...?
@monishkumar2780
@monishkumar2780 Жыл бұрын
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.
@balaganesh3440
@balaganesh3440 Ай бұрын
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.
@nikitacollier4065
@nikitacollier4065 7 жыл бұрын
Good explanation! Very helpful! now i just need to implement this in assembly....not so easy lol
@johann-san
@johann-san 9 жыл бұрын
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
@smbehindyou
@smbehindyou 7 жыл бұрын
yes - you are absolutely correct
@varshar5856
@varshar5856 6 жыл бұрын
I'm sorry, I cant get the last condition. Whats right? Is it end-1? And do you mean (Pindex!=end)?
@sanketughade6986
@sanketughade6986 6 жыл бұрын
thanks brother...you saved me...i was going wrong with the pseudo code explained a lot !!...thanks a lottt !!!
@pvpaparaokancharapu3219
@pvpaparaokancharapu3219 6 жыл бұрын
if(pindex != i ) { swap(A[pindex],A[end]) return pindex } else return end
@willamsurya6901
@willamsurya6901 6 жыл бұрын
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?
@XanderWood
@XanderWood 8 жыл бұрын
What an excellent tutorial! I didn't have a clue how quicksort worked until watching this. Thanks for the video :D
@crazystuff6760
@crazystuff6760 4 жыл бұрын
The BEST explanation of Quick Sort Ever!!! Thanks for this wonderful video.
@rayhane6497
@rayhane6497 8 жыл бұрын
I finnaly understood this sort :D .. Thank you so much
@LamiAtZenith
@LamiAtZenith 8 жыл бұрын
Best tutorials out there! Better than my lectures man thank you!
@pauldavid_d
@pauldavid_d 5 жыл бұрын
facts
@sekhardeka498
@sekhardeka498 4 жыл бұрын
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....
@bit_FLIP
@bit_FLIP 8 жыл бұрын
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
@doctorlazarus8854
@doctorlazarus8854 5 жыл бұрын
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?
@lravikiran88
@lravikiran88 8 жыл бұрын
THIS SORTING WILL TAKE SOME TIME TO UNDERSTAND
@BiswasTharakath
@BiswasTharakath 7 жыл бұрын
Watching it twice did the trick!
@antoniomiranda7472
@antoniomiranda7472 5 жыл бұрын
It takes 20 minutes and 38 seconds to be precise ;)
@aashishgoyal1436
@aashishgoyal1436 5 жыл бұрын
This is the best and easiest partition function i ve seen in quick sort implementation. simply too good
@highmem
@highmem 2 жыл бұрын
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.
@sushiwalker232
@sushiwalker232 8 жыл бұрын
"Just think about it and you should be able to get it. " towards the end hahaha
@AbhishekSingh-ky2dn
@AbhishekSingh-ky2dn 5 ай бұрын
Who is still in 2024 ?hit like
@minthep2611
@minthep2611 2 ай бұрын
I m in 2025
@Rajeshkumar-rj5my
@Rajeshkumar-rj5my 6 жыл бұрын
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!
@qazizaahirah4168
@qazizaahirah4168 6 жыл бұрын
Can we take a moment to appreciate your explaining skills. Great Job!
@ahmedsafwat85
@ahmedsafwat85 9 жыл бұрын
Very cool! The best video explaining Qucik Sort.
@shaikpspk
@shaikpspk 2 жыл бұрын
We really miss you sir 😢😔💔 #rip #humblefool
@nothingpersonal21
@nothingpersonal21 7 жыл бұрын
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.
@holystone3736
@holystone3736 7 жыл бұрын
Guys this alghoritm is a mess
@mycodeschool
@mycodeschool 10 жыл бұрын
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.
@srikantjenakumar
@srikantjenakumar 4 жыл бұрын
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.
@shakirasunshinez
@shakirasunshinez 4 жыл бұрын
wow i did not realize that
@akshitbansal352
@akshitbansal352 4 жыл бұрын
Did you get the answer to that?
@folcotandiono6736
@folcotandiono6736 8 жыл бұрын
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
@ericnawnaw
@ericnawnaw 5 жыл бұрын
I got confused at first too. But it's just extra operation and doesn't affect the correctness of Algorithm.
@tarunkumarreddy5020
@tarunkumarreddy5020 3 жыл бұрын
@@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....
@joshuaopata6433
@joshuaopata6433 2 жыл бұрын
the only guy who has been able to make me understand quicksort this easy
@swaritthakare3081
@swaritthakare3081 7 жыл бұрын
really ,really appreciate your effort for teaching algorithms in simplest way existed .
@ninetynin
@ninetynin Жыл бұрын
wishing the legened is still alive rip humblefool
@MrStarTraveler
@MrStarTraveler 7 жыл бұрын
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
@ravipapisetti1
@ravipapisetti1 6 жыл бұрын
I agree, with your analysis.
@syedsouban9870
@syedsouban9870 6 жыл бұрын
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
@ramrai2642
@ramrai2642 5 жыл бұрын
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
@kaipulla77
@kaipulla77 5 жыл бұрын
Can you give me an array input for which this doesn't work, please? I tried with duplicates and it works. Just curious.
@atulmalakar
@atulmalakar 5 жыл бұрын
@@kaipulla77 5 4 3 2 1
@youknwmyname1323
@youknwmyname1323 2 жыл бұрын
Beautifully explained with animations in the video while doing the dry run!! Thankyou!!
@vigneshk8139
@vigneshk8139 4 жыл бұрын
I'm watching this in Feb 2020. The best explanation on quick sort algorithm.
@HeyltsKenzi
@HeyltsKenzi 4 жыл бұрын
Im going to win a medal at IOI 2020 in your memory Lord Harsh.R.I.P
@rohithdsouza8
@rohithdsouza8 4 жыл бұрын
The guy explaining the video is not Harsha but it's Animesh and he's still alive.
@alizafar4399
@alizafar4399 7 жыл бұрын
what does "O" and "n" in "O(nlogn) " refers to?
@Ramgautam12345
@Ramgautam12345 7 жыл бұрын
Ali Zafar it is known as the big Oh notation, to calculate the complexity and efficiency of the program. read about it.
@divelikejunk8557
@divelikejunk8557 7 жыл бұрын
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.
@namooman6447
@namooman6447 7 жыл бұрын
Thanks mycodeschool..Your videos are simply awesome.
@alive4metal731
@alive4metal731 Жыл бұрын
best quicksort explanation I've seen. thank you
@subbuch89
@subbuch89 7 жыл бұрын
Did you consider negative scenario where all the elements on the left of the pivot are less than the pivot in the decreasing order ?
@KARTHIKPANCH97
@KARTHIKPANCH97 4 жыл бұрын
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
@AkshayKumar-dz5ts
@AkshayKumar-dz5ts 7 жыл бұрын
//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
@sagardafle
@sagardafle 7 жыл бұрын
Thanks man !
@Lollipop69420
@Lollipop69420 6 жыл бұрын
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
@vivektodmal1
@vivektodmal1 6 жыл бұрын
Why u need 2 temp variables you can use the same one for both the purposes in partition function
@farooqansari
@farooqansari 6 жыл бұрын
Not all heroes wear capes.
@purplebeard806
@purplebeard806 6 жыл бұрын
Program takes inputs but does not sort :(
@poompataipuntidpong3700
@poompataipuntidpong3700 9 жыл бұрын
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!!
@mgeasley
@mgeasley 4 жыл бұрын
omg...finally..... the best quick sort explanation on the internet. THANK YOU
@ManikantaRaju
@ManikantaRaju 9 жыл бұрын
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!
@mycodeschool
@mycodeschool 9 жыл бұрын
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.
@ManikantaRaju
@ManikantaRaju 9 жыл бұрын
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!
@anuragghosh9710
@anuragghosh9710 7 жыл бұрын
sir could you provide the code link?
@muhammadzainzaheer2072
@muhammadzainzaheer2072 7 жыл бұрын
//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
@anuragghosh9710
@anuragghosh9710 7 жыл бұрын
thank u Muhammad Zain Zaheer
@racastilho
@racastilho 6 жыл бұрын
Super clear, best instructor ever! Thank you, sir!
@sainaths3655
@sainaths3655 9 жыл бұрын
Is there any link to learn Heap sort which is explained by you ?
@mycodeschool
@mycodeschool 9 жыл бұрын
SAINATH D'LEH Not yet,, we need to create one.
@FarhanArRafi
@FarhanArRafi 9 жыл бұрын
mycodeschool yeah, bro make some heap sort video ASAP. thanks again.
@akhilsuresh2560
@akhilsuresh2560 8 жыл бұрын
+mycodeschool IT will be very helpful ..btw gr8 work!!!
@ZuestTV
@ZuestTV 8 жыл бұрын
+mycodeschool no heap yet ):
@mycodeschool
@mycodeschool 8 жыл бұрын
+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. :)
Analysis of quicksort
20:17
mycodeschool
Рет қаралды 308 М.
Merge sort algorithm
18:20
mycodeschool
Рет қаралды 2,2 МЛН
Hot Ball ASMR #asmr #asmrsounds #satisfying #relaxing #satisfyingvideo
00:19
Oddly Satisfying
Рет қаралды 51 МЛН
Would you like a delicious big mooncake? #shorts#Mooncake #China #Chinesefood
00:30
A* (A Star) Search Algorithm - Computerphile
14:04
Computerphile
Рет қаралды 1,1 МЛН
The Quicksort Sorting Algorithm: Pick A Pivot, Partition, & Recurse
26:31
Back To Back SWE
Рет қаралды 162 М.
Learn Quick Sort in 13 minutes ⚡
13:49
Bro Code
Рет қаралды 290 М.
Analysis of Merge sort algorithm
18:21
mycodeschool
Рет қаралды 540 М.
Quicksort: Partitioning an array
4:48
KC Ang
Рет қаралды 576 М.
10 Sorting Algorithms Easily Explained
10:48
Coding with Lewis
Рет қаралды 33 М.
Insertion sort algorithm
14:15
mycodeschool
Рет қаралды 1,5 МЛН
Check if a binary tree is binary search tree or not
16:30
mycodeschool
Рет қаралды 375 М.
Rust Functions Are Weird (But Be Glad)
19:52
Logan Smith
Рет қаралды 127 М.
Sorts 8 Quick Sort
9:12
RobEdwards
Рет қаралды 194 М.
Hot Ball ASMR #asmr #asmrsounds #satisfying #relaxing #satisfyingvideo
00:19
Oddly Satisfying
Рет қаралды 51 МЛН