Introduction:

Sorting is so important that every programming language has this function built in. Yet, every Data Structures textbook spends a great number of pages on this topic. Since this function is provided by the programming language, why should we still need to learn the inner working of different sorting algorithms? There are several reasons:

Computers have spent more time doing sorting than doing anything else.

Sorting is so important that it is the most thoroughly studied problem in computer science.

Through the various implementations of sorting come many important concepts. Therefore, sorting has become the basic building block that many other algorithms are built upon.

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

Turn in:

Your modified version of ArraySorter;

P6Step1.java, p6Step2.java, both output text files, and p6report.docs.

These are the Sample programs

III. Sample Programs: Comparable, Generics, and Some Selected Sorts /** A driver that demonstrates the Comparable aspect of the class Name (Java Interlude 3 version). @author Frank M. Carrano @author Timothy M. Henry @version 4.0 */ 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

/* Testing Name's equals method: Comparing Jane Doe and another Jane Doe using the method equals: true Comparing Jane Doe and Jane Smith using the method equals: false Testing Name's compareTo method: Comparing Derek Greene and Lila Bleu using the method compareTo: Derek Greene is after Lila Bleu Comparing Lila Bleu and Derek Greene using the method compareTo: Lila Bleu is before Derek Greene Comparing Lila Bleu and Lila Bleu using the method compareTo: Lila Bleu equals Lila Bleu Comparing Lila Bleu and Jane Doe using the method compareTo: Lila Bleu is before Jane Doe Done. */ ________________________________________ /** A mutable class that represents a person's comparable name. @author Frank M. Carrano @author Timothy M. Henry @version 4.0 */ public class Name implements Comparable { 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

// 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 > 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 > 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