In the real world, our unsorted data is not necessarily in a random order. The d
ID: 3807556 • Letter: I
Question
In the real world, our unsorted data is not necessarily in a random order. The data could be almost sorted (i.e., its inversion number is small). In this situation, using neither the first element nor the last element as the pivot in QuickSort is a good choice. Because the two parts divided by the pivot element is quite uneven, this will make the QuickSort algorithm close to the worst case (O(n 2 ) in complexity). To avoid this situation, we can choose the pivot more wisely by picking a random element in the array. Implement a quicksort method by using a random element in the array as a pivot. (Hint: you can use the Math.random() function to generate the index of a random element.)
Explanation / Answer
code:
void Rand_qsort(int a[],int s,int r)
{
int q;
if(s<r)
{
q=Rand_part(a,s,r);
Rand_qsort(a,s,q-1);
Rand_qsort(a,q+1,r);
}
}
int Rand_part(int a[],int p,int r)
{
int i=p+rand()%(r-p+1);
int t;
t=a[r];
a[r]=a[i];
a[i]=t;
return part(a,p,r);
}
int part(int a[],int p,int r)
{
int t,t1;
int x=a[r];
int i=p-1;
for(int j=p;j<=r-1;j++)
{
if(a[j]<=x)
{
i=i+1;
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
t1=a[i+1];
a[i+1]=a[r];
a[r]=t1;
return i+1;
}