a) Describe a way of arranging elements of an array of length n such that the ru
ID: 3847052 • Letter: A
Question
a) Describe a way of arranging elements of an array of length n such that the running time would be a worst-case for your InsertionSort algorithm.
b) Write a program to determine the size n of the array that gives a running time of 1000 milliseconds. (Similar to (a) in Part 1.)
c) Create a worst-case array as described in (a) for 50 ”equally spaced sizes” between 1 and the size determined in part (b); and compute the running time of your algorithm on these arrays.
d) Plot the results of (b) on a graph alongside a plot of the analytical well-known worst-case running time of insertion sort and a best fit polynomial curve of degree 2.
e) Create a pdf file that shows the plots from (d) and explain the differences you see in these plots.
f) Repeat (b) through (e) except use random data for your analysis instead of worst-case data. Be sure to also explain in the pdf reasons for differences between worse case data and random data.
Interfaces Implemented
import java.util.ArrayList;
public interface sortAnalysis<E extends Comparable<? super E>> {
/**
* Sorts the list of elements and returns the amount of time required to sort them. (in milliseconds)
* @param list
* A list of comparable elements to be sorted and analyzed.
* @return list The time required to sort the list.
*/
public long analyzeSort(ArrayList<E> list);
}
public interface MatrixAnalysis {
/**
* @param double[][] m1 The first square matrix to multiply
* @param double[][] m2 The second square matrix to multiply
* @param double[][] m3 The result is placed in the square matrix m3 = m1 *
* @return long The time in the number of milliseconds for the mutiple to complete
*
*/
public long analyzeMultiply(double [][] m1, double[][] m2, double [][] m3);
/**
* @param double[][] m1 The square matrix to take the inverse of
*
* @param double[][] m2 The resultant inverse
*
* @return long The time in the number of milliseconds for the multiple to complete
*
*/
public long analyzeInverse(double [][] m1, double[][] m2);
}
Create a class called QuickSort that implements SortAnalysis in a file named QuickSort java. This quick sort implementation must be in place." Repeat steps (a) through (f) in Part 2 using this quicksort implementationExplanation / Answer
Hi, I have implemented QuickSort (Part 1) and part a) of PArt II.
Please repost other questions in separate post.
// Java program for implementation of QuickSort
public class QuickSort
{
/* This function takes last element as pivot,
places the pivot element at its correct
position in sorted array, and places all
smaller (smaller than pivot) to left of
pivot and all greater elements to right
of pivot */
int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low-1); // index of smaller element
for (int j=low; j<=high-1; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1;
}
/* The main function that implements QuickSort()
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void sort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
sort(arr, low, pi-1);
sort(arr, pi+1, high);
}
}
/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
// Driver program
public static void main(String args[])
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = arr.length;
QuickSort ob = new QuickSort();
ob.sort(arr, 0, n-1);
System.out.println("sorted array");
printArray(arr);
}
}
a) Describe a way of arranging elements of an array of length n such that the running time would be a worst-case for your InsertionSort algorithm.
If array elements are in decending order and you want to sort in ascending order, then this is worst case:
14, 13, 8, 6, 4, 2, 1
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.