Would you like to inspect the original subtitles? These are the user uploaded subtitles that are being translated: 1 1 00:00:00,185 --> 00:00:05,185 (lively music) (keyboard clacking) 2 2 00:00:05,880 --> 00:00:09,400 We've just covered a bunch of sort algorithms 3 3 00:00:09,400 --> 00:00:12,530 and we've implemented those algorithms in Java, 4 4 00:00:12,530 --> 00:00:14,570 so suppose you have an array 5 5 00:00:14,570 --> 00:00:17,340 that you wanna sort in a Java application. 6 6 00:00:17,340 --> 00:00:19,810 Do you implement one of those algorithms 7 7 00:00:19,810 --> 00:00:21,070 to sort the array? 8 8 00:00:21,070 --> 00:00:23,610 Well, you can, especially if you can use one 9 9 00:00:23,610 --> 00:00:25,470 of the linear sort algorithms 10 10 00:00:25,470 --> 00:00:27,670 that makes assumptions about the data 11 11 00:00:27,670 --> 00:00:28,900 but if you can't do that, 12 12 00:00:28,900 --> 00:00:30,900 if you can't make any assumptions about the data, 13 13 00:00:30,900 --> 00:00:33,850 if counting sort and radix sort aren't suitable, 14 14 00:00:33,850 --> 00:00:36,300 do you go ahead and implement one of the algorithms? 15 15 00:00:36,300 --> 00:00:39,270 Well, you don't have to because hey, it's Java. 16 16 00:00:39,270 --> 00:00:41,760 We have the JDK at our disposal 17 17 00:00:41,760 --> 00:00:44,470 and the JDK contains an arrays class 18 18 00:00:44,470 --> 00:00:47,110 and that class has methods that sort arrays. 19 19 00:00:47,110 --> 00:00:49,890 So, let's take a look at the arrays Java doc. 20 20 00:00:49,890 --> 00:00:51,430 I've got it on the screen. 21 21 00:00:51,430 --> 00:00:52,460 So, right at the top, 22 22 00:00:52,460 --> 00:00:55,140 it says this class contains various methods 23 23 00:00:55,140 --> 00:00:58,940 for manipulating arrays such as sorting. 24 24 00:00:58,940 --> 00:01:01,893 So, let's scroll down and take a look at the sort methods. 25 25 00:01:07,150 --> 00:01:08,980 As you can see, there are a lot of methods here 26 26 00:01:08,980 --> 00:01:11,430 and boom, look at all these methods as well. 27 27 00:01:11,430 --> 00:01:14,380 So, these are all methods for primitive types 28 28 00:01:14,380 --> 00:01:16,749 but you'll se that you can also sort objects. 29 29 00:01:16,749 --> 00:01:20,210 If you wanna sort objects, of course you have to tell 30 30 00:01:20,210 --> 00:01:23,400 the runtime how to sort those objects 31 31 00:01:23,400 --> 00:01:27,010 and so, you'd implement the comparable interface. 32 32 00:01:27,010 --> 00:01:29,490 That's what the natural ordering would be, 33 33 00:01:29,490 --> 00:01:32,080 it would be based on the comparable. 34 34 00:01:32,080 --> 00:01:34,860 You'll also notice that there are sort methods 35 35 00:01:34,860 --> 00:01:37,130 that sort the entire array 36 36 00:01:37,130 --> 00:01:39,040 or just a part of the array, 37 37 00:01:39,040 --> 00:01:41,480 so you don't have to implement these sort methods 38 38 00:01:41,480 --> 00:01:43,540 when you wanna sort an array in Java. 39 39 00:01:43,540 --> 00:01:46,010 As I said, we've got a whole library at our disposal 40 40 00:01:46,010 --> 00:01:48,310 and the arrays class has sort methods, 41 41 00:01:48,310 --> 00:01:50,690 so let's go back to the IDE now 42 42 00:01:50,690 --> 00:01:53,610 and call the appropriate sort method 43 43 00:01:53,610 --> 00:01:56,483 on our usual example array. 44 44 00:02:01,525 --> 00:02:03,300 I've created a project, I've put the code 45 45 00:02:03,300 --> 00:02:06,380 into academy.learnprogramming.sortingarrays 46 46 00:02:06,380 --> 00:02:08,980 and I've created our usual array. 47 47 00:02:08,980 --> 00:02:11,360 We've gone back to our seven-element array 48 48 00:02:11,360 --> 00:02:13,420 that we were working with before we looked 49 49 00:02:13,420 --> 00:02:15,403 at counting sort and radix sort 50 50 00:02:15,403 --> 00:02:18,100 and I have the usual code for printing the array. 51 51 00:02:18,100 --> 00:02:19,510 So, we wanna sort this array, 52 52 00:02:19,510 --> 00:02:23,310 so let's just call Arrays.sort 53 53 00:02:23,310 --> 00:02:25,653 and we'll just pass it our intArray. 54 54 00:02:27,310 --> 00:02:28,343 And let's run. 55 55 00:02:32,200 --> 00:02:35,826 And there we go, minus 22, minus 15, 56 56 00:02:35,826 --> 00:02:39,810 one, seven, 20, 35 and 55. 57 57 00:02:39,810 --> 00:02:41,380 So, that's wonderful 58 58 00:02:41,380 --> 00:02:44,190 but now that we know about all these sort algorithms, 59 59 00:02:44,190 --> 00:02:47,350 we might ask well, what sort algorithm is it using? 60 60 00:02:47,350 --> 00:02:50,280 So, let's go to the source code for this. 61 61 00:02:50,280 --> 00:02:53,340 So, I'm going to right click 62 62 00:02:53,340 --> 00:02:56,110 and say Go To the Declaration 63 63 00:02:57,490 --> 00:03:00,510 and here we are and we'll see that it's using something 64 64 00:03:00,510 --> 00:03:02,773 called a DualPivotQuicksort 65 65 00:03:03,660 --> 00:03:05,474 and we can see from the comments 66 66 00:03:05,474 --> 00:03:09,520 that this is a modified form of Quicksort 67 67 00:03:09,520 --> 00:03:12,480 that doesn't degrade as much for larger datasets 68 68 00:03:12,480 --> 00:03:14,890 and it's typically faster than the Quicksort 69 69 00:03:14,890 --> 00:03:16,670 that uses one pivot, 70 70 00:03:16,670 --> 00:03:20,100 so this algorithm offers O n to the log n performance 71 71 00:03:20,100 --> 00:03:22,700 on many datasets that cause other quicksorts 72 72 00:03:22,700 --> 00:03:25,140 to degrade to quadratic performance. 73 73 00:03:25,140 --> 00:03:27,300 Remember that I mentioned 74 74 00:03:27,300 --> 00:03:31,090 that in the worst case, Quicksort is a quadratic algorithm 75 75 00:03:31,090 --> 00:03:34,610 but in the average case it's O n log n. 76 76 00:03:34,610 --> 00:03:37,720 It also says that a Dual-Pivot is typically faster 77 77 00:03:37,720 --> 00:03:40,610 than traditional one-pivot Quicksort algorithms, 78 78 00:03:40,610 --> 00:03:42,830 so if you were interested in looking 79 79 00:03:42,830 --> 00:03:45,610 at how this DualPivotQuicksort algorithm works, 80 80 00:03:45,610 --> 00:03:47,670 you could probably find an article out there 81 81 00:03:47,670 --> 00:03:51,190 on the web somewhere that will explain what it's doing 82 82 00:03:51,190 --> 00:03:54,010 but we can guess that it's using two pivots 83 83 00:03:54,010 --> 00:03:55,240 rather than one. 84 84 00:03:55,240 --> 00:03:58,960 The arrays class also has a bunch of parallel sort methods, 85 85 00:03:58,960 --> 00:04:03,410 so let's go back to our main class here 86 86 00:04:03,410 --> 00:04:05,460 and let's call parallelSort 87 87 00:04:05,460 --> 00:04:07,223 instead of just plain old sort. 88 88 00:04:08,311 --> 00:04:09,394 ParallelSort. 89 89 00:04:10,380 --> 00:04:11,530 It's giving me this error 90 90 00:04:11,530 --> 00:04:14,250 because even though I'm using Java 9, 91 91 00:04:14,250 --> 00:04:16,460 for some reason the language level it sets 92 92 00:04:16,460 --> 00:04:17,880 is sometimes lower than that, 93 93 00:04:17,880 --> 00:04:21,120 so this has only been available since Java 8 94 94 00:04:21,120 --> 00:04:22,490 and so, if you see that, 95 95 00:04:22,490 --> 00:04:23,750 a light bulb should come up, 96 96 00:04:23,750 --> 00:04:24,920 where'd that light bulb go? 97 97 00:04:24,920 --> 00:04:26,860 And then you can just say set my language level 98 98 00:04:26,860 --> 00:04:29,757 to Java 8, please and there we go. 99 99 00:04:29,757 --> 00:04:31,170 So, that's how we fix that error. 100 100 00:04:31,170 --> 00:04:32,143 So, let's run. 101 101 00:04:35,340 --> 00:04:37,860 And once again, we have our sorted values, 102 102 00:04:37,860 --> 00:04:40,410 minus 22 up to 55 103 103 00:04:40,410 --> 00:04:42,160 but what's this doing? 104 104 00:04:42,160 --> 00:04:44,830 Well, let's go to the source code, 105 105 00:04:44,830 --> 00:04:47,850 so we'll right click, Go To the Declaration 106 106 00:04:47,850 --> 00:04:49,550 and close this down for a minute 107 107 00:04:51,020 --> 00:04:53,110 and if we scroll up, 108 108 00:04:53,110 --> 00:04:55,870 we'll see it's a hybrid algorithm of sorts. 109 109 00:04:55,870 --> 00:04:58,160 It's a parallel sort merge 110 110 00:04:58,160 --> 00:05:01,200 that breaks the array into sub arrays 111 111 00:05:01,200 --> 00:05:03,250 that are assorted and then merged 112 112 00:05:03,250 --> 00:05:07,600 but when the sub array length reaches a minimum granularity, 113 113 00:05:07,600 --> 00:05:10,270 the sub array is sorted using 114 114 00:05:10,270 --> 00:05:12,510 the appropriate arrays.sort method 115 115 00:05:12,510 --> 00:05:14,340 which is know is Quicksort. 116 116 00:05:14,340 --> 00:05:16,200 So, it's doing a merge sort 117 117 00:05:16,200 --> 00:05:20,620 but when it's dealing with smaller partitions, 118 118 00:05:20,620 --> 00:05:22,950 it's sorting them using Quicksort 119 119 00:05:22,950 --> 00:05:24,920 rather than just traversing the arrays 120 120 00:05:24,920 --> 00:05:27,430 and copying the smaller element 121 121 00:05:27,430 --> 00:05:29,060 into a temporary array. 122 122 00:05:29,060 --> 00:05:30,468 It's also using threads 123 123 00:05:30,468 --> 00:05:33,830 and that's why it's called parallelSort. 124 124 00:05:33,830 --> 00:05:38,000 So, this sort might be faster for larger datasets. 125 125 00:05:38,000 --> 00:05:39,685 So, if you have a larger dataset, 126 126 00:05:39,685 --> 00:05:43,050 using parallelSort might result 127 127 00:05:43,050 --> 00:05:44,030 in a faster sort. 128 128 00:05:44,030 --> 00:05:46,040 You'd have to run some benchmarks to decide 129 129 00:05:46,040 --> 00:05:49,790 whether to just call sort or parallelSort. 130 130 00:05:49,790 --> 00:05:52,290 And that's all I wanted to do in this video. 131 131 00:05:52,290 --> 00:05:54,780 The point is that it's good to understand 132 132 00:05:54,780 --> 00:05:56,560 the different types of sort algorithms 133 133 00:05:56,560 --> 00:05:59,520 but you don't necessarily have to implement them yourself 134 134 00:05:59,520 --> 00:06:00,650 and you'll see the same thing 135 135 00:06:00,650 --> 00:06:03,950 when we look at some of the upcoming data structures. 136 136 00:06:03,950 --> 00:06:07,750 Java has a lot of support for commonly used data structures. 137 137 00:06:07,750 --> 00:06:09,270 So, you rarely have to implement 138 138 00:06:09,270 --> 00:06:10,850 the data structure yourself. 139 139 00:06:10,850 --> 00:06:13,090 There is often a class in the JDK 140 140 00:06:13,090 --> 00:06:15,630 that has already done it for you or if there isn't, 141 141 00:06:15,630 --> 00:06:18,210 you can usually find a third-party library 142 142 00:06:18,210 --> 00:06:21,090 that has an implementation that you can use. 143 143 00:06:21,090 --> 00:06:23,330 So, the bottom line here 144 144 00:06:23,330 --> 00:06:25,350 is that you don't have to write the sort code 145 145 00:06:25,350 --> 00:06:27,050 when you wanna sort an array. 146 146 00:06:27,050 --> 00:06:30,120 You have methods available to you in the JDK 147 147 00:06:30,120 --> 00:06:33,060 and so, unless you wanna use counting or radix sort, 148 148 00:06:33,060 --> 00:06:34,300 or unless for some reason 149 149 00:06:34,300 --> 00:06:37,000 you don't wanna use a DualPivotQuicksort 150 150 00:06:37,000 --> 00:06:40,620 or you don't wanna use a merge sort-Quicksort hybrid, 151 151 00:06:40,620 --> 00:06:42,140 you'll typically just go ahead 152 152 00:06:42,140 --> 00:06:44,830 and use one of the sort methods in the JDK 153 153 00:06:44,830 --> 00:06:47,140 and if you want to sort an array of objects, 154 154 00:06:47,140 --> 00:06:48,850 remember that you'll have to implement 155 155 00:06:48,850 --> 00:06:50,510 the comparable interface 156 156 00:06:50,510 --> 00:06:52,450 so that the method knows 157 157 00:06:52,450 --> 00:06:55,140 how it's supposed to order your objects 158 158 00:06:55,140 --> 00:06:56,797 when it's doing a sort. 159 159 00:06:56,797 --> 00:06:58,613 I'll see you in the next video. 13506