1 00:00:07,150 --> 00:00:12,940 I hope you enjoyed that assignment and that you were able to successfully come up with your own algorithm 2 00:00:12,940 --> 00:00:17,020 to solving the QuickSort implementation. 3 00:00:17,920 --> 00:00:23,650 We are now going to go over my solution to the QuickSort algorithm. 4 00:00:24,010 --> 00:00:30,130 So the first thing I want to do is set up my arrays that I'm going to test out. 5 00:00:31,090 --> 00:00:35,860 And again, I want to use the same values that we did in the previous lecture. 6 00:00:35,860 --> 00:00:41,050 So 8512, seven three and then four. 7 00:00:42,820 --> 00:00:51,700 And then I'm going to say length is equal to array length, and then we're going to call QuickSort and 8 00:00:51,700 --> 00:01:01,810 we're going to pass in the array zero, because that is the starting index and length minus one. 9 00:01:03,670 --> 00:01:05,950 And then lastly, I want to. 10 00:01:07,370 --> 00:01:11,060 Print out the sorted array. 11 00:01:16,030 --> 00:01:20,650 And now we have printed out the sorted array. 12 00:01:20,860 --> 00:01:25,540 So now we need to go up and implement an QuickSort. 13 00:01:26,830 --> 00:01:29,410 So we see F in quicksort. 14 00:01:31,850 --> 00:01:38,450 We're going to have our array, which will use a mutable array slice. 15 00:01:39,590 --> 00:01:44,270 We will have our starting index, which is going to be of type you size, and then we will have our 16 00:01:44,270 --> 00:01:47,300 ending index, which is also of type you size. 17 00:01:48,710 --> 00:01:52,130 And then if start is less than end. 18 00:01:53,810 --> 00:02:00,440 We will say let part four partition is equal to partition. 19 00:02:00,770 --> 00:02:04,070 The array start and end. 20 00:02:04,820 --> 00:02:15,950 And then we will call quicksort again on array, start partition minus one and quicksort on array, 21 00:02:19,040 --> 00:02:25,370 partition plus one, and then all the way to the end. 22 00:02:28,830 --> 00:02:37,290 And then here we are going to print out our our return, our I 32 vector. 23 00:02:38,310 --> 00:02:43,260 So now we will say array dot two vec. 24 00:02:44,860 --> 00:02:49,030 So now we need to implement in our partition. 25 00:02:52,060 --> 00:02:58,030 And so we know that we need a pass in mutable reference to our array slice. 26 00:03:00,250 --> 00:03:03,070 We need our start, which is going to be use size. 27 00:03:03,070 --> 00:03:06,820 And then we also need our end, which is also use size. 28 00:03:07,480 --> 00:03:14,710 And then we need to return a use size because that is where we know our partition. 29 00:03:15,810 --> 00:03:20,880 Our our new pivot was where our pivot was placed. 30 00:03:21,390 --> 00:03:25,320 So we will say let mute I is equal to start. 31 00:03:25,320 --> 00:03:32,520 So put the AI at the beginning and then we will put our pivot at the end and then we will say four j 32 00:03:32,520 --> 00:03:37,170 and start equals to end minus one. 33 00:03:37,170 --> 00:03:41,220 So instead of my J being at the end, I'm actually going to put it at the beginning. 34 00:03:41,760 --> 00:03:55,290 And then I will say if array of J is less than array of pivot, well now we want to go ahead and swap 35 00:03:55,290 --> 00:04:02,730 because now we know that our pivot, our j is less than our pivot. 36 00:04:02,730 --> 00:04:09,210 So now we want to swap in J and now we want to increment I by one. 37 00:04:12,180 --> 00:04:20,250 And then once all of that code is done, well, now we know that our. 38 00:04:21,730 --> 00:04:24,630 Pivot is in the correct spot, thanks to this check. 39 00:04:26,530 --> 00:04:27,040 Excuse me. 40 00:04:27,040 --> 00:04:35,890 We know that everything to the left of where pivot is going to be is going to be less than the pivot. 41 00:04:35,890 --> 00:04:39,280 And then everything above that index is going to be greater than the pivot. 42 00:04:39,610 --> 00:04:52,060 So now we're going to swap I in the pivot and return I because again, with this check right here, 43 00:04:53,230 --> 00:04:57,130 everything that is below I. 44 00:04:57,910 --> 00:05:02,890 Is less than the pivot, and everything above AI is greater than the pivot. 45 00:05:05,080 --> 00:05:10,780 So now we want to return that index because now we know that that is where Pivot was placed. 46 00:05:11,410 --> 00:05:14,650 So now we know that pivot is in the correct spot. 47 00:05:17,990 --> 00:05:19,790 And that is what we get returned here. 48 00:05:19,790 --> 00:05:25,820 So then we will run quicksort again on everything, one below pivot and one above. 49 00:05:26,650 --> 00:05:27,970 Her pivot was placed. 50 00:05:28,720 --> 00:05:39,070 So now if we run down here to Maine and we execute our code, we see that we have one, two, three, 51 00:05:39,070 --> 00:05:41,200 four, five, seven and eight. 52 00:05:41,320 --> 00:05:48,260 So my implementation and hopefully yours, which is very should be relatively similar to mine. 53 00:05:48,280 --> 00:05:53,320 Again, as I said, there are many ways that you can implement this in with different places of putting 54 00:05:53,320 --> 00:05:54,310 your pivots. 55 00:05:54,880 --> 00:06:01,990 In the previous lecture I show Jay being at the end, but to just give you an example of how unique 56 00:06:01,990 --> 00:06:08,650 you can get with this and my implementation, I put Jay in the beginning, so I and Jay were technically 57 00:06:08,650 --> 00:06:09,340 the same. 58 00:06:11,230 --> 00:06:17,620 So if you have any questions about my implementation or any questions about your implementation, please 59 00:06:17,620 --> 00:06:20,890 feel free to ask them in the Q&A section. 60 00:06:20,890 --> 00:06:29,020 And I hope you are comfortable with all the different algorithms that we have on over in this section 61 00:06:29,020 --> 00:06:31,840 on how to do sorting. 62 00:06:32,050 --> 00:06:37,600 And in the next section, we will begin taking a look at Linked List.