Quick Sort Optimization Consider the QuickSort algorithm for sorting arrays SEEN
ID: 3546350 • Letter: Q
Question
Quick Sort Optimization
Consider the QuickSort algorithm for sorting arrays SEEN BELOW and two algorithm optimization proposals QuickSortOpt1 and QuickSortOpt2, described below. QuickSortOpt1 executes QuickSort until partitions size gets lower than a given cutoff value (usually 10) and then, executes Insertion Sort for sorting the small partitions. QuickSortOpt2 executes QuickSort until all partitions size gets lower than a given cutoff value (usually 10) and then, executes the improved Bubble Sort algorithm upon the whole "almost sorted" array.
Part1 Design and implement the QuickSortOpt1 and QuickSortOpt2 algorithms. Write a Java program to test the functionality of these algorithms. Define an array of size 100, randomly populated with Integer or int values in the range 1 .. 999 and sort the array in increasing order by using the QuickSort algorithm followed by QuickSortOpt1 and then by QuickSortOpt2. Display the array content before sorting and then after invoking each sorting method.
Part 2 Using System.nanoTime() method, measure the execution time of the three sorting algorithms, for each of the array sizes (see table below), and display the average execution time values for 10 runs. Consider the arrays as being randomly populated with Integer or int values in the range 1 .. MAX as specified in the table below for each SIZE value. Notes. (1) The array content should not be displayed for Part 2. (2) The algorithms should be executed and the required values should be displayed within one run, without modifying the source code and recompiling the project file(s).
SUGGESTIONS by the professsor:
I suggest defining the classes Term, Polynomial and Test.
The class Polynomial defines, as its main data structure, an instance variable of type List (JCF ArrayList or JCF LinkedList) of Term objects, each term defining the exponent and the coefficient.
Alternatively, instead of a list of Terms, you may decide to use: (i) a list of integers - the even indices will store the exponents while the odd indices will store coefficients or (ii) two lists of integers one for the exponents and one for the coefficients.
The class Test defines the main method. In the main method you should define a List of Polynomials (JCF ArrayList or JCF LinkedList) to store (for each polynomial read from the input file), its name and a reference to the Polynomial object (where the exponents and coefficients are stored).
In the main method, you should read the input file line by line.
For each read line you should: (1) take the polynomial name and store it in the list of polynomials, and (2) take the exponents and coefficients and build a Polynomial object then store the reference to this object in the list of polynomials (in association with polynomial name).
For adding / subtracting polynomials, to get an overview of the process and then the work idea, I suggest drawing the two Polynomial objects and tracing by hand how the operations are executed. Basically you have to generate the new polynomial (term by term), from the terms of the two polynomials that are added (or subtracted).
You may assume that there are no errors in polynomials representation in the input file.
QuickSort:
public class Quicksort{
public static void quickSort(int[] list){
quickSort(list, 0, list.length - 1);
}
public static void quickSort(int[] list, int first, int last){
if (last > first){
int pivotIndex = partition(list, first, last);
quickSort(list, first, pivotIndex - 1);
quickSort(list, pivotIndex + 1, last);
}
}
/** Partition the array list[first..last] */
public static int partition(int[] list, int first, int last){
int pivot = list[first]; // Chose the first element as the pivot
int low = first + 1; // Index for forward search
int high = last; // Index for backwards search
while (high > low){
// Search forward from left
while (low <= high && list[low] <= pivot)
low++;
// Search backward from right
while(low <= high && list[high] > pivot)
high--;
// Swap two elements in the list
if (high > low) {
int temp = list[high];
list[high] = list[low];
list[low] = temp;
}
}
while (high > first && list[high] >= pivot)
high--;
// Swap pivot with list[high]
if (pivot > list[high] {
list[first] = list[high];
list[high] = pivot;
return high;
}
else{
return first;
}
}
Explanation / Answer
public static void quickSort(int[] s, int l, int r)
{
int i, j;
int x, y;
i = l; j = r;
x = s[(l + r) / 2];
do
{
while ((s[i] < x) && (i < r))
i++;
while ((x < s[j]) && (j > l))
j--;
if (i <= j)
{
y = s[i];
s[i] = s[j];
s[j] = y;
i++; j--;
}
} while (i <= j);
if (l < j) quickSort(s, l, j);
if (i < r) quickSort(s, i, r);
}
static void Main(string[] args)
{
DateTime Time1, Time2;
Time1 = DateTime.Now;
Console.WriteLine("The time is: {0}", Time1);
Random ranNum = new Random();
int[] s = new int[10000];
for (int j = 0; j < 1000; j++)
{
Console.Write(j + " ");
for (int i = 0; i < 10000; i++)
{
s[i] = ranNum.Next(25);
}
quickSort(s, 0, 9999);
}
Time2 = DateTime.Now;
Console.WriteLine(" The time is: {0}", Time2);
Console.WriteLine(" The elapsed time is: {0}", Time2 - Time1);
Console.ReadLine();
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.