В QuickSort оценка сводной точки перед условиями сортировки заставляет алгоритм работать, а использование его индекса для получения значения в рамках условий приводит к его сбою, хотя опорный индекс вычисляется заранее и не должен меняться, в отличие от левого и правого.
Я не могу понять, в чем здесь проблема и как это изменение приводит к сбою алгоритма, поскольку кажется, что это не изменение логики, а скорее реорганизация кода с той же функциональностью.
Пожалуйста, проверьте приведенную ниже реализацию, объясненная проблема находится в методе partition
в комментируемой части:
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] numbers = { 120, 10, 3, 8, 15, 22, 6, 2, 17, 60, 4, 13};
System.out.println(Arrays.toString(numbers));
quickSort(numbers);
System.out.println(Arrays.toString(numbers));
}
private static void quickSort(int[] numbers) {
quickSort(numbers, 0, numbers.length - 1);
}
private static void quickSort(int[] numbers, int left, int right) {
if(left >= right) return;
int index = partition(numbers, left, right);
quickSort(numbers, left, index-1);
quickSort(numbers, index, right);
}
private static int partition(int[] arr, int left, int right) {
int pivotIndex = (left + right) / 2;
int pivot = arr[pivotIndex];
while(left <= right){
// This won't work
//while(arr[left] < arr[pivotIndex]) left++;
//while(arr[right]> arr[pivotIndex]) right--;
//This will work
while(arr[left] < pivot) left++;
while(arr[right]> pivot) right--;
if(left <= right) {
swap(arr, left, right);
left++;
right--;
}
}
//swap(numbers, pivot, left);
return left;
}
private static void swap(int[] arr, int left, int right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}