Моя реализация быстрой сортировки использует слишком много сравнений, но не может определить, почему - PullRequest
Новая
       6

Моя реализация быстрой сортировки использует слишком много сравнений, но не может определить, почему

0 голосов
/ 27 октября 2018

Я пытаюсь реализовать быструю сортировку в Java, и я изо всех сил пытаюсь реализовать это эффективно. Я считаю, что проблема в моих рекурсивных вызовах, но я не могу определить, как это исправить. Я использую сравнения, чтобы увидеть, сколько раз было сделано сравнение в надежде определить, где проблема. Единственное, о чем я могу думать, - это требовать условного выражения для моих рекурсивных операторов, потому что количество необходимых сравнений остается тем же, независимо от того, был ли введенный массив уже отсортирован или, по-видимому, рандомизирован. 

public int quickSort(int[] arr, int left, int right) {

    //left is lowest index
    //right is highest index

    int compares = 0;

    //calls insertion sort once subsets get smaller than 7 elements
    if (right - left < 6) {
      compares += insertSort(arr, left, right);
      return compares;
    }

        //calculate random pivot
        int pivotIndex = randomInt(left, right);
        int pivotValue = arr[pivotIndex];


        //moves pivot value to rightmost index
        int temp;
        temp = arr[pivotIndex];
        arr[pivotIndex] = arr[right];
        arr[right] = temp;

        int pivotFinal = left;


        //determines how many values are lower than the pivot, swapping 
        //smaller values with larger values along the way
        for (int i = left; i < right; i++) {
            compares++;
            if (arr[i] <= pivotValue) {
                temp = arr[i];
                arr[i] = arr[pivotFinal];
                arr[pivotFinal] = temp;
                pivotFinal++;
            }
        }

        //moves pivot to final position so that quicksort is complete
        temp = arr[pivotFinal];
        arr[pivotFinal] = arr[right];
        arr[right] = temp;

        compares += quickSort(arr, left, pivotIndex - 1);
        compares += quickSort(arr, pivotIndex + 1, right);
        return compares;
}



public void main() {
    QuickSort qs = new QuickSort();

    int n = 60;
    int[] array = qs.GenerateRandomSequence(n);

    int compares = qs.quickSort(array);
}

При n, равном 60, для одной из последовательностей требуется более 4 миллионов сравнений, что намного, намного хуже, чем фактическое время выполнения в худшем случае.

1 Ответ

0 голосов
/ 27 октября 2018

У вас есть пара ошибок с вашими индексами. Ваша рекурсия должна использовать вашу конечную опорную позицию. 

compares += quickSort(arr, left, pivotFinal - 1);
compares += quickSort(arr, pivotFinal + 1, right);

И вы правильно относитесь к своему «правильному» индексу в разных местах. Вероятно, проще всего просто использовать «<=» в вашем цикле </p> 

for (int i = left; i < right; i++) // assumes right is after the last index

arr[pivotIndex] = arr[right]; // assumes right IS the last index
...