CODEWITHSUNDEEP
javaalgorithmquicksort
bug
bug

Reputation: 71

My Quicksort algorithm is running too slow

I am sorting 32 bit random integers using Quicksort algorithm. When I sort 10 or 100 or 1000 elements algorithm works quickly but when I choose n=10.000 it takes approximately 15minutes to sort. I want to increase n to 10000000 but then algorithm will take forever. I could not find what is wrong in my implementation.

Here is my main function

 public static void main(String[] args) {

    for(int i=0; i<100; i++){

    Random rand = new Random(new Date().getTime()); //different seed for each run

    createRandArray(rand);  
    long startTime= System.nanoTime();
    sort();
    long finishTime= System.nanoTime();
    }

Here is the implementation of Quicksort

  public static void sort(){
        int left = 0;
        int right = my_array.length-1;
        quickSort(left, right);
    }

    private static void quickSort(int left,int right){

        if(left >= right)
            return;

        BigInteger pivot = my_array[right];
        int partition = partition(left, right, pivot);

        quickSort(0, partition-1);
        quickSort(partition+1, right);

    }

    private static int partition(int left,int right,BigInteger pivot){
        int leftCursor = left-1;
        int rightCursor = right;

        while(leftCursor < rightCursor){

                while(my_array[++leftCursor].compareTo(pivot)==-1);
                while(rightCursor > 0 && my_array[--rightCursor].compareTo(pivot)==1);

            if(leftCursor >= rightCursor){
                break;
            }
            else{
                swap(leftCursor, rightCursor);
            }
        }

        swap(leftCursor, right);
        return leftCursor;
    }

    public static void swap(int left,int right){

        BigInteger temp = my_array[left];
        my_array[left] = my_array[right];
        my_array[right] = temp;
    }

This is how I create the 32 bit rand integer array

 public static void createRandArray(Random rand ){

        BigInteger big_int=new BigInteger("1"); //initialization

        for(int i=0; i<100 ; i++){
        big_int= new BigInteger(32, rand);
        my_array[i]= big_int;
    }
}

Any help will be appreciated.

Upvotes: 1

Views: 1368

Answers (1)

vandale
vandale

Reputation: 3650

You are incorrectly assuming the lower bound is zero instead of left in a couple places hence you are doing more work than you need to:

in quickSort(int left,int right):

quickSort(0, partition-1);
to
quickSort(left, partition-1);

and in partition(int left,int right,BigInteger pivot):

while(rightCursor > 0 && my_array[--rightCursor].compareTo(pivot)==1);
to
while(rightCursor > left && my_array[--rightCursor].compareTo(pivot)==1);

Upvotes: 6

Related Questions