Big data

Download a book from www.gutenberg.org

Read the words from the book into an ArrayList and then sort three times, once with each sort type (Selection, merge and then Collections sort method) .

Translate the Selection Sort and Merge Sort provided at the bottom of this assignment into code that works with an ArrayList of Strings.

Print and calculate the elapsed time with the following, and then print the first 15 items of the sorted list to be sure it is really sorted.

For each of the 3 sorts, do this: (Selection, merge and then Arrays or Collections sort method)

start = System.currentTimeMillis();

System.out.println(start);

// do your sort

end = System.currentTimeMillis();

System.out.println(end);

System.out.println("sort time span is " + (end - start));

Upload to Lab Gutenberg And Lab2 Finch when you are done.

----------------------------------------------

Here are the 2 sort methods you are translating. It is important that you translate these as closely as possible instead of pulling the code from the internet.

Guides:

· Change all int[] to ArrayList<String>

· Change element access to an arraylist get method: from something like arr[i] to arr.get(i)

· Change element setting to an arraylist set method: from something like arr[i] = 7 to arr.set(i,7);

· Change integer operations to string operations, so change x < y to: x.compareTo(y) < 0 and x== y to x.compareTo(y) == 0 or x.equals(y);

· For the merge sort, you can use the Arraylist's sublist method to grab just a range of items.

public static void selectionSort ( int [ ] num )

{

int i, j, smallestIndex;

int temp;

for ( i = 0 ; i < num.length ; i ++ )

{

smallestIndex = i;

for(j = i+1; j < num.length; j ++) //locate smallest element between positions 1 and i.

{

if( num[ j ] < num[smallestIndex] )

smallestIndex = j;

}

temp = num[ smallestIndex ]; //swap smallest found with element in position i.

num[ smallestIndex ] = num[ i ];

num[ i ] = temp;

}

}

public static void mergeSort(int[] num){

if (num.length > 1) {

// split into two halves

int[] left = Arrays.copyOfRange(num, 0, num.length / 2);

int[] right = Arrays.copyOfRange(num, num.length / 2, num.length );

// sort those halves (further splitting)

mergeSort(left);

mergeSort(right);

// merge the sorted halves into wholes

merge(num, left,right);

}

}

public static void merge(int[] result, int[] left, int[] right){

int leftIndex = 0;

int rightIndex = 0;

for (int i = 0; i < result.length; i++){

if (rightIndex >= right.length

|| (leftIndex < left.length && left[leftIndex] <= right[rightIndex])){

// take from left

result[i] = left[leftIndex];

leftIndex++;

}

else // take from right

{

result[i] = right[rightIndex];

rightIndex++;

}

}

}