Project Specification: Step 1: (Send the output to “p6part1out.txt” and have you
ID: 3705664 • Letter: P
Question
Project Specification:
Step 1: (Send the output to “p6part1out.txt” and have your name displayed on the first line.)
Generate random integers between 0 and the maximum value of Integer type to fill two arrays of size 10,000 each with the same value. Call these arrays “array1” and “array2”.
Slightly modify the sample program “ArraySorter” (line 189) so that you can use them to sort “array2”.
Use nanoTime() to record the time it takes for each algorithm to sort “array2”.
To verify if you have used the sort program correctly, print the first 20 and the last 20 numbers of the sorted array.
Copy array1 to array2 before you try the different algorithm so that the same unsorted array will be used.
Repeat the above steps for 20 times.
Use Spreadsheet to record the time, find the average time for each algorithm and draw a line graph based upon Average time and the Sort algorithm.
Your program logic should be like the following:
For I from 1 to 20 do {
Generate 100,000 random integers to fill “array1” and “array2”;
startTime = nanoTime();
Call Sort1 using array2;
elapseTime = nanoTime() – startTime;
printFirstLast20(outfile1, array2);
outfile1.println(“Sort1-“ + I + “: Time = “ + elapseTime);
copyArray(array1, array2);
startTime = nanoTime();
Call Sort2 using array2;
elapseTime = nanoTime() – startTime;
printFirstLast20(outfile2, array2);
outfile.println(“Sort2-“ + I + “: Time = “ + elapseTime);
…(repeat the same process for every sort algorithm)…
}
Finally, compile the above result and write your finding as you did Project 5. Call this file “p6report.docx”
Step 2: (Send the output to “p6part2out.txt” and have your name displayed on the first line.)
Apply step 1 to “p1arts” instead of integers. i.e., Read in “p1arts” into an array of Art class that you define in project 2.
Have the records sorted on ArtID within ArtistID.
Display the columns in the order of artistID, artID, artName, and then artValue.
Sort this once only for every sorting algorithm.
Tabulate and draw the line graphf.
Add the result to “p6sortsResult.docx”
Explanation / Answer
From the above:
public class Driver
{
public static void main(String[] args)
{
Name jane1 = new Name("Jane", "Doe");
Name jane2 = new Name("Jane", "Doe");
Name jane3 = new Name("Jane", "Smith");
Name lila = new Name("Lila", "Bleu");
Name derek = new Name("Derek", "Greene");
System.out.println("Testing Name's equals method: ");
System.out.println("Comparing Jane Doe and another Jane Doe using the method equals: " +
jane1.equals(jane2));
System.out.println("Comparing Jane Doe and Jane Smith using the method equals: " +
jane1.equals(jane3));
System.out.println(" Testing Name's compareTo method: ");
System.out.print("Comparing Derek Greene and Lila Bleu using the method compareTo: ");
if (derek.compareTo(lila) < 0)
System.out.println(derek + " is before " + lila + "<--- ERROR!");
else if (derek.compareTo(lila) > 0)
System.out.println(derek + " is after " + lila);
else
System.out.println(derek + " equals " + lila + "<--- ERROR!");
System.out.println("Comparing Lila Bleu and Derek Greene using the method compareTo: ");
if (lila.compareTo(derek) < 0)
System.out.println(lila + " is before " + derek);
else if (lila.compareTo(derek) > 0)
System.out.println(lila + " is after " + derek + "<--- ERROR!");
else
System.out.println(lila + " equals " + derek + "<--- ERROR!");
System.out.println("Comparing Lila Bleu and Lila Bleu using the method compareTo: ");
if (lila.compareTo(lila) < 0)
System.out.println(lila + " is before " + lila + "<--- ERROR!");
else if (lila.compareTo(lila) > 0)
System.out.println(lila + " is after " + lila + "<--- ERROR!");
else
System.out.println(lila + " equals " + lila);
System.out.println("Comparing Lila Bleu and Jane Doe using the method compareTo: ");
if (lila.compareTo(jane1) < 0)
System.out.println(lila + " is before " + jane1);
else if (lila.compareTo(jane1) > 0)
System.out.println(lila + " is after " + jane1 + "<--- ERROR!");
else
System.out.println(lila + " equals " + jane1 + "<--- ERROR!");
System.out.println(" Done.");
} // end main
} // end Driver
public class Name implements Comparable<Name>
{
private String first; // First name
private String last; // Last name
public Name()
{
this("", "");
} // end default constructor
public Name(String firstName, String lastName)
{
first = firstName;
last = lastName;
} // end constructor
public void setName(String firstName, String lastName)
{
setFirst(firstName);
setLast(lastName);
} // end setName
public String getName()
{
return toString();
} // end getName
public void setFirst(String firstName)
{
first = firstName;
} // end setFirst
public String getFirst()
{
return first;
} // end getFirst
public void setLast(String lastName)
{
last = lastName;
} // end setLast
public String getLast()
{
return last;
} // end getLast
public void giveLastNameTo(Name aName)
{
aName.setLast(last);
} // end giveLastNameTo
public String toString()
{
return first + " " + last;
} // end toString
public boolean equals(Object other)
{
boolean result;
if ((other == null) || (getClass() != other.getClass()))
result = false;
else
{
Name otherName = (Name)other;
result = first.equals(otherName.first) &&
last.equals(otherName.last);
} // end if
return result;
} // end equals
public int compareTo(Name other) // As given in the answer to Self-Test Question 1 in Java Interlude 3
{
int result = last.compareTo(other.last);
// If last names are equal, check first names
if (result == 0)
result = first.compareTo(other.first);
return result;
} // end compareTo
} // end Name
/**
A class of static, iterative methods for sorting an array of
Comparable objects from smallest to largest.
@author Frank M. Carrano
@author Timothy M. Henry
@version 4.0
*/
public class ArraySorter
{
// SELECTION SORT
public static <T extends Comparable<? super T>> void selectionSort(T[] a, int n)
{
for (int index = 0; index < n - 1; index++)
{
int indexOfNextSmallest = getIndexOfSmallest(a, index, n - 1);
swap(a, index, indexOfNextSmallest);
} // end for
} // end selectionSort
private static <T extends Comparable<? super T>>
int getIndexOfSmallest(T[] a, int first, int last)
{
T min = a[first];
int indexOfMin = first;
for (int index = first + 1; index <= last; index++)
{
if (a[index].compareTo(min) < 0)
{
min = a[index];
indexOfMin = index;
} // end if
} // end for
return indexOfMin;
} // end getIndexOfSmallest
// -------------------------------------------------------------------------------
// INSERTION SORT
public static <T extends Comparable<? super T>>
void insertionSort(T[] a, int n)
{
insertionSort(a, 0, n - 1);
} // end insertionSort
public static <T extends Comparable<? super T>>
void insertionSort(T[] a, int first, int last)
{
for (int unsorted = first + 1; unsorted <= last; unsorted++)
{ // Assertion: a[first] <= a[first + 1] <= ... <= a[unsorted - 1]
T firstUnsorted = a[unsorted];
insertInOrder(firstUnsorted, a, first, unsorted - 1);
} // end for
} // end insertionSort
private static <T extends Comparable<? super T>>
void insertInOrder(T anEntry, T[] a, int begin, int end)
{
int index = end;
while ((index >= begin) && (anEntry.compareTo(a[index]) < 0))
{
a[index + 1] = a[index]; // Make room
index--;
} // end for
a[index + 1] = anEntry; // Insert
} // end insertInOrder
// -------------------------------------------------------------------------------
// BUBBLE SORT
public static <T extends Comparable<? super T>>
void bubbleSort(T[] a, int n)
{
for (int lastIndex = n - 1; lastIndex > 0; lastIndex--)
{
for (int index = 0; index < lastIndex; index++)
order(a, index, index + 1);
}
} // end bubbleSort
private static <T extends Comparable<? super T>>
void order(T[] a, int i, int j)
{
if (a[i].compareTo(a[j]) > 0)
swap(a, i, j);
// Assertion: a[j] is larger
} // end order
// -------------------------------------------------------------------------------
// BETTER BUBBLE SORT
// Exercise 10, Chapter 8
public static <T extends Comparable<? super T>>
void betterBubbleSort(T[] a, int n)
{
for (int lastIndex = n - 1; lastIndex > 0; lastIndex--)
{
int lastSwapIndex = 0;
for (int index = 0; index < lastIndex; index++)
{
if (a[index].compareTo(a[index + 1]) > 0)
{
swap(a, index, index + 1);
lastSwapIndex = index;
} // end if
} // end for
lastIndex = lastSwapIndex + 1;
} // end for
} // end betterBubbleSort
// -------------------------------------------------------------------------------
// MERGE SORT
public static <T extends Comparable<? super T>>
void iterativeMergeSort(T[] a, int n)
{
// The cast is safe because the new array contains null entries
@SuppressWarnings("unchecked")
T[] tempArray = (T[])new Comparable<?>[a.length]; // unchecked cast
int beginLeftovers = n;
for (int segmentLength = 1; segmentLength <= n/2; segmentLength = 2*segmentLength)
{
beginLeftovers = mergeSegmentPairs(a, tempArray, n, segmentLength);
// Two full segments do not remain at end; the following are possibilites:
// a. one full segment and a partial second segment
// b. one full segment only
// c. one partial segment
// d. nothing is left at end
int endSegment = beginLeftovers + segmentLength - 1;
if (endSegment < n - 1)
// Case a: one full segment and a partial second segment exist, so merge them
merge(a, tempArray, beginLeftovers, endSegment, n-1);
// else Cases b, c, or d: only one full or partial segment is left (leave it in place)
// or nothing is left
} // end for
// merge the sorted leftovers, if any, with the rest of the sorted array
if (beginLeftovers < n)
merge(a, tempArray, 0, beginLeftovers-1, n-1);
} // end iterativeMergeSort
// Merges pairs of segments of a given length within an array
// and returns the index after the last merged pair.
private static <T extends Comparable<? super T>>
int mergeSegmentPairs(T[] a, T[] tempArray, int n, int segmentLength)
{
int mergedPairLength = 2 * segmentLength; // Length of two merged segments
int numberOfPairs = n / mergedPairLength;
int beginSegment1 = 0;
for (int count = 1; count <= numberOfPairs; count++)
{
int endSegment1 = beginSegment1 + segmentLength - 1;
int beginSegment2 = endSegment1 + 1;
int endSegment2 = beginSegment2 + segmentLength - 1;
merge(a, tempArray, beginSegment1, endSegment1, endSegment2);
beginSegment1 = endSegment2 + 1;
} // end for
return beginSegment1; // Return index of element after last merged pair
} // end mergeSegmentPairs
private static <T extends Comparable<? super T>>
void merge(T[] a, T[] tempArray, int first, int mid, int last)
{
// Two adjacent subarrays are a[beginHalf1..endHalf1] and a[beginHalf2..endHalf2].
int beginHalf1 = first;
int endHalf1 = mid;
int beginHalf2 = mid + 1;
int endHalf2 = last;
// While both subarrays are not empty, copy the
// smaller item into the temporary array
int index = beginHalf1; // Next available location in tempArray
for (; (beginHalf1 <= endHalf1) && (beginHalf2 <= endHalf2); index++)
{ // Invariant: tempArray[beginHalf1..index-1] is in order
if (a[beginHalf1].compareTo(a[beginHalf2]) < 0)
{
tempArray[index] = a[beginHalf1];
beginHalf1++;
}
else
{
tempArray[index] = a[beginHalf2];
beginHalf2++;
} // end if
} // end for
// Finish off the nonempty subarray
// Finish off the first subarray, if necessary
for (; beginHalf1 <= endHalf1; beginHalf1++, index++)
// Invariant: tempArray[beginHalf1..index-1] is in order
tempArray[index] = a[beginHalf1];
// Finish off the second subarray, if necessary
for (; beginHalf2 <= endHalf2; beginHalf2++, index++)
// Invariant: tempa[beginHalf1..index-1] is in order
tempArray[index] = a[beginHalf2];
// Copy the result back into the original array
for (index = first; index <= last; index++)
a[index] = tempArray[index];
} // end merge
// -------------------------------------------------------------------------------
// Swaps the array entries a[i] and a[j].
private static void swap(Object[] a, int i, int j)
{
Object temp = a[i];
a[i] = a[j];
a[j] = temp;
} // end swap
} // end ArraySorter
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.