Quicksort Sort Algorithm in Java - Full Tutorial With Source

quicksort is one of the fastest sorting algorithms out there but it can also be one of the hardest to understand in this video we'll go through exactly how the quick sort algorithm works in detail in a way that i promise you'll understand then we'll walk through coding our own quicksort implementation in java my name is john i'm a lead java software engineer and i love sharing what i've learned with you in a clear and understandable way i also have a full java course available and a link down in the description if you're interested let's get right into it okay before we just dive into eclipse and start coding it's important to know how the quick sort algorithm works the whole quick sort algorithm is basically just three steps the first step is choose one of the numbers in your array as the pivot so you might be thinking what do you mean choose a pivot i just choose any number in my array here as my pivot and essentially the answer is yes it's not so much that the pivot you pick isn't important but how you choose a pivot isn't important to understanding the actual algorithm what we're going to be doing is just choosing the last element in the array as the pivot and i'll show you how that works then at the end of the video we'll go over a better strategy for picking the pivot which is also still really easy to implement after you've chosen the pivot the second step is to move all numbers in the array that are lower than the pivot to the left of it and all numbers that are higher than the pivot to the right of it this step is also called partitioning so since we're using the last number as our pivot in this case it will be seven and the partitioning step will put all numbers less than 7 on the left side of the 7 so that means that the 1 the 3 the 4 and 5 will all be moved to the left of 7 and 8 and 9 will be moved to the right of 7. so after that partitioning step all the numbers to the left of 7 are smaller than 7 and all the numbers to the right of 7 are larger and the number that we chose for our pivot the 7 in this case is actually in its final spot in the array the partitioning step is probably the most complicated to code but don't worry we'll go through that part step by step after partitioning the third step is to recursively quick sort all the values to the left of that pivot and all the values to the right of the pivot and when we do the quick sort for those sub arrays it's done exactly the same way we just did it so first we would do the quick sort for the left portion here and we'll repeat the same steps that we did before which are first choose a pivot and again we're just going to use the last number as the pivot which in this case would be 1. then we do the partitioning where we take any number that is greater than 1 and put it to the right of 1 and any number that is less than one and put it to the left in this case they all happen to be greater than one so they all go to the right of one then after the partitioning step of that quick sort we then recursively quick sort all the elements to the left of the pivot and all the elements to the right of the pivot there's no elements to the left of the pivot because our pivot was 1 in this case so we just have to recursively quick sort all the numbers to the right of the pivot and again we do that exactly the same way where we first choose a pivot which is going to be the last number for us or five then we move all the numbers in this subarray that are less than five to the left of five and all the numbers that are more than five to the right in this case three and four are both less than five and they're already to the left of five so there's nothing we have to swap then again we recursively quick sort the sub arrays to the left and right of that pivot since there's nothing to the right of 5 we only have to recursively quick sort the subarray to the left of 5 which is 3 and 4. again to quick sort this subarray we first choose a pivot which for us is going to be the last number in this array four then we do the partitioning again where in this case three is less than four and it's already to the left of four and then we recursively quick sort each sub-array to the left and right of four in this case we only have a subarray to the left of four here which is just the number three the number three is just one element so it's already sorted so now we've completed quick sorting all of the numbers that were originally next to the seven but remember we still have to recursively sort all the numbers to the right of the seven and of course we just quick sort this in exactly the same way first we choose a pivot which in our case we're just going to choose the last number which is nine then we do the partitioning where in this case there's no changes that we have to make because 8 is less than 9 and it's already to the left of 9. then we recursively quick sort these sub-arrays to the left and right of our pivot in this case we only have a subarray to the left of the pivot which is just the number 8. since it's only one element it's already in order and there's nothing that we have to do at that point we've completed all of the recursive quick sorts and we finally end with our perfectly sorted array and now for the fun part let's get to coding as always with these sorting algorithm tutorials i'm starting here with a little bit of setup just so we can test the sorting algorithm that we write this first part will generate an array of 10 integers randomly between 0 and 99. so that just gives us a random array of ins to sort then we print out that array here in its initial completely random order then we call our quicksort method here which we are going to write where all the magic happens and it sorts our array from smallest to largest and then after that we print out the array again hopefully in perfectly sorted order so let's go ahead and jump into that quick sort method which is currently completely empty and we'll start our implementation you may have noticed that it's actually taking in three parameters the first one is the actual array that it's going to sort that makes sense but then it also takes in a low index and high index if you remember from the demo quick sort is a recursive algorithm where after we do the partitioning where we put all the numbers less than the pivot to the left and all the numbers higher than the pivot to the right we recursively quick sort all the numbers in the left partition and recursively quick sort all the numbers in the right partition that recursive step is why we need the low index and the high index when we tell it to recursively sort the subarray we don't want to just tell it to recursively sort the entire array again so we pass in basically a range a low index and a high index of that particular subarray so that it can properly do the recursive quick sorts however that does make it so that when you initially call the quick sort method in addition to passing in the array you need to pass in the low index and the high index too which of course when you want to just sort the entire array the low index is going to be 0 and the high index is just going to be the last element in the array which is just going to be the length of the array minus 1. near the end of the video i'm going to show you a trick where you can get rid of this for your initial quick sort call and just have to pass in the array that you want to sort all right now let's get to writing our quick sort method now what was the first step in our quick sort algorithm it's to choose a pivot and remember for our purposes we're just going to choose the last number as the pivot so to do that we'll just create an int and we'll call it pivot and set it equal to the value of the array at that high index that's passed in here remember that this is a recursive algorithm so we can't always just pick the last element of the entire array that we're sorting as the pivot in any given recursive step in the middle we might just be sorting one small sub array portion of the entire array and that'll be passed into this method recursively with a low index and a high index indicating that range that we want to be recursively sorting right now so the last element of that particular range that we want to be sorting is going to be passed in as high index now we've done the easy part we've chosen a pivot now for the hard part the partitioning where we have to move all the numbers lower than the pivot to the left of the pivot and all the numbers higher than the pivot to the right of the pivot how exactly are we going to do that in the code here's what we're going to do so we chose a pivot right that is just going to be the the last number in this case 7. so 7 is our pivot and for now we're just going to ignore that and let it be and just focus on all of the other numbers then what we're going to do is create two variables that we're going to use as pointers one we'll call the left pointer and we're going to start at the leftmost part of the array and the other will call right pointer and we're going to start it at the rightmost portion of the array we're going to start with the left pointer what we're going to do is start walking through our array a single element at a time until we find an element that is larger than the pivot so first we look at the number one is one larger than seven no so then we move that left pointer over to look at the number eight is eight larger than seven yes so we'll stop there and leave that left pointer pointing at the number eight and then we move on to our right pointer and what we're going to do with the right pointer is start walking from the right side of the list one element at a time to the left until we run into a number that is less than our pivot so our right pointer starts looking at the number five is the number five less than seven yes so we stop there with the right pointer pointing at the number five so at this point our left pointer is pointing to a number that is greater than our pivot and our right pointer is pointing to a number that is less than our pivot at that point we are going to swap the numbers at those two pointers so our eight will move over here where the five was and the five will move down here where our eight was then we repeat that process we move our left pointer over one spot so our left pointer is pointing at the number three is three greater than seven no it's not so we move our left pointer over to point at the number nine is nine greater than seven yes so we stop there with the left pointer pointing at nine then we move over to our right pointer and move it to the left to look at the number four is four less than seven yes so we stop there at this point our left pointer is pointing to a number that is greater than seven and our right pointer is pointing to a number that is less than seven at that point we swap the two numbers that our left pointer and right pointer are pointing to then we continue that same process we move the left pointer over one spot at this point our left pointer and right pointer are pointing to exactly the same element once that happens we want to stop that process of moving the left pointer and right pointer toward each other and then what we're going to do is swap our pivot with the number that our left pointer is pointing to so in this case the number nine so that will move our 9 out to here where our pivot was and our 7 in here where our 9 was at that point the partitioning step is complete so you'll notice that all the numbers less than 7 are to the left of 7 and all the numbers that are greater than 7 are to the right of seven after that partitioning happens we're going to recursively quick sort the sub array to the left of our pivot and recursively quick sort the subarray to the right of our pivot that partitioning step is probably the most important part of the quick sort algorithm let's put what we just talked about into some code first we'll declare our two pointers left pointer and right pointer so we're going to have int left pointer and we're going to start the left pointer at the left side of the array that we're sorting so we can just initialize it to low index and we'll also create an int right pointer and we'll start it at the high index of the array that we want to sort now we need to create a loop that will move the left index and the right index toward each other until they hit each other so to do that we're going to create a while loop and the condition of our while loop is going to be while the left pointer is still less than the right pointer so once our left pointer runs into our right pointer this expression will evaluate to false and knock us out of our loop so inside of that loop we want to walk our left pointer from left to right until we find a number that is higher than the pivot or we hit our right pointer so to do that we're going to want an inner while loop so while the value of the array at that left pointer is less than or equal to the pivot and our left pointer is less than our right pointer so while that is still the case we want to increment our left pointer so left pointer plus plus so this will keep incrementing our left pointer until the value of the array at that left pointer is greater than the pivot or if it's walking from the left and never finds a value that's greater than the pivot eventually the left pointer will pass the right pointer and will also kick us out of this loop and we'll do exactly the same thing for walking from the right side we'll have another inner while loop we're going to walk from the right until we hit a number that is less than the pivot or until we pass our left pointer so it's going to look very similar while array at right pointer is greater than or equal to the pivot and left pointer less than right pointer because we want to move the right pointer from right to left we actually have to decrement it each time in the while loop instead so we'll do right pointer minus minus at this point we have a left pointer that's pointing to something that is larger than the pivot and a right pointer that is pointing to something smaller than the pivot and now we just want to swap those two numbers since we're going to have to do that swapping in a couple of places in our algorithm it's probably the best to do that in its own private method so let's scroll down here and create a new private static void method that we're going to call swap and it needs to take in three parameters one is the array that contains the two elements that we want to swap then it also needs to take in the two indexes that we want to swap so int index one and int index two in order to do a swap we just need to create a temporary variable we'll just call it temp to hold one of the values that we want to swap so in temp equals array of index 1 then we set the value of the array at index 1 equal to the value of the array at index 2. finally we set the value of the array at index 2 equal to our temp variable so back up here in our quick sort method remember that at this point we wanted to swap the elements that were at our left pointer and right pointer so to do that now we can just call our swap method and pass in the array and also the left pointer and right pointer as the indexes that we want it to swap so what these while loops will do is keep moving the left pointer and right pointer closer and closer to each other swapping elements when it needs to until those pointers meet now remember from our demo that at that point what we want to do once our left pointer and right pointer meet we want to swap our pivot in with the value that our left pointer is pointing at like this so to do that it's very easy we can just call our swap method again pass in the array and we want to pass in our left pointer as the index of one of the elements we want to swap for the other index we actually want to pass in high index and that's because we know that this high index will be the index of our pivot because we've always chosen the last element as our pivot at that point the partitioning step is done all the numbers that are lower than the pivot should be to the left of it and all the numbers higher than the pivot should be to the right of it so the only step left is the recursive step where we're recursively quick sorting the partition to the left of the pivot and recursively quick sorting the partition to the right of the pivot so first let's make the recursive call for the partition to the left of the pivot so we'll recursively call our quick sort method we need to pass in our array but we also need to pass in a low index and a high index so at this point remember our pivot is right here so what we want to do is call quick sort for just these four elements so what do we need to use as the low index and the high index that we pass in well our low index will just be the very first number in the array that we were sorting in the first place right and that was passed in as low index to this method so for the low index we can just pass in low index now for our high index we want it to be the last element in the subarray that we're sorting now since our left pointer is going to be pointing at our pivot here the high index of this left partition is actually just going to be our left pointer minus one so we can just pass in left pointer minus one next we need to recursively quick sort the right partition and to do that is going to be very similar we'll call the quick sort method recursively pass in our array so what do we need to pass in for our low index well it's just going to be one number past our pivot which is where this left pointer is pointing so we can just use left pointer plus one so we'll just pass in left pointer plus one and for the high index that we pass in we can just pass in the high index of this entire array that we were sorting so we can just pass in high index before we finish this algorithm though there's still one case we haven't accounted for yet and that's the case where as these recursive calls keep going and going eventually it's going to be told to recursively sort a list of just one element at that point because an array of just one element is already sorted it can just return there's nothing that it has to do so we actually want to put that logic here at the top of our quicksort method so here if the low index is greater than or equal to the high index then we know we're dealing with a subarray of just one element and we can just return and there's nothing else we have to do okay and with that that should give us a working quick sort so let's go ahead and run our test program with 10 random ins and see if it works here we go okay so i printed our before and completely random order and then printed the after where everything looks to be perfectly sorted awesome let's go ahead and run it a few more times just to make sure everything is looking okay okay so now that we know our quicksort algorithm is working let's do a little bit of code cleanup to kind of optimize it and then we'll see exactly how fast quicksort is first just for code readability remember how we had three main steps in our quick sort algorithm choose a pivot do the partitioning and then do the recursive quick sort calls so here in this whole section right after we choose the pivot but before we do those recursive quick sort calls this is basically all partitioning code so it might be nice to split this out into its own method so to do that you can just highlight all the code that you want to put into that partition method and if you're using eclipse you can hit alt shift m that'll pop up this window here and all you need to do is name the method that you want to create so since this will be our partition method we will call it partition then just go ahead and hit ok and it automatically created our partition method with all the code that we wrote so now our quicksort method is even easier to read choosing a pivot performing the partitioning and then recursively quick sorting the left and right partitions next i mentioned at the beginning of the video that how you choose the pivot can be important because there are certain situations where if you choose the pivot really poorly it could result in worse average performance for quick sort so while choosing the last number in our array does work fine a strategy which ends up with a bit better average runtime is actually choosing a pivot at random that might sound like it'll be really complicated to implement but it's really just a pretty simple modification to what we have so far here's how that's going to work so we're going to choose a random element in this array as the pivot so let's say we randomly choose the number three instead of trying to do the partitioning with this three still in this same spot in the list what we're going to do is actually swap this element with the last element in our list right away so that way the three that we chose as our pivot is now at the end of the list and completely out of the way and at that point after we've swapped that pivot and put it at the end of our list everything else works exactly the same way that it did before we do the whole partitioning step with the rest of the array and at the end of that step we still swap out our pivot with the index of our left pointer so to do that in the code we're going to start here by creating an int that we'll call the pivot index this is going to be the index in our array that we're going to choose randomly as our pivot and in order to choose that randomly we are going to use the random class so we'll say newrandom.nextint and what we're going to pass into this method is high index minus low index and then we're actually going to add the low index this calculation will give you a random index somewhere between the low index and the high index that are passed in so now instead of just using the value of the array at the high index we want to choose the value of the array at the pivot index that we just randomly generated and then we need to do the swap that we talked about where we swap that random pivot with that last element of our array so to do that we can just do swap pass in our array and then swap our pivot index with the high index so that's all you need to change in order to choose your pivot randomly so you should be able to rerun your code everything should still be sorted perfectly except your algorithm will now perform a little bit better in the average case one other thing here is that it's kind of ugly that at the beginning when you call this quick sort method initially you have to pass in the low index and the high index it would be nice if you could just pass in the array that you want to quick sort like this well what we can do is actually create another private method and we'll actually also call it quick sort so we will overload the quick sort method overloading is when you have more than one method that has the same name but different parameters so in this case we'll only take in the array that we want to sort so this isn't the method that we're going to be calling recursively we'll only call it the first time when we want to initiate the quick sort all we have to do in this method is call this other quick sort method that does take in the low index and the high index so we'll just call that other quick sort method pass in the array and just as we did before we'll pass in zero as the low index and array dot length minus one as the high index so now we should again be able to rerun our program and have everything work exactly as it did before the only difference is now you can kind of call this quick sort method a bit more naturally where you just have to pass in the array that you want to sort now that we have everything fully optimized let's crank this up and see how fast quicksort actually is so instead of just sorting 10 numbers we're gonna have it sort a million numbers and instead of doing between zero and about a hundred we'll do between zero and about ten thousand okay it took a while for it to print out but it's already printing out the completed lists all right that finished really quickly i think most of the time it took there was actually just printing out the initial million numbers so what i'm actually going to do now that we know that the algorithm is working i'm going to take out the steps where it's printing the array out because i think that's probably taking the most time all right let's go ahead and run that again 1 million numbers okay it was done basically instantly in less than one second so let's crank this up to 10 million okay that did take a little bit longer about five seconds let's keep going and do a hundred million okay so at a hundred million we actually hit a stack overflow error so what's happening here is that just due to the sheer size of the array that we're sorting it ends up having to make tons and tons of recursive calls and each time it makes a recursive call it adds that method that it's calling onto something called the stack and there's only a certain amount of memory allocated to that stack in java and once you hit that limit you get a stack overflow error and there's just nothing you can do about it but still for sorting an array of 10 million elements in less than five seconds that is pretty awesome and that's why quicksort is generally regarded as the fastest sorting algorithm out there if you enjoyed this video or learned something please let me know by hitting the like button and be sure to subscribe so you don't miss each new java tutorial and after you make sure you completely understand quicksort don't stop there and keep your momentum going by watching one of these other job tutorials below thank you so much for watching i really appreciate you being here with me i'll see you next time

Channel: Coding with John

Views: 2,041

Keywords: java, codingwithjohn, coding with john, java beginner lesson, quicksort java, quicksort, quicksort algorithm, quicksort in java, quicksort algorithm in java, quick sort, quick sort java, quick sort algorithm, quicksort java code, quicksort java implementation, quicksort (algorithm), programming, quicksort hoare partition, quicksort partition

Id: h8eyY7dIiN4

Length: 24min 58sec (1498 seconds)

Published: Tue Nov 30 2021