Java Quick Sort
HTML-код
- Опубликовано: 27 июл 2024
- Get the Code Here: goo.gl/zPL7r
Welcome to my Java Quick Sort tutorial! In most situations the Quick Sort is the fastest sorting algorithm.
In essence, the quick sort works by partitioning arrays so that the smaller numbers are on the left and the larger are on the right. I'll cover what partitioning is in this video.
The Quick Sort then recursively sends small parts of larger arrays to itself and partitions again. Between the code and the video you will completely get it in the end.
You're very welcome :) I'm very happy that more people are enjoying the videos
You're very welcome :) I'm happy you like them!
Thank you :) I used to do stuff like that in college. Fun stuff. I'm going to revisit algorithms and data structures soon
Sometimes positive reinforcement is all we need :) Its great that you figured it out! Great job
Awesome tutorial! Most of the other algorithms I've seen do this using recursion (I suspect to TEACH recursion🙂), but they don't do a good job of visually demonstrating what's happening with the "pointers" (i.e. - inidces). Your explanation helped me to understand this much better. 👍🏿
Thank you for taking the time to tell me :) I'm happy I could help
Thank you :) I hadn't planned on covering that because I don't think java lends itself to functional programming. I'll look into it though. Thank you for the idea
I really enjoy your tutorials! you explains things clearly especially with the visuals and by going through the code step by step
Tak. Jeg er meget glad for, at du nyder det. Jeg tror, jeg vil have mere fritid i denne uge, så jeg bør være i stand til at få flere videoer ud i denne uge
I will definitely cover both languages. They shouldn't be any trouble. I will do my best to make the videos fun. This month either android or java game tutorials will finally begin. Either way I need c
Thank you :) Sure snake is easy. This will be the last tutorial before I either do Android development or game development for desktops. I can do a great deal more on the desktop, but I know people want to see Android. Maybe I should have another vote? One or the other will be next, meaning it will start this month
Sorry about that. I sort of was hoping people would get the code and play around with it. Later in the tutorial series I tried to do a better job at showing the algorithm in action
Thank you :) I try to do my best
Thanks for doing these videos man!
You're very welcome :)
thank you Derek. I have learnt how to use merge sort and quick sort after your video. Many thanks
I'm happy I could help :)
The code may help you understand this easier then I can in the little comment area here. Here is all the code newthinktank. com/2013/03/java-quick-sort/
It is heavily commented
Feel free to ask questions
really appreciable, concepts are very clearly explained, thank you 👍👍🙂🙂
Thank you very much :)
Thank you so much for the help. hopefully il find more videos by you that are the topics of my logbook. thanks
Trollacaust You're very welcome :) I have a ton of Java videos. Well over 100.
how do you know which value to put as your pivot?
Thank you :)
Great tutorial, I am currently preparing ahead for my Data Structures class, and have to say that your video helped me to understand this algorithm very well.
I wanted to ask, whats the difference between your algorithm and other algorithms that use another method to create partitions?
Also, I see that some implementations of Quicksort differ when it comes to selecting the pivot. Can you explain whats the best choice for pivot in general?
Great tutorials! Will you be covering Functional Programming in the future?
I'll probably start android this month over regular java games because I have been getting so many requests for it
Hey Derek!
Please do one regarding C or C++ game development. I've been searching for quite a while for a decent series but haven't come across one. People either give out extremely inefficient ways of doing something or their videos are very outdated. If you could make a series with your own twist, that would be great.
People also have trouble explaining such a complicated language like C++. I would like to see how you do with it!
Thanks.
Awesome sauce man! :D
I didn't get the the line 19 and line 26 at time: 5:01 :
while(leftpointerpivot);
you are using two While loops but both of them don't have " { } " and code in between them.
I would like to know how they are working. Could you please explain how they are working?
Thanks :-)
thanks man, you help me a lot!
Derek maybe you can add Ant Colony Optimization algorithm, and some other genetic/evolutionary algorithms. Your videos are awesome. Thanks :)
Hi Derek,
Could you please explain what is the meaning of below code line and how this pivot value from the left is being used in this code? I could not find any relation between this code line and the actual code!
System.out.println("Value in left " + theArray[left]
+ " is made the pivot");
Hey Derek, can you tell me why does this algorithm not work if you take the left array element as the pivot?
@Derek Banas Love your videos man. I finally got the whole MVC pattern thingy watching all your videos. Can you make a tutorial on developing games? Particularly, i'm interested in Snake, etc. Thanks!
Please explain why you do the last swap outside of the while loop on line 92 and why its with "leftPointer" and "right".
cuz right is the pivot and you know left pointer is greater than the pivot, you want to swap them before you split your array
Wow. thanks. This helps those like me who are more visual learners.
__dxmole__ You're very welcome :) I'm glad I could help
15:50, Why do you swapValues(leftPointer, right) here? I don't understand where this is coming from.
Looking forward to your android game tutorials Derek! Thumbs up to you ^_^
I hope there is some issue with the partitioning logic.
I gave the input [51, 11, 12, 13, 21, 14, 50, 35, 37, 35]. The pivot value selected is 35.
The output array is [35, 11, 12, 13, 21, 14, 35, 50, 37, 51] which is not expected.
I found the same issue! if we have 35 involved there, we have a problem
your explanation was very clear until minute 10:00 when 21 was finished as the pivot and then you used 19 as the pivit and 52 which was at the 4th position was suddenly placed at the end of the array. That really threw me for a loop. I did some reading up and figured it out. This link helped me ece.uwaterloo.ca/~cmoreno/ece250/quick-sort-complete-example.pdf
Other than that very nice tutorial
Thank you for the input and the link :)
can you do a partitioning using the middle of three technique
@9:27 you said how nothing changes because according to the new pivot 19, there are no changes but right under you moved the 21 and 52 (swapped them) why ?
I cover both recursion and the merge sort in the same video here newthinktank. com/2013/03/java-recursion/
If you want to watch it on RUclips search for java recursion on my youtube channel.
i hope it helps :)
@GreenCheese500:
I think these "while" sections are stepping leftPointer or rightPointer to the next position where they can be used for swapping.
I.e the first "while" section does nothing just make leftPointer step to the position where it's pointed value in array is less than pivot value.
Then the "while" exists and the program goes to the next statement.
Hey Derek! In my class, we are currently learning linked-list (made manually, as in no importing linked list). I've finally got that complete, however, our professor would like for us to have the linked list printed in a sorted manner. He would like for it to sort as you enter data. For example, I add the number '3', then I say to add another node. If I enter '1', the '1' node will be moved before the '3' node. How would you do this? Could you possibly make a video tutorial, or would you be able to help me via comments if I supplied my source code?
Thank you!
You don't have to do a sort as a separate step. Do a linear search for the position where the new number should be inserted, and insert it there.
Why make a variable ArraySize when you can use Array.length ?
The length is precalculated and stored in the variable rather than being calculated each time using array.length. It can also prove to be less tedious during implementation.
It would be cool to teach java nio and java aio! great channel and thank you!
+Guilherme Alves Thank you :) More Java coming soon
Why this video isn't with Java algorithms playlist? I cant find this attached to any playlist. Whats wrong with it? :)
Hey Derek,
What is the meaning of the semicolon inside the while loop?
Those while loops are the ones that make the pointers move. There is nothing inside the while statement so you need to close that statement with the semicolons.
Hello ,
You mean the one on MVC specifically right ?
Or
Is it one that I missed, mistakenly ?
Thanks
Thanks for the video.
blizzmademegod You're very welcome :)
It's very easy to understand this algorithm, but is hard to implement it. However, good video!
Thank you :)
May you have a good life
Hadi hadi halim I wish you all the best in life :)
Wouldn't it also be correct to call qSort as qSort(i,m);
qSort(m+1,j); ?
Where i = 0 and j = array.length?
Ty for,these videos
Speed, Java is too slow for anything involving 3D
Yes, but c will come first because I need it for android
difficult to understand how the values are swapping and how the pointers are moving in the videos. Maybe add some animations?
Probably start by understanding recursion
understanding recursion? how does that have the same effect as adding arrows to a video? Anything you can do recursively you can do iteratively, so the point is mute (unless were talking about complexity... and we're not...)
Thank you derek.
Great Video
Thank you :)
Hi Derek, just wanna ask, can i simulate these codes that u gave? so i can learn it more, but i can't because i don't know the meaning of other lines..
Just ask what lines, many ppl will probably explain them for you
umm about importing arrays, how does it work? cause i never tried it before. thanks :)
+Olive Grace Lagrosa If you mean the import lines at the top of the code? That's how you can import certain packages in the java language so that you can use them throughout the class you're coding. Or do you mean how arrays work?
how do arrays work when you import it?
importing it does nothing, other than allow you to use them. It applies to many other things. How arrays actually work is actually complicated to explain briefly, probably can find a few videos explaining them but actually understanding them and using them without thinking about them much takes a lot of practice.
sir plz provide java frameworks as struts , spring,hibernate and also another example of mvc
sripriya nagaraju I'll cover that ASAP
I like your videos a lot but this one got a little confusing.
I can't tell how you choose the pivot and every time left and right pointers meet each other, i don't understand their positions in the next figure of the array. Can you go deeper in these?
Thanks very much, your classes are awesome!
I use a translator.
Min översättare talar svenska :)
Hi, when is try to run the code explained by you, it gives an error "Could not find or load main class". Also on the 10th line we have a warning "The public type Partitioning must be defined in its own file".... Could you please check and help me once with this explanation.
kiran katkam Make sure you save the java file in the src directory
Derek Banas -- Yup, I have saved the file in SRC but could not get the output.
Also, could you please help me with the code to implement the below partitioning algorithm...? I'm finding this difficult to implement.
Thanks a lot in advance.
Partition Algorithm :
pivot = pick a random element out of the array A
swap the pivot with the last element of A
small_count = 0
for each element x of array A except the last
if x < pivot
swap x with A[small_count]
add 1 to small_count
swap A[small_count] with the last element of A
Example Run:
Array after picking 4 as pivot and swapping with last
pivot = 4, ^ indicates current array element in for loop.
7 6 5 2 3 8 1 9 4 small_count = 0
^
next element
7 6 5 2 3 8 1 9 4 small_count = 0
^
next element
7 6 5 2 3 8 1 9 4 small_count = 0
^
next element
7 6 5 2 3 8 1 9 4 small_count = 0
^
swap A[0] with 2, add 1 to small_count, next element
2 6 5 7 3 8 1 9 4 small_count = 1
^
swap A[1] with 3, add 1 to small_count, next element
2 3 5 7 6 8 1 9 4 small_count = 2
^
next element
2 3 5 7 6 8 1 9 4 small_count = 2
^
swap A[2] with 1, add 1 to small_count, next element
2 3 1 7 6 8 5 9 4 small_count = 3
^
next element
2 3 1 7 6 8 5 9 4 small_count = 3
^
swap A[small_count] with last element
2 3 1 4 6 8 5 9 7 small_count = 3
Now elements 0 to small_count - 1 are < pivot
elements from small_count on are >= pivot
If partition partitions array a and returns small_count:
quicksort(a, first, last)
if (first == last) return
small = partition(a, first, last)
quicksort(a, first, first + small)
quicksort(a, first + small + 1, last)
can somebody explain this part to me. I don't understand why leftPointer is swapping with right.
swapValues(leftPointer, right);
So the smaller number lands up behind the bigger number.
Thank you very much for your videos. They're very well done and very helpful.
Is "H" the right pointer? Why "H?"
I'm happy they helped :) Sorry but I don't understand the question
@@derekbanas
Thank you so much for replying, definitely did not see that coming. I was referring to around 7:10 where the pointers seem to be indicated with an "L" and "H"
H represents the Highest (Largest Number) while L the lowest. Sorry for the confusion
@@derekbanas I know it's been 2 years, but I realized that I never responded to your comment, when at the time and now too, I had been so appreciative and touched that you took the time to even reply and clarify. So if you ever see this, thank you very much for all the tremendous work that you have done in helping so many with your endless amount of educational videos
referring to last 2 mins of video, you swapped 45 with 40 which is not true.
can you please explain why 45 was swapped by 40. As per me it should be swapped by 39
Can anyone please explain why 53 is still at the left side of pivot 30? @1:13
I think it
I have to honestly say I found your explanation a little confusing, even though I already knew exactly how quicksort works. What I would do if I were you, is to have some animations of the numbers moving to different places. You simply say that the numbers swapped and showed a slides of them after being swapped, which sometimes makes me lost. It would be a lot easier if I could see them actually being swapped (animation moving the numbers around instead of slides). It is a great video though! ty
Thanks!
AHTOIIIKA Your welcome :)
Can you make a merge sort video?
good video
Thank you :)
Hej Kære Coach,
Video serie på algoritmer er en fornøjelse at følge.
Det har føjet til min dygtighed sæt.
Alle takket være dig selv mindre hjælp.
Jeg kunne ikke vinde guld, da jeg fik timingen forkert: (
Pas.
How are you supposed to memorize all this??
Mummie560 Don't try to memorize, it but instead focus on understanding the process. I found that if I modeled algorithms using UML that they were much easier to understand and memorize. Here is a UML course ruclips.net/video/OkC7HKtiZC0/видео.html
thanks for the vids .... BUT, are you afraid to of silence in your videos? It would be a lot easier to follow if you left out the fluff when talking and just said what is happening and then let the diagram run or typed the code in silence and then talked again when showing something new
Sorry you didn't like the style of the video. Making edited videos is kind of what makes me different. I'm certain my videos aren't for everyone
@@derekbanas thanks for responding. Sorry to come across as a controlling ass. Just my consideration on what would make your videos easier to follow for me. I still appreciate the videos.
Do you actually speak Danish or do you use a translator?
If you do:
Pratar du Svenska också?
I think you should have explained your code more, telling us to just swap leftPointer and right with out way you did so left me more confused then when i came here. I think that this tutorial is only good for the people who want to get the overall idea but not understand most of what goes on.
+Tamir Offen If you follow his tutorials I think this video make perfect sense. He can't start from the beginning on every single video.
You have to pay attention to. He initially declared that the right was the pivot point and when he demonstrated that you would swap the pivot point with the left pointer he demonstrated that in the code. I don't know if I'm late lol.
are you Ed Helms?
Yes, but don't tell anyone :)
You need C for android? How come?
I don't understand it
its not the speed , its just not very clear
This is confusing ._.
this and insertion sort KO'd me ;(
+spacepod100 Experiment with it and try looking at the changes using a tree like I show here ruclips.net/video/63BBWWsqsT0/видео.html
He is smart but too fast beginner
too fast for beginner
This is a bad explanation by your standards Derek.
go slow..
so many cringes while watching this
cannot stand your intonation when you explain. FINISH THE SENTENCES. It seems like it's a single sentence going on forever
+Dat Huy Richard Le Sorry about that. I edit out all of the pauses to speed up the videos.
Disagree with +Dat Huy Richard Le, Derek has perfected tutorial video with his video editing and tempo, and it's a major reason his are the top around for the subject matter. The alternative would be watching a video full of silent pauses, and would easily double the length of videos. Keep up the great work, Derek!
+Dat Huy Richard Le Derek tries to complete the whole tutorial as fast as he can in order to pack up everything and to minimize the time while holding the subject crystal clear and this is why a lot of people choose to watch his video tutorials. Most of his videos are smaller than 15mins or at most 20 mins.
+Derek Banas I like the edited down versions normally. For this example it is quite difficult to follow the swap process because you talk quite fast. We can alway pause or look at the code though, so no worries.
Do you edit out all of the pauses manually or do you have a program that does it for you?
very fast your english is like blablabla not properly understand