I've written my first implementation of quicksort in Java 8. Please let me know of any improvements that I can make (e.g. whether I'm creating any List
s unnecessarily).
Also, when I try to add elements directly to the leftArray
, I get a ConcurrentModificationException
. Doesn't subList()
create a new List
that's separate from the one that's passed into the sublist()
method? (the stuff related to the ConcurrentModificationException
is commented out. The code is working correctly.)
import java.util.ArrayList;
import java.util.List;
public class QuickSort {
public List<Integer> quickSort(List<Integer> arrayToSort){
if(arrayToSort.size() <= 1){
return arrayToSort;
}
int pivot = arrayToSort.get(0);
int i = 0, j = 1; // i is index of rightmost element with a value less than pivot's
while(j < arrayToSort.size()){
if(pivot > arrayToSort.get(j)){
swap(i + 1, j, arrayToSort);
i++;
}
j++;
}
swap(0, i, arrayToSort);
List<Integer> leftArray = quickSort(arrayToSort.subList(0, i));
List<Integer> rightArray = quickSort(arrayToSort.subList(i + 1, arrayToSort.size()));
if(false){
// Why do I get a ConcurrentModificationException here? Doesn't .subList() create a new list?
//leftArray.add(arrayToSort.get(i));
//leftArray.addAll(rightArray);
//return leftArray;
}
List<Integer> sorted = new ArrayList<>(leftArray.size() + rightArray.size() + 1);
sorted.addAll(leftArray);
sorted.add(arrayToSort.get(i));
sorted.addAll(rightArray);
return sorted;
}
private void swap(int a, int b, List<Integer> arrayToSort){
int temp = arrayToSort.get(a);
arrayToSort.set(a, arrayToSort.get(b));
arrayToSort.set(b, temp);
}
}
ConcurrentModificationException
suggests that it's not, which would make your question off-topic. \$\endgroup\$ConcurrentModificationException
is in the if-statement that has afalse
value, so it's not executed by the JVM. \$\endgroup\$arrayToSort
andrightArray
toleftArray
(all of which are sublists at a given recursion depth). Judging by what is said on the documentation, these structural modifications can be made as they're done via the returned sublist. I would expect to get aConcurrentModificationException
the original is structurally changed however. \$\endgroup\$