Lab 6
Quick Sort Part I
(Not Generic)
Implement the quicksort algorithm using Java.
Create a class QuickSorter.java
that implements the quicksort algorithm over arrays of Integers
(later on we will use generic lists). You may
use this file as a
template. Your goal is twofold:
-
Complete the partition method.
-
Fill in the recursive portion of the quicksort algorithm
within the `quicksort' method.
You may use the following algorithm for your partition method:
Function Partition(
array,
start,
end)
pivotI ← GetPivotI(
start,
end)
pivot ←
array[pivotI]
Swap(
end,
pivotI)
// Move pivot to the end
large ←
start
For index from start upto end
If array[index] >
pivot
Swap(index, large)
large ← large + 1
EndIf
EndFor
Swap(
large,
end)
Return large
// Return the index of the pivot
EndFunction
After you have completed the above, you should
experiment with the `getPivotIndex' method to see how this
affects the time of the algorithm. Here are some ideas to try:
-
First item of the array (already done for you)
-
Last item of the array.
-
Middle element of the array.
-
Randomized location within the array.
Be careful not to introduce potential ArrayIndexOutOfBoundsExceptions
Upload the .java file to the dropbox