Java:
public class QuickSort {
public static void sort(int[] numbers) {
new QuickSort().quickSort(numbers, 0, numbers.length - 1);
}
protected void quickSort(int[] numbers, int leftIndex, int rightIndex) {
if (leftIndex < rightIndex) {
int pivotIndex = divide(numbers, leftIndex, rightIndex);
quickSort(numbers, leftIndex, pivotIndex - 1);
quickSort(numbers, pivotIndex + 1, rightIndex);
}
}
/**
* liefert den Index des Pivot-Elementes und ordnet das Array innerhalb
* der angegebenen Indizes so um, dass alle Zahlen links vom Index
* kleiner oder gleich und alle Zahlen rechts vom Index groesser
* oder gleich dem Pivot-Element sind
*/
protected int divide(int[] numbers, int leftIndex, int rightIndex) {
int pivotIndex = choosePivotIndex(numbers, leftIndex, rightIndex);
int pivotValue = numbers[pivotIndex];
// das Pivot-Element kommt nach ganz rechts im Array
swap(numbers, pivotIndex, rightIndex);
int left = leftIndex - 1;
int right = rightIndex;
do {
left++;
while (left <= rightIndex && numbers[left] <= pivotValue)
left++;
right--;
while (right >= leftIndex && numbers[right] >= pivotValue)
right--;
if (left < right) {
swap(numbers, left, right);
}
} while (left < right);
// platziere das Pivot-Element an seine korrekte Position
if (left < rightIndex) {
swap(numbers, left, rightIndex);
return left;
} else {
return rightIndex;
}
}
protected int choosePivotIndex(int[] numbers, int leftIndex, int rightIndex) {
return (leftIndex + rightIndex) / 2;
}
protected void swap(int[] numbers, int index1, int index2) {
if (index1 != index2) {
int tmp = numbers[index1];
numbers[index1] = numbers[index2];
numbers[index2] = tmp;
}
}
}
public class QuickSortTest {
public static void main(String[] args) {
int[] numbers = {2, 3, 9, 33, -2, 4, 55, 66, -234};
print(numbers);
QuickSort.sort(numbers);
print(numbers);
int[] numbers2 = {2, 3, 9, 33, -2, 4, 55, 66, -234};
print(numbers2);
QuickSortThreaded.sort(numbers2);
print(numbers2);
}
private static void print(int[] numbers) {
for (int number : numbers) {
System.out.print(number + " ");
}
System.out.println();
}
}
public class QuickSortThreaded extends QuickSort{
public static void sort(int[] numbers) {
QuickSort.sort(numbers);
}
protected void quickSort(int[] numbers, int leftIndex, int rightIndex) {
super.quickSort(numbers, leftIndex, rightIndex);
}
}In der Hilfsmethode quickSort werden nacheinander der Bereich links vom Pivot-Element und der Bereich rechts vom PivotElement durch rekursiven Aufruf der Methode sortiert. Die beide Aktionen sind unabhängig voneinander. Wie kann ich sie durch die Verwendung von Threads parallelisieren?
