Как я могу отслеживать количество точек в быстрой сортировке? - PullRequest
Новая
       13

Как я могу отслеживать количество точек в быстрой сортировке?

0 голосов
/ 16 марта 2019

Я пробовал разные подходы.

  1. Изменение типа возвращаемого значения quickSort на int и добавление параметра "int numPivots" в метод. Затем я добавил numPivots ++; после вызова метода разбиения и возвращает numPivots в конце. При передаче 0 в качестве аргумента возвращаемое значение в моем методе main было 1. Это имеет смысл, поскольку это первое значение, которое будет возвращено после всех рекурсий. Я просто не могу понять, что мне нужно изменить, чтобы сделать эту работу.

  2. Создание "ArrayList pivots" в методе main и передача его в качестве аргумента для быстрой сортировки и оттуда к разделу. Я заполнил его всеми опорными точками, но все еще не получил правильный результат. Это был странный подход, но я потерял самообладание.

  3. Создание переменной экземпляра и методов для ее увеличения / получения ее значения. Это тоже не сработало и казалось глупым.

Вот код 

public static void quickSort(int[] arr, int start, int end){

    int partition = partition(arr, start, end);


    if(partition-1>start) {
        quickSort(arr, start, partition - 1);
    }
    if(partition+1<end) {
        quickSort(arr, partition + 1, end);
    }

}

public static int partition(int[] arr, int start, int end){
    int pivot = arr[end];


    //checks if left pointer < pivot
    for(int i=start; i<end; i++){
        if(arr[i]<pivot){
            int temp= arr[start];
            arr[start]=arr[i];
            arr[i]=temp;
            start++;
        }
    }

    //switches pivots
    int temp = arr[start];
    arr[start] = pivot;
    arr[end] = temp;

    return start;
}

Также: я думал, что quickSort будет работать с 2 указателями, указателем влево и указателем вправо. После неудачной попытки написать собственный алгоритм быстрой сортировки, я просто взял его из учебника. Это смущает меня, потому что он не использует rightPointer. Я взял ручку и бумагу, чтобы выполнить шаги, и я думаю, что понял, как это работает, но это тот же алгоритм, как объяснено здесь ?

Я знаю, это много вопросов. Спасибо за ваше время!

1 Ответ

0 голосов
/ 16 марта 2019

Решил вот так: 

class CountObject{
int count;

public CountObject(int count){
    this.count=count;
}
public void increaseCount (){
    this.count++;
}

public int getCount() {
    return count;
}

}

...