CODEWITHSUNDEEP
javaquicksort
user3212703
user3212703

Reputation: 15

Why doesn't my quick sort code work?

Can anyone help me with my quick sort code because it doesn't get executed when I give data to it.

I don't get any answer. It's like it goes an infinite loop or something like that.

public class Provo {

public static void swap(int[] a, int i, int j)
{
    int temp=a[i];
    a[i]=a[j];
    a[j]=temp;
}

public static int HoarePartition(int m , int d, int[] a)
{ int pivot=a[m];
 int i=m;
 int j=d;

    while(i<j)
    {
        while(a[i]<pivot)
        {i=i+1;}

        while(a[j]>pivot)
        {j=j-1;}

        if(i<j)
         swap(a,i,j);
    }
    swap(a,m,j);

    return j;
}

public static void quicksort(int m, int d, int[] a)
{
    if (m<d)
    { int s=HoarePartition(m,d,a);
        quicksort(m,s-1,a);
        quicksort(s+1,d,a);
    }
}
}

Upvotes: 0

Views: 108

Answers (2)

xor
xor

Reputation: 2698

Problem is in HoarePartition() function the left index i.e. i should start searching for a value (greater than pivot) one ahead from the pivot itself.

so statement int i=m; should be int i=m+1;

EDIT:
Ensuring while(i<=j) rather than while(i<j) should do the trick

Upvotes: 0

linstantnoodles
linstantnoodles

Reputation: 4400

This part might be problematic:

if(i<j)
  swap(a,i,j);

What happens when both a[i] and a[j] equals the pivot element? That means they'll get swapped, but neither lo nor hi will get decremented, hence resulting in an infinite loop.

Try this:

if(i<j)
  swap(a,i++,j--);

That basically does a post-increment/decrement, ensuring that lo and hi get closer after every iteration.

Upvotes: 1

Related Questions