You will need the QuickSort.java and Pair.java files for this lab. Examine the Q
ID: 3830813 • Letter: Y
Question
You will need the QuickSort.java and Pair.java files for this lab.
Examine the QuickSort class to see what methods it contains.
Problem 1: Recall how the partition algorithm works:
The variables start, end, left, and right are array indexes, not elements.
The partition is identified by the indexes start and end.
Choose a pivot.
Swap the pivot with the element at the beginning of the partition.
Let left be start+1.
Let right be end.
Until right passes left:
Advance left towards the end of the partition until it encounters an element that is >= the pivot.
Advance right towards the start of the partition until it encounters an element < the pivot.
If left < right,
Swap the elements at left and right.
Swap the pivot with right.
Return right.
If there are many duplicate elements, there may be many elements equal to the pivot. To improve Quick Sort, we can modify this algorithm so that it places all elements equal to the pivot between the two partitions. In this way, neither partition will contain an element that is equal to the pivot. This is called fat partitioning.
Fat partitioning works the same way as partitioning, except that elements that are equal to the pivot are swapped to the beginning or end of the partition and then swapped into the middle after partitioning is done.
There are two more indexes to keep track of: leftPivots and rightPivots.
leftPivots is initialized to start + 1
rightPivots is initialized to end
leftPivot marks the start of the left partition, not counting the pivot elements at the beginning.
rightPivots marks the end of the right partition, not counting the pivot elements at the end.
pivot elements
left partition
right partition
pivot elements
Whenever left encounters an element equal to the pivot:
Swap the elements at left and leftPivots.
Advance leftPivots to the right.
Whenever right encounters an element equal to the pivot:
Swap the elements at right and rightPivots.
Advance rightPivots to the left.
Once the partition is done when right passes left, you must swap all of the pivot elements to the middle, between the partitions using the following algorithm:
Left pivots:
Move leftPivots one element to the left.
Until leftPivots passes start:
Swap the elements at leftPivot and right.
Move both indexes one element to the left.
Right pivots:
Move rightPivots one element to the right.
Until rightPivots passes end:
Swap the elements at left and rightPivots.
Move both indexes one element to the right.
When fat partitioning is done, left marks the beginning of the right partition and right marks the end of the left partition. All elements between indexes right and left are equal to the pivot.
left partition
pivot elements
right partition
This is a tricky algorithm to get right.
Test your algorithm using the testPartition method. Do NOT try to use fat partitioning with Quick Sort.
If you have fat partitioning working correctly (after several tests!), then you can modify Quick Sort to use fat partitioning instead of the regular partitioning. If you manage to get Quick Sort working again, run five tests of Quick Sort. Is there an improvement over the regular partitioning?
________________________________
pivot elements
left partition
right partition
pivot elements
Explanation / Answer
Methods in Quick Sort:
1. public static void quickSort(int[] a)
This method takes array that need to sort
THis method call : private static void quickSort(int[] a, int start, int end)
2. private static void quickSort(int[] a, int start, int end)
This method recursively call itsef for left and rigth part
3. public static int partition(int[] a, int start, int end)
THis method partation the array in two parts.
It choose the pivot as median of first, last and middle element of array portion
It is used by quickSort method
4. public static int middleOf3(int[] a, int x, int y, int z)
It returns the median of three numbers.
It is used by partation method
5. public static void printArray(int[] a): To print array a
6. public static void swap(int[] a, int i, int j): to swap two numbers in array
7. public static int[] generateRandom(int size): to generate size random numbers
8. public static boolean isSorted(int[] a): TO check whether array a is sorted or not
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.