How can I keep track of the number of pivots in Quick Sort?

I tried different approaches.

  1. Changing the return type of quickSort to int and adding the parameter “int numPivots” to the method. Then I added numPivots++; after the call of the partition method and returned the numPivots at the end. When passing 0 as an argument the returned value in my main method was 1. This makes sense since it is the first value that will be returned after all the recursions. I just cant get my head around what I have to change to make this work.

  2. Creating an “ArrayList pivots” in the main method and passing it as an Argument to quickSort and from there to partition. I filled it with all the pivots but still didnt get the right result. This was a weird approach, but I got devestaded.

  3. Creating an instance variable and methods to increase it / get its value. This didnt work either and felt kind of stupid.

Here is the code

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

Also: I thought quickSort would work with 2 Pointers, a left pointer and a right pointer. After failing to write my own quickSort algorithm I simply took this one from a tutorial. This confuses me because it doesn’t use a rightPointer. I took pen and paper to follow the steps and I think I got how it works but is it the same algorithm as explained here?

I knoiw these are a lot of questions. Thank you for your time!

Answer

Solved it like this:

class CountObject{
int count;

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

public int getCount() {
    return count;
}

}

Leave a Reply

Your email address will not be published. Required fields are marked *