1 |
/* opdracht3.java - Opdracht 3 of OOP2, generic typing.
|
2 |
Copyright 2015 Maarten Vangeneugden |
3 |
|
4 |
Licensed under the Apache License, Version 2.0 (the "License"); |
5 |
you may not use this file except in compliance with the License. |
6 |
You may obtain a copy of the License at |
7 |
|
8 |
https://www.apache.org/licenses/LICENSE-2.0 |
9 |
|
10 |
Unless required by applicable law or agreed to in writing, software |
11 |
distributed under the License is distributed on an "AS IS" BASIS, |
12 |
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
13 |
See the License for the specific language governing permissions and |
14 |
limitations under the License.*/ |
15 |
|
16 |
import java.util.ArrayList; |
17 |
import java.util.Random; |
18 |
|
19 |
class ItHurtsWhenIP { |
20 |
/** Sorts a given ArrayList using quicksort. |
21 |
* @param array An ArrayList of items to be sorted. |
22 |
* @return The same ArrayList, but sorted. |
23 |
* @pre The given list is of type ArrayList. The items in the list implement the class Comparable. |
24 |
* @post The items in the list are sorted according to their implementation of Comparable. |
25 |
* @exception NullPointerException Thrown when the given array is not there. |
26 |
*/ |
27 |
|
28 |
public static <T extends Comparable> ArrayList<T> quickSort(ArrayList<T> array) { |
29 |
int index = new Random().nextInt(array.size()); // A random pivot between 0 and the size of the array. |
30 |
T pivot = array.get(index); // Taking the pivot element. |
31 |
|
32 |
if(array.size() == 0 || array.size() == 1) { // If the size of the array is too small to sort, return it as is. |
33 |
return array; |
34 |
} |
35 |
|
36 |
for (T value : array) { // Else, loop trough the elements, and sort them according to the pivot. |
37 |
if(value.compareTo(pivot) < 0) { // If the value is smaller than the pivot: |
38 |
if(array.indexOf(value) > index) { //If the value comes after the pivot, replace: |
39 |
array.set(array.indexOf(value), pivot); |
40 |
array.set(index, value); |
41 |
} |
42 |
} |
43 |
else { // The value is greater than the pivot: |
44 |
if(array.indexOf(value) < index) { // If the value comes before the pivot, replace: |
45 |
array.set(array.indexOf(value), pivot); |
46 |
array.set(index, value); |
47 |
} |
48 |
} |
49 |
} |
50 |
|
51 |
if(array.size() == 2 || array.size() == 3) // If the array is only 2 or 3 long, do not go recursive. instead, return it. |
52 |
return array; |
53 |
else { // If the array needs additional quicksorting, do so: |
54 |
ArrayList<T> lowerPart = quickSort((ArrayList)array.subList(0, index)); // Sorting the lower list. |
55 |
lowerPart.add(pivot); // Adding the pivot to the sorted lower list. |
56 |
ArrayList<T> upperPart = quickSort((ArrayList)array.subList(index, array.size())); // Sorting the upper list. |
57 |
lowerPart.addAll(upperPart); // Adding the upper sorted list to the lower sorted list. |
58 |
|
59 |
return lowerPart; // Returning it. |
60 |
} |
61 |
} |
62 |
} |
63 |
|