I hope you enjoyed that assignment and that you were able to successfully come up with your own algorithm
to solving the QuickSort implementation.
We are now going to go over my solution to the QuickSort algorithm.
So the first thing I want to do is set up my arrays that I'm going to test out.
And again, I want to use the same values that we did in the previous lecture.
So 8512, seven three and then four.
And then I'm going to say length is equal to array length, and then we're going to call QuickSort and
we're going to pass in the array zero, because that is the starting index and length minus one.
And then lastly, I want to.
Print out the sorted array.
And now we have printed out the sorted array.
So now we need to go up and implement an QuickSort.
So we see F in quicksort.
We're going to have our array, which will use a mutable array slice.
We will have our starting index, which is going to be of type you size, and then we will have our
ending index, which is also of type you size.
And then if start is less than end.
We will say let part four partition is equal to partition.
The array start and end.
And then we will call quicksort again on array, start partition minus one and quicksort on array,
partition plus one, and then all the way to the end.
And then here we are going to print out our our return, our I 32 vector.
So now we will say array dot two vec.
So now we need to implement in our partition.
And so we know that we need a pass in mutable reference to our array slice.
We need our start, which is going to be use size.
And then we also need our end, which is also use size.
And then we need to return a use size because that is where we know our partition.
Our our new pivot was where our pivot was placed.
So we will say let mute I is equal to start.
So put the AI at the beginning and then we will put our pivot at the end and then we will say four j
and start equals to end minus one.
So instead of my J being at the end, I'm actually going to put it at the beginning.
And then I will say if array of J is less than array of pivot, well now we want to go ahead and swap
because now we know that our pivot, our j is less than our pivot.
So now we want to swap in J and now we want to increment I by one.
And then once all of that code is done, well, now we know that our.
Pivot is in the correct spot, thanks to this check.
Excuse me.
We know that everything to the left of where pivot is going to be is going to be less than the pivot.
And then everything above that index is going to be greater than the pivot.
So now we're going to swap I in the pivot and return I because again, with this check right here,
everything that is below I.
Is less than the pivot, and everything above AI is greater than the pivot.
So now we want to return that index because now we know that that is where Pivot was placed.
So now we know that pivot is in the correct spot.
And that is what we get returned here.
So then we will run quicksort again on everything, one below pivot and one above.
Her pivot was placed.
So now if we run down here to Maine and we execute our code, we see that we have one, two, three,
four, five, seven and eight.
So my implementation and hopefully yours, which is very should be relatively similar to mine.
Again, as I said, there are many ways that you can implement this in with different places of putting
your pivots.
In the previous lecture I show Jay being at the end, but to just give you an example of how unique
you can get with this and my implementation, I put Jay in the beginning, so I and Jay were technically
the same.
So if you have any questions about my implementation or any questions about your implementation, please
feel free to ask them in the Q&A section.
And I hope you are comfortable with all the different algorithms that we have on over in this section
on how to do sorting.
And in the next section, we will begin taking a look at Linked List.