PLEASE READ ALL INSTRUCTIONS!!! YOUR CODE MUST COMPILE AND PASS BOTH DRIVERS!!!
ID: 3539838 • Letter: P
Question
PLEASE READ ALL INSTRUCTIONS!!!
YOUR CODE MUST COMPILE AND PASS BOTH DRIVERS!!!
I NEED YOUR CODE WITH DETAILED COMMENTS EXPLAINING YOUR CODE USING //.
THANKS!!!
Your task is to implement quicksort. You will put the implementation into a class called Qsort.java.
you will do this by implementing four methods, the first is provided for you:
The second and third methods are similar:
and
public static int[] greaterThan(int[] array, int pivot)
The first method should create an array that contains everything in array which
is less than pivot. The second method will return an array containing everything in array which is greater than the pivot. For example, lessThan([1, 4, 10, 2, 7, 12], 7) returns the array [1, 4, 2]. On the other hand, greaterThan([1, 4, 10, 2, 7, 12], 7) returnsthearray[10, 12]. The following is psuedocode for the lessThan method
(greaterThan psuedocode is similar):
Step 4 will require some careful thinking, because you cannot use the same index variable for both the input array and the created array.
The third method, has the following header:
the method should return an array containing everything in f (in its original order) then s, then everything in t (in its original order). For example, the following call to append append([2, 3, 1], 8, [4, 5, 0]) should return the array [2, 3, 1, 8, 4, 5, 0].
Here is driver one:
Explanation / Answer
Hi ,
Please try this out.. Hope it Helps :)
public class Qsort {
public static int[] quicksort(int[] array)
{
if(array.length <= 1) return array;
int pivot = array[array.length - 1];
int[] lt = lessThan(array, pivot);
int[] gt = greaterThan(array, pivot);
lt = quicksort(lt);
gt = quicksort(gt);
return append(lt, pivot, gt);
}
public static int[] lessThan(int[] array, int pivot)
{
// Loop to calculate the number of items less than pivot
int arraySize=0;
for(int i=0;i<array.length;i++)
{
if(array[i]<pivot)
{
arraySize++;
}
}
// Now that we have the size, we can define array and assign the items to it
int [] lessArray = new int[arraySize];
int counter=0;
for(int i=0;i<array.length;i++)
{
if(array[i]<pivot)
{
lessArray[counter]=array[i];
counter= counter+1;
}
}
return lessArray;
}
public static int[] greaterThan(int[] array, int pivot)
{
// Loop to calculate the number of items greater than pivot
int arraySize=0;
for(int i=0;i<array.length;i++)
{
if(array[i]>pivot)
{
arraySize++;
}
}
// Now that we have the size, we can define array and assign the items to it
int [] moreArray = new int[arraySize];
int counter=0;
for(int i=0;i<array.length;i++)
{
if(array[i]>pivot)
{
moreArray[counter]=array[i];
counter= counter+1;
}
}
return moreArray;
}
public static int[] append(int[] f, int s, int[] t)
{
int len1 = f.length;
int len2 = t.length;
// calculate the total length of expected array
int totallength = len1 + 1+ len2;
int tcounter=0;
int [] finalArray = new int[totallength];
for(int i=0;i<totallength;i++)
{
// copy the first array elements till len1
if(i<len1)
{
finalArray[i] = f[i];
}
// copy the middle element
else if(i==len1)
{
finalArray[i] = s;
}
// use a counter to copy the last array elements
else if(i>len1)
{
finalArray[i] = t[tcounter];
tcounter=tcounter+1;
}
}
return finalArray;
}
// Thats it , you are good to go :)
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.