Question: Given an array, a[i], . . . , a[j], with j i 2, let k = (i + j)/2 and

Question

Question: Given an array, a[i], . . . , a[j], with j i 2, let k = (i + j)/2 and choose as the... (1 bookmark) Given an array, a[i], . . . , a[j], with j i 2, let k = (i + j)/2 and choose as the partition element for Quicksort the median among a[i], a[j], a[k] (i.e., the value that would be in the middle if a[i], a[j], and a[k] were sorted). This is called median-of-three partitioning. (NOTE: There are several descriptions of the median-of-three method on the web. Students are not permitted to seek out these descriptions in solving this problem.) (a) Write pseudocode for median-of-three partitioning. (b) What is the running time of median-of-three partitioning? Justify your answer. (c) What is the running time of Quicksort if you use median-of-three partitioning on an input set that is already sorted? Justify your answer. (d) Implement Quicksort using a normal pivot process and the median-of-three process described above. Test your run time analysis of medium-of-three, and then compare the average and worst case run times of Quicksort with the two pivot processes. Note that you must implement all of these algorithms from scratch. Also remember that CPU time is not a valid measure for testing run time. You must use something such as the number of comparisons. Code needed in java.

Explanation / Answer

a)Pseudo Code for median of two partitioning:-

median(int i, int j) {
int k = (i+ j) / 2;
if (A[i] > data[m]) // Compare first and middle element
swap(i, k);

if (A[i] > data[j])   // Compare first and last element
swap(i, j);

if (data[k] > data[j])   // Compare middle and last element
swap(k, j);

swap(k, j- 1); // put pivot on right
return A[j-1]; // return median value
}

partition(int i, int j, int piv) {

    int l = i + 1; // right of first element

    int r = j - 1; // left of pivot

    while (true) {

while (A[++l] < pivot); // finding the bigger element

while (A[--r] > pivot) ; // finding the smaller element

      if (l>= r) // when the pointers inersect then partition is done

break;

      else

swap(l, r); // If pointers don't intersect, then swap elements

    }

    swap(l, r- 1); // restore the pivot

    return l; // return pivot location

  }

-----------------------------------------------------------------------------------------------------------------------------------------------------

b) input: A[] ={12,63,40,31,93,83,57}

For the above input, in case of the median of three partitioning of 7 numbers, the recursive quicksort function called itself 5 times. (runtime-0.977s)

For the above input, in case of the selecting 1st element as pivot of 7 numbers, the recursive quicksort function called itself 5 times (runtime 0.981s)

Thus, it took almost the same time for execution of both programs.

---------------------------------------------------------------------------------------------------------------------------------------------------------

c) input: A[] ={12,31,40,57,63,83,93}

For the above input, in case of the median of three partitioning of 7 numbers, the recursive quicksort function called itself 3 times. Thus, it took less time to run the program as compared to the previously unsorted array. (runtime-0.971s)

---------------------------------------------------------------------------------------------------------------------------------------------------

d)

public class QuickSort {
public long[] a;

private int len;
  
public int runtime = 0;
  
private boolean medianOfThree;

public QuickSort(int max) {
a = new long[max];
len = 0;
}

public void insert(long value) {
a[len] = value; // insert and increment size
len++;
}

public void display() {
if(medianOfThree)
System.out.print("Quick Sorted With Median Of Three:");
else if(!medianOfThree)
System.out.print("Quick Sorted Without Median Of Three:");
else
System.out.print("Array:");
for (int j = 0; j < len; j++)
System.out.print(a[j] + " ");
System.out.println("");
System.out.println("runtime="+runtime);
}

public void quickSort(boolean x) {
medianOfThree = x;
quickSortWithPartition(0, len - 1);
}

public void quickSortWithPartition(int left, int right) {
++runtime;
int size = right - left + 1;
if (size <= 3) // manual sort if small
manualSort(left, right);
else // quicksort if large
{
long median;
if(medianOfThree)   
median = medianOf3(left, right);
else
median = a[0];
median = a[right-1];
int partition = partitionIt(left, right, median);
quickSortWithPartition(left, partition - 1);
quickSortWithPartition(partition + 1, right);
}
}

public long medianOf3(int left, int right) {
int center = (left + right) / 2;
// order left & center
if (a[left] > a[center])
swap(left, center);
// order left & right
if (a[left] > a[right])
swap(left, right);
// order center & right
if (a[center] > a[right])
swap(center, right);

swap(center, right - 1); // put pivot on right
return a[right - 1]; // return median value
}

public void swap(int dex1, int dex2) {
long temp = a[dex1];
a[dex1] = a[dex2];
a[dex2] = temp;
}

public int partitionIt(int left, int right, long pivot) {
int leftPtr = left; // right of first elem
int rightPtr = right - 1; // left of pivot

while (true) {
// find bigger
while (a[++leftPtr] < pivot)
;
// find smaller
while (a[--rightPtr] > pivot)

;
if (leftPtr >= rightPtr) // if pointers cross, partition done
break;   
else
// not crossed, so
swap(leftPtr, rightPtr); // swap elements
}
swap(leftPtr, right - 1); // restore pivot
return leftPtr; // return pivot location
}

public void manualSort(int left, int right) {
int size = right - left + 1;
if (size <= 1)
return; // no sort necessary
if (size == 2) { // 2-sort left and right
if (a[left] > a[right])
swap(left, right);
return;
} else // size is 3
{ // 3-sort left, center, & right
if (a[left] > a[right - 1])
swap(left, right - 1); // left, center
if (a[left] > a[right])
swap(left, right); // left, right
if (a[right - 1] > a[right])
swap(right - 1, right); // center, right
}
}

public static void main(String[] args) {
int maxSize = 7;
QuickSort arr = new QuickSort(maxSize);

for (int j = 0; j < maxSize; j++) { // random numbers
long n = (int) (java.lang.Math.random() * 99);
arr.insert(n);
}
  
arr.a = new long[]{12,63,40,31,93,83,57};
arr.display();
arr.quickSort(true);
arr.display();
arr.runtime = 0;
arr.a = new long[]{12,63,40,31,93,83,57};
arr.quickSort(false);
arr.display();
}
}

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.