Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Learn Quick Sort in 13 minutes ⚡
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 68 Zeilen
- hey uh it's you bro hope you're doing well and in this video i'm going to explain the quicksort algorithm in computer science yep so uh sit back
- relax and enjoy the show all right quick sort here's how quick sort is going to work we need an array
- or some other type of collection i have a simple unordered array what we do is that we'll pass our array as an argument into a quick sort function after passing
- our array as an argument to the quick sort function we need to pick a pivot there's different variations of quick sort we can either pick a pivot at the
- beginning the middle or at the end but with most standard quick sort algorithms we will set the pivot to be at the end of our array what we're trying to
- accomplish is that we need to find the final resting place of our pivot where is this value going to be and taking a look at this
- that would be right about here but we don't know that yet so to find the final resting place of this value our pivot here's what we can do we will declare
- and use two indices j and i j will begin at the start of our array i will be one less than the beginning of our array and that's going to be important later and
- we'll need the help of a temporary variable so we can swap some values all we're doing is checking to see if the value at j is less than our pivot if
- it's greater than our pivot or equal to our pivot we ignore it eight is greater than five we ignore this value and then increment j by one
- so during that last iteration i did not come into play yet but it will this round again we check to see if this value is less than our pivot which it is
- what we do now is increment i then what comes next is that we swap these two values i and j and we'll need the help of a temporary variable so take
- the value at i assign it to temp take the value at j assign it to i
- take the value within temp assign it to j then we can move on to the next iteration increments j
- we check to see if the value at j is less than our pivot which it is if that is the case we increment i swap these two values
- we'll repeat this process until j reaches our pivot then we can move on to the next step
- this here's the next step after our index j reaches our pivot we now know where the final resting place of our pivot is
- gonna be it's i incremented by one so we will increment i then swap the value at index of i with the value at our pivot
- our pivot is now within the correct place an easy way to tell is that all elements to the left of our pivot should be at less than our pivot but they're
- not necessarily going to be in order and that's fine they'll be organized later all elements to the right of our pivot should be greater than or equal to our
- pivot and like i said before they probably will not be in order the important thing is that elements to the left should be less than our pivot
- elements to the right should be greater than that's how we know the pivot's in the correct place now the next step we're going to create two sections two
- partitions the first partition will be all the elements from the beginning of our array up until our pivot but not including the
- pivot and our second partition will be all the elements after our pivot until the end of our array quicksort is a recursive algorithm we need to pass
- these partitions as arguments into the quick sort function remember that the quick sort algorithm is a recursive divide and conquer algorithm but unlike
- with merge sort with merge sort we create new subarrays with quick sort we will be sorting these arrays in place but we need to keep track of the
- beginning and ending indices of these partitions and then it's just a matter of repeating the same steps over again but we're
- going to instead use these partitions sections of our array i'll give you a quick demonstration of what the quicksort algorithm is going to look
- like to completion [Music] [Music]
- and that ladies and gentlemen was your visual representation of the quicksort algorithm let's code our own quick sort algorithm just to solidify our
- understanding of this topic all right people let's create a quick sort function you'll need an array to work with place some random numbers within
- that array and then some way to iterate and display the elements of your array i'm just using a symbol for each loop so after running this of course our array
- is not yet sorted so before we display the elements of our array let's invoke a quick sort function which we still need to declare defined there will be three
- arguments our array and the beginning and ending indices of our array so that would be zero for the beginning then to find the ending you
- can just say array dot length minus one let's declare this function private static void quick sort and let's rename some of these
- parameters we have our array of integers named array and this will be the starting index and this parameter will be the ending index
- so we have indices start and end now the base case this will use recursion will be if
- end is less than or equal to start then we will return and this is our base case eventually we
- won't be able to divide our array any further so that's when we stop and return with our quick sort function we'll need the assistance of a helper
- function that we will name partition let's copy our function declaration paste it and make a few changes so this will return an int the location
- of our pivot and the function name will be partition and the parameters are the same at the end of our partition helper function
- we'll return i i will be the location of our pivot but we'll get to that later okay so within our quick sort function we'll need to find the location of where
- to pivot int pivot and the partition function will be in charge of that partition is going to sort our array and find the pivot so all elements to the
- left will be smaller than our pivot all elements to the right will be larger so pass in our array we're sorting our array in place there's
- no need to create any sub-arrays we'll just pass in our original array as well as the start and end after we figure out where our pivot's going to be
- we can pass in each partition recursively back into the quick sort function so again we will invoke quick sort
- pass in our array the start of our left partition and the ending of our left partition and that is where pivot is minus one we do
- not want to include our pivot and then we will need to use quick sort on the right partition change start to pivot plus one
- because the pivot is already in place and then the end of our array in this variation of the quick sort function we will say that pivot is at the end it
- will always be at the end to begin with int pivot equals array at index of n we'll need two indices i and j we'll create index i
- equals start minus one and then we will iterate through our array and this is where we will declare int j our second index
- int j equals start and we will continue this for loop as long as j is less than or equal to the end of our array minus one then
- increment j by one what we're going to check is if array at index of j is less than our pivot
- if one of these elements is less than our pivot we want it on the left hand side of our pivot any numbers larger than our pivot should
- be on the right hand side so we will increment i by 1 and do a basic variable swap and we'll need the help of a temporary variable int temp
- equals array at index of i array at index of i equals array at index of j lastly array at index of j equals temp
- this is just a basic variable swap once all elements that are less than our pivot are on the left hand side and all elements that are larger than our pivot
- are on the right hand side what we will do now is increment i by one and then insert our pivot into its final resting place with another basic
- variable swap so let's copy this code then paste it and make a few changes intent equals array at index of i that's the same
- array at index of i equals array at index of end array at index event equals temp and that's it and then make sure you return
- i at the end that is the location of our pivot then after running this our array is now sorted via the quick
- sort algorithm in conclusion the quick sort algorithm moves smaller elements to the left of a pivot we recursively divide our array into two partitions and
- pass those partitions as arguments recursively into the quick sort function the runtime complexity of the quicksort algorithm actually varies in its best
- and average cases it runs in big o of n log n however in its worst case it can run in big o of n squared this is rare and it occurs if the array is already
- sorted or close to being sorted but most of the time it will run in big o of n log n and the space complexity of the quicksort algorithm is big o of log n
- this is due to recursion it uses more space than bubble sort selection sort and insertion sort even though it sorts in place that's because the quick sort
- algorithm uses recursion we're adding frames to the call stack which takes memory so yeah that is the quick sort algorithm if you found this video
- helpful please be sure to smash that like button leave a random comment down below and subscribe if you'd like to become a fellow bro