изменение места оценки поворота приводит к сбою QuickSort

В 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;
    }
}

person Ahmed Waheed    schedule 06.12.2020    source источник


Ответы (1)


Поскольку значение в опорном индексе может быть изменено,

Рассмотрим этот очень простой обр [7, 10, 4, 2].

После первого вызова функции распределения значение left,

В рабочем коде значение будет 3, а массив будет [7, 2, 4, 10].

В нерабочем коде значение будет 2, а массив будет [7, 2, 4, 10]. Что явно неверно, поскольку левые значения индекса 2 должны быть меньше значения индекса 2. Что не следует, потому что 7 меньше 4 и находится слева.

person starboy_jb    schedule 07.12.2020