Original subtitles

1 1

(lively music) (keyboard clacking) 2

2

We've just covered a bunch of sort algorithms 3

3

and we've implemented those algorithms in Java, 4

4

so suppose you have an array 5

5

that you wanna sort in a Java application. 6

6

Do you implement one of those algorithms 7

7

to sort the array? 8

8

Well, you can, especially if you can use one 9

9

of the linear sort algorithms 10

10

that makes assumptions about the data 11

11

but if you can't do that, 12

12

if you can't make any assumptions about the data, 13

13

if counting sort and radix sort aren't suitable, 14

14

do you go ahead and implement one of the algorithms? 15

15

Well, you don't have to because hey, it's Java. 16

16

We have the JDK at our disposal 17

17

and the JDK contains an arrays class 18

18

and that class has methods that sort arrays. 19

19

So, let's take a look at the arrays Java doc. 20

20

I've got it on the screen. 21

21

So, right at the top, 22

22

it says this class contains various methods 23

23

for manipulating arrays such as sorting. 24

24

So, let's scroll down and take a look at the sort methods. 25

25

As you can see, there are a lot of methods here 26

26

and boom, look at all these methods as well. 27

27

So, these are all methods for primitive types 28

28

but you'll se that you can also sort objects. 29

29

If you wanna sort objects, of course you have to tell 30

30

the runtime how to sort those objects 31

31

and so, you'd implement the comparable interface. 32

32

That's what the natural ordering would be, 33

33

it would be based on the comparable. 34

34

You'll also notice that there are sort methods 35

35

that sort the entire array 36

36

or just a part of the array, 37

37

so you don't have to implement these sort methods 38

38

when you wanna sort an array in Java. 39

39

As I said, we've got a whole library at our disposal 40

40

and the arrays class has sort methods, 41

41

so let's go back to the IDE now 42

42

and call the appropriate sort method 43

43

on our usual example array. 44

44

I've created a project, I've put the code 45

45

into academy.learnprogramming.sortingarrays 46

46

and I've created our usual array. 47

47

We've gone back to our seven-element array 48

48

that we were working with before we looked 49

49

at counting sort and radix sort 50

50

and I have the usual code for printing the array. 51

51

So, we wanna sort this array, 52

52

so let's just call Arrays.sort 53

53

and we'll just pass it our intArray. 54

54

And let's run. 55

55

And there we go, minus 22, minus 15, 56

56

one, seven, 20, 35 and 55. 57

57

So, that's wonderful 58

58

but now that we know about all these sort algorithms, 59

59

we might ask well, what sort algorithm is it using? 60

60

So, let's go to the source code for this. 61

61

So, I'm going to right click 62

62

and say Go To the Declaration 63

63

and here we are and we'll see that it's using something 64

64

called a DualPivotQuicksort 65

65

and we can see from the comments 66

66

that this is a modified form of Quicksort 67

67

that doesn't degrade as much for larger datasets 68

68

and it's typically faster than the Quicksort 69

69

that uses one pivot, 70

70

so this algorithm offers O n to the log n performance 71

71

on many datasets that cause other quicksorts 72

72

to degrade to quadratic performance. 73

73

Remember that I mentioned 74

74

that in the worst case, Quicksort is a quadratic algorithm 75

75

but in the average case it's O n log n. 76

76

It also says that a Dual-Pivot is typically faster 77

77

than traditional one-pivot Quicksort algorithms, 78

78

so if you were interested in looking 79

79

at how this DualPivotQuicksort algorithm works, 80

80

you could probably find an article out there 81

81

on the web somewhere that will explain what it's doing 82

82

but we can guess that it's using two pivots 83

83

rather than one. 84

84

The arrays class also has a bunch of parallel sort methods, 85

85

so let's go back to our main class here 86

86

and let's call parallelSort 87

87

instead of just plain old sort. 88

88

ParallelSort. 89

89

It's giving me this error 90

90

because even though I'm using Java 9, 91

91

for some reason the language level it sets 92

92

is sometimes lower than that, 93

93

so this has only been available since Java 8 94

94

and so, if you see that, 95

95

a light bulb should come up, 96

96

where'd that light bulb go? 97

97

And then you can just say set my language level 98

98

to Java 8, please and there we go. 99

99

So, that's how we fix that error. 100

100

So, let's run. 101

101

And once again, we have our sorted values, 102

102

minus 22 up to 55 103

103

but what's this doing? 104

104

Well, let's go to the source code, 105

105

so we'll right click, Go To the Declaration 106

106

and close this down for a minute 107

107

and if we scroll up, 108

108

we'll see it's a hybrid algorithm of sorts. 109

109

It's a parallel sort merge 110

110

that breaks the array into sub arrays 111

111

that are assorted and then merged 112

112

but when the sub array length reaches a minimum granularity, 113

113

the sub array is sorted using 114

114

the appropriate arrays.sort method 115

115

which is know is Quicksort. 116

116

So, it's doing a merge sort 117

117

but when it's dealing with smaller partitions, 118

118

it's sorting them using Quicksort 119

119

rather than just traversing the arrays 120

120

and copying the smaller element 121

121

into a temporary array. 122

122

It's also using threads 123

123

and that's why it's called parallelSort. 124

124

So, this sort might be faster for larger datasets. 125

125

So, if you have a larger dataset, 126

126

using parallelSort might result 127

127

in a faster sort. 128

128

You'd have to run some benchmarks to decide 129

129

whether to just call sort or parallelSort. 130

130

And that's all I wanted to do in this video. 131

131

The point is that it's good to understand 132

132

the different types of sort algorithms 133

133

but you don't necessarily have to implement them yourself 134

134

and you'll see the same thing 135

135

when we look at some of the upcoming data structures. 136

136

Java has a lot of support for commonly used data structures. 137

137

So, you rarely have to implement 138

138

the data structure yourself. 139

139

There is often a class in the JDK 140

140

that has already done it for you or if there isn't, 141

141

you can usually find a third-party library 142

142

that has an implementation that you can use. 143

143

So, the bottom line here 144

144

is that you don't have to write the sort code 145

145

when you wanna sort an array. 146

146

You have methods available to you in the JDK 147

147

and so, unless you wanna use counting or radix sort, 148

148

or unless for some reason 149

149

you don't wanna use a DualPivotQuicksort 150

150

or you don't wanna use a merge sort-Quicksort hybrid, 151

151

you'll typically just go ahead 152

152

and use one of the sort methods in the JDK 153

153

and if you want to sort an array of objects, 154

154

remember that you'll have to implement 155

155

the comparable interface 156

156

so that the method knows 157

157

how it's supposed to order your objects 158

158

when it's doing a sort. 159

159

I'll see you in the next video.