Divide and Conquer 1/Java Beispiel 1

Wiki-Quelltext dieser Seite.

<language>Java</language>
Quicksort in Java ([http://www.vogella.de/articles/JavaAlgorithmsQuicksort/article.html#quicksort_implementation Quelle]):

<code id="4bbdcbc3119a0">
int[] numbers;
int number;

void quicksort (int[] values) {
	numbers = values;
	number = values.length;
	quicksorting(0, number - 1);
        for(int i=0; i < numbers.length; i++) System.out.print(numbers[i]+ (i < numbers.length-1 ? "," : ""));
}

void quicksorting (int low, int high) {
	int i = low, j = high;
	// Get the pivot element from the middle of the list
	int pivot = numbers[(low + high) / 2];

	// Divide into two lists
	while (i <= j) {
		// If the current value from the left list is smaller then the pivot
		// element then get the next element from the left list
		while (numbers[i] < pivot) {
			i++;
		}
		// If the current value from the right list is larger then the pivot
		// element then get the next element from the right list
		while (numbers[j] > pivot) {
			j--;
		}

		// If we have found a values in the left list which is larger then
		// the pivot element and if we have found a value in the right list
		// which is smaller then the pivot element then we exchange the
		// values.
		// As we are done we can increase i and j
		if (i <= j) {
			exchange(i, j);
			i++;
			j--;
		}
	}
	// Recursion
	if (low < j)
		quicksorting(low, j);
	if (i < high)
		quicksorting(i, high);
}

void exchange(int i, int j) {
	int temp = numbers[i];
	numbers[i] = numbers[j];
	numbers[j] = temp;
}

</code>
<run id="4bbdcbc3121f3">
quicksort(new int[] {1,42,5,23,6,34}); 
</run>