My own version of quicksort only seems to work for small arrays

Question

I am trying to implement my own version on quicksort. I was very happy when I saw that it sorted for small arrays, but as soon as I tried on larger array inputs such as 1k, 50k, 100k, 1000k. I saw that the running time was higher than expected also when I tried with array input 1000k it caused stackoverflow.

I would love to get feedback on my code, what I should change in the code to make the algorithm work and comment on why it is currently not working with my code.

I have added run_partition = false, once I find out that the left pointer and right pointer points at same index. It made it possible to sort for an input array of 100k.

// O(nlogn) worst case running time
// O(n) space complexity
import java.util.*;
public class Quicksort {


    public int partition_array(int [] array, int start, int end) {
         // The pivot pointer starts at the first element initially, array index = 0
         // The left pointer points to first element initially

        int left_pointer = start;

        int right_pointer = end;
        int pivot_pointer =  left_pointer;
        boolean run_partition = true; 
        // keep running partition until we return a pivot index, once we return a partition index we can do quicksort on the values left to partition and values to right of partition
     while(run_partition) {


            if( pivot_pointer == left_pointer) {
                // If pivot points towards the left pointer then we have to make sure that all values to the right of pivot, make sure ew can sort duplicate keys too
                while(array[pivot_pointer] <= (array[right_pointer]) && right_pointer != pivot_pointer  ) {
                    right_pointer--;
                 }
                if(left_pointer == right_pointer) {
                // System.out.println(left_pointer + ": is same as  " + right_pointer);
                    run_partition=false;
                   return pivot_pointer;
                }
                // if pivot points towards left pointer and we find out that there exists a right value that is smaller, we have to swap them.
                else if(array[pivot_pointer] > (array[right_pointer]) )  {
                    // System.out.println("Right: " + array[right_pointer] + " is less than pivot_left:  " + array[pivot_pointer]);
                    swap(array, pivot_pointer, right_pointer);
                    pivot_pointer = right_pointer;

                }
                else if( right_pointer < left_pointer){
                break;
                }
                else {
                    right_pointer--;
                }
            }

            if(pivot_pointer == right_pointer) {
                // if pivot_pointer points towards right pointer then we have to make sure that all values to the left is smaller
                while(array[pivot_pointer] > ( array[left_pointer])  && left_pointer != pivot_pointer) {
                    // increment left_pointer until this while condition is no longer true
                    left_pointer++;
                }

                if(pivot_pointer == left_pointer) {
                    run_partition=false;
                    // System.out.println(left_pointer + "is same as " + right_pointer);
                    return pivot_pointer;
                }

                else if(array[pivot_pointer] < (array[left_pointer]))  {
                    // System.out.println("Left: " + array[left_pointer] + " er storre enn pivot:  " + array[pivot_pointer]);
                    swap(array, pivot_pointer, left_pointer);
                    pivot_pointer= left_pointer;
                }
                else if( left_pointer < 0){
                    break;
                    }
                else {
                    left_pointer++;
                }
            }             
        }
            return -1;

    }



    public void quicksort(int [] array, int start, int end) {

        // The pivot pointer starts at the first element initially, array index = 0
        // The left pointer points to first element initially
        // The right pointer points to last element initially
        // All elements to the right of pivot must be greater than pivot
        // All elements to the left of pivot must be smalelr than pivot
        // The pivot pointer starts at the first element initially, array index = 0
         // The left pointer points to first element initially
         if(end<=start || start>=end){
             return;
         }
         if(start <= end) {
            int partition_index = partition_array(array,start,end);
            quicksort(array,start,partition_index-1);
            quicksort(array,partition_index+1,end);

        }
        // System.out.println(Arrays.toString(array));
    }

    public void swap(int[] array, int index_left, int index_right) {
        int temp = array[index_left];
        array[index_left] = array[index_right];
        array[index_right] = temp;
    }        
}

I expect the code to work for larger array input.

end<=start and start>=end are 2 ways of saying exactly the same thing, and if neither is true, start<=end must be (in fact, start<end). — Scott Hunter
Re: "I expect [...] that the running time should be running in O(nlogn) worst case running time": I don't understand why you would expect this from an implementation of Quicksort, which has a worst-case time complexity of O(n²). Can you clarify where this expectation came from? — ruakh

maitreyak maitreyak · Accepted Answer · 2019-10-27T23:26:03

The algorithm implementation uses recursion, given a large input your call stack grows, which is mostly likely what caused the program to stack overflow. You have to implement an iterative version to handle large arrays.

My own version of quicksort only seems to work for small arrays

1 Answers