Hi all,
I am trying to implement the algorithm for Quicksort in ascending order and desending order for Students array and Price array.
But i am getting Wrong answer for the results of the sort.My algorithm works for some set of numbers and fails for some.
I cant understand where i am going wrong.I dont want to use the default sort functions in java..
Can anyone help me to solve this problem?
import java.io.*;
import java.lang.*;
import java.util.*;
class CADYDIST
{
static long stu[];
static long pri[];
public static void main(String args[])throws IOException
{
Scanner scan = new Scanner(System.in);
int n;int i,j,temp;long sum;
while((n=scan.nextInt())!=0)
{
int cz=0,pz=0;
stu= new long[n];
pri= new long[n];
for(i=0;i<stu.length;i++)
stu[cz++]=scan.nextLong();
for(i=0;i<pri.length;i++)
pri[pz++]=scan.nextLong();
QsortAsc(pri,0,n-1);
//System.out.println(Arrays.toString(pri));
QsortDesc(stu,0,n-1);
//System.out.println(Arrays.toString(stu));
sum=0;
for(i=0;i<n;i++)
sum+=stu[i]*pri[i];
System.out.println(sum);
}
}
private static void QsortAsc(long[] A,int low,int high)
{
int pivot;
// Termination condition!
if (high > low) {
pivot = PartitionAsc(A, low, high);
QsortAsc(A, low, pivot - 1);
QsortAsc(A, pivot + 1, high);
}
}
private static void QsortDesc(long[] A,int low,int high)
{
int pivot;
if(low<high)
{
pivot=PartitionDesc(A,low,high);
QsortDesc(A,low,pivot-1);
QsortDesc(A,pivot+1,high);
}
}
private static int PartitionAsc(long[] A,int low,int high)
{
int left, right;long pivot_item = A[low];
left = low;
right = high;
while (left < right) {
// Move left while item < pivot
while (A[left] <= pivot_item)
left++;
// Move right while item > pivot
while (A[right] > pivot_item)
right--;
if (left < right)
swap(A, left, right);
}
// right is final position for the pivot
A[low] = A[right];
A[right] = pivot_item;
return right;
}
private static int PartitionDesc(long[] A,int low,int high)
{
int right,left;long pivot_item=A[low];
left=low;
right=high;
while(left<right)
{
while(A[left]>=pivot_item)
left++;
while(A[right]<pivot_item)
right--;
if(left<right)
swap(A,left,right);
}
A[low]=A[right];
A[right]=pivot_item;
return right;
}
private static void swap(long[]A,int left,int right)
{
long temp=0;
temp = A[left];
A[left] = A[right];
A[right] = temp;
}
}