i have to write a quicksort-algorithm with a random pivot so i created the following code:
public void quickSort(int left, int right)
{
if(a.length == 1)
{
System.out.println("Only one element.");
}
else
{
int l = left;
int r = right;
if(right > left)
{
Random rand = new Random();
int num = left + rand.nextInt(right - left);
int p = a[num];
int tmp = a[r];
a[r] = a[num];
a[num] = tmp;
num = r;
r--;
while(r > l)
{
while((l<right)&&(a[l]<=p))
{
l++;
}
while((r > left)&&(a[r]>=p))
{
r--;
}
if(l < r)
{
tmp = a[l];
a[l] = a[r];
a[r] = tmp;
}
}
if(a[l] > p) {
tmp = a[l];
a[l] = a[num];
a[num] = tmp;
}
quickSort(left,l-1);
quickSort(l+1,right);
}
}
}
"a" is supposed to be an int-Array. As you can see, as soon as I get my random pivot I swap it with the last element of the array so I don't get any problems with the algorithm, but I wonder if there is a possibility to let the pivot stay at it's random position and sort it without problems, nevertheless. Thx in advance.
Aucun commentaire:
Enregistrer un commentaire