For the Java Exercise, you need to implement the following sorting methods:

 

• Insertion sort

• Cocktail Shaker sort

• A variation of Quick Sort

• External sort

 

You also need to implement an efficient, linear time, algorithm that takes two sorted arrays and returns an array of the elements that occur in both arrays.

 

You may not use any built-in sorting methods (or in-built classes from the Collections framework such as ArrayList, LinkedList, HashMap etc.) for this Exercise.

 

Implementation Details

 

The starter code has been provided to you. Fill in code in class SortingImplementation that implements the following SortingInterface (it's important that you do not modify the signatures of any methods):

 

public interface SortingInterface {

 

void insertionSort(Comparable[] array, int lowindex, int highindex, boolean reversed); void shakerSort(Comparable[] array, int lowindex, int highindex, boolean reversed); void modifiedQuickSort(Comparable[] array, int lowindex, int highindex);

void externalSort(String inputFile, String outputFile, int k, int m);

 

}

 

 

 

You will also need to implement the method intersectionOfSortedArrays that takes two sorted arrays and returns an array of elements that occur in both arrays.

 

You should not use any instance variables for this exercise apart from constants; use only local method variables. You may write private helper methods.

 

We describe each of the sorting algorithms below:

 

 

 

1. Insertion Sort

 

public void insertionSort(Comparable[] array, int lowindex, int highindex, boolean reversed);

 

Modify the code of the insertion sort so that:

 

• It sorts all elements in the array with indices in the range from lowindex to highindex

 

(inclusive). Youshouldnotchangeelementsoutsidetherangelowindextohighindex.

 

• If reversed is false, the list should be sorted in ascending order. If the reversed flag is true, the list should be sorted in descending order.

• Can sort the array of any Comparable objects, not just integers.

 

2. Cocktail Shaker Sort

 

public void shakerSort(Comparable[] array, int lowindex, int highindex, boolean reversed);

 

 

This is a variation of the bubble sort that sorts in both directions (bubbles the largest element to the end, and bubbles the smallest element to the front on each pass). It has the same asymptotic running time as bubble sort.

 

The first pass consists of two parts: we first iterate over the array from left to right and bubble the largest element to the end of the list. Then we take the leftward pass (iterate from the (last-1) element to the first element) and bubble the smallest element to the front of the array.

The second pass will first bubble the second largest element to the end of the list (to index last-1) and then shift the second smallest element to the correct position at index 1.

...

 

After each pass, we reduce the size of the list that needs to be sorted by two elements.

 

Example (assume we want to sort the list in ascending order, and lowindex =0, and highindex = array.length-1): 4, 10, 6, 9, 2, 3, 8, 4

After the first part of pass 1 we get: 4, 6, 9, 2, 3, 8, 4, 10 (the largest element is in the last position).

 

After the second part of pass 2 (iterating from right to left): 2, 4, 6, 9, 3, 4, 8, 10. The smallest element is in the first position. Now we need to sort the list from index 1 to index last -1.

After the first part of pass 2, the list will look like this: 2, 4, 6, 3, 4, 8, 9, 10.

After the second part of pass 2 we get: 2, 3, 4, 6, 4, 8, 9, 10

We will now sort from index 2 to index 5 (inclusive):

 

After the first part of pass 3 we get: 2, 3, 4, 4, 6, 8, 9, 10. The list won't change after the second part of pass 3. It would now need to sort the list from index 3 to index 4. The list won't change, and we are done. Note: your code should work for any lowindex, highindex and in both ascending and descending order.

 

3. Modified Quick Sort

 

public void modifiedQuickSort(Comparable[] array, int lowindex, int highindex);

 

Change the code of the quick sort so that:

 

- It sorts the sub-list of the original list (from lowindex to highindex)

 

- At each pass, it picks three elements of the sub-list:

 

- the first element in the sublist (at index lowindex),

 

- the middle element of the sublist (in the middle between lowindex and highindex)

 

- the last element of the sublist (at index highindex),

 

and uses the median of these three elements as the pivot. How do you compute a median of three values? If we "sort" three elements, the median is the element in the middle (for instance, if the three elements are 5, 2, 19, the median is 5); note that it is different from mean (average)! Do not use the mean.

 

Example: Consider the following array 5, 2, 9, 12, 6, 8, 3, 1 and assume we want to sort the array from lowindex = 2 to highindex = 7 (so from elements 9 to 1). We first find three elements we are considering for our first pivot: 9, 6 and 1 (9 is the element at lowindex, 1 is the element at highindex, and 6 is the middle element in the sublist). We order them and get 1, 6, 9. And take the median one, the one in the middle, 6. This is our pivot for the first pass of quick sort.

 

We then run quicksort as usual:

5, 2, 9, 12, 1, 8, 3, 6 (swap the pivot with the element at highindex).

 

i starts at index lowindex=2, so points at 9 which is larger than the pivot. j points at 3 which is smaller than the pivot. Swap them:

5, 2, 3, 12, 1, 8, 9, 6

 

i now points at 12, j moves until it points to 1 (an element less than the pivot. We swap 12 and 1 and increment i, decrement j:

5, 2, 3, 1, 12, 8, 9, 6

 

i and j now overlap, so we are done with the first pass, we just need to swap the pivot with the element at i and get:

5, 2, 3, 1, 6, 8, 9, 12

 

So the first pass split the sublist into elements < 6, 6 and elements > 6. We now need to recursively run quicksort on sublists 3, 1 and 8, 9, 12. Why didn't we include 5, 2? Because we were given a lowindex = 2, so we do not look at the first two elements. For each sublist, we would again pick potential pivot elements and choose a median as a pivot. If the sublist contains only two elements, randomly pick one of the two as the pivot. Finish this example before you start coding this version of quick sort.

 

4. External Sort

 

public void externalSort(String inputFile, String outputFile, int k, int m);

 

What if we need to sort a very large list that does not fit into memory all at once? Then you need to use external sort that stores partial results in files on the disk. Assume we can only fit k integers into memory at a time, and we have a text file that contains N integers (one per line, to keep it simple). We can read k integers from the file at a time, store them in a list and sort the list using some existing efficient sorting algorithm such as quicksort. Then we can write the result to a temporary file. We can repeat this process for another chunk of the original file. We would need to do it m (number of chunks) = ceiling(N/k) times, until all the partial results are stored in temporary files (the provided test expects you to call them "temp0.txt", "temp1.txt", ..., "temp99.txt"). In this method, k (how many integers can fit in an array) and m (the number of chunks) are passed as parameters to the method. Please note that N is not passed as a parameter (but it can be determined from the number of lines in a file).

 

We need to merge the sorted sublists stored in the temp files into a single sorted "list" stored in the output file. You can use the algorithm similar to the merge step of the mergesort, except that you would read data from the temp files (all of them need to be open at the same time, you may use an array of BufferedReaders for that) and keep writing the numbers to another file as your algorithm proceeds with the merge. You will read the first number from each temporary file, find the minimum of those numbers, and write it to the output file. Then read another number from the file that contained the minimum and again find the minimum of the currently read set of numbers and write it to the output file. For this problem, the list in the output file should be sorted in ascending order.

 

Consider the following example (to keep the example short, let's assume the input file has 6 numbers, and our tiny memory is only able to fit k = 3 integers at a time):

 

8

4

10

3

7

5

 

The external sort algorithm will read m = 2 chunks from the input file: [8, 4, 10] and [3, 7, 5], sort them with quicksort and save the sorted sublists in two temporary files:

"temp0.txt" 4

 

8

10

 

"temp1.txt" 3

5

7

 

It will then open both temp files and merge them as following: it will first read 4 and 3 (the first numbers in each temp file), save them into the temporary array, find the minimum (3) and write it to the output file (assume it is called "output"):

"output" 3

Then it would read another number from "temp1" since it's the file that contained the minimum element. Now the array of elements is [4 , 5], the minimum is a 4 and we write it to the output file" "output"

3

4

 

We read another number from "temp0", 8, and the array is [5, 8]. The minimum is a 5, we write it to the output file:

"output" 3

4

5

 

We read another number from "temp1", a 7, the array is now [8, 7], the minimum is 7 and the output file is:

"output" 3

4

5

7

 

We continue as before until we write all the elements to the output file. The temporary files can then be deleted (although you are not required to delete them in your program).

To test your external sort, create a large file of integers (also done in the test file, provided in the zip file).

 

5. Find "Intersection" of two sorted lists

 

Implement the method intersectionOfSortedArrays that takes two sorted arrays and returns an array of elements that occur in both arrays.

For instance, if we pass the following two sorted arrays to the method:

int[] arr1= {2, 10, 12, 34, 90};

int[] arr2 = {4, 6, 8, 10, 11, 12, 14, 20, 26, 30, 34, 48, 50};

then the method should return: {10, 12, 34}.

 

Note: your method should be general and work for any two sorted arrays of integers. It is required that it runs in linear time: Theta(n1+n2), where n1 and n2 are the sizes of the two lists and takes advantages of the fact that the input lists are sorted.

 

Testing

 

The zip file provides some basic tests for testing several methods of the project, but they simply check if the list is sorted after running your algorithm. Passing the tests does not guarantee that your code is correct; you should also do your own testing and are encouraged to write your own tests.

 

Code Style

Your code needs to adhere to the code style described in the StyleGuidelines.pdf document. You may receive a deduction if your code does not follow these guidelines.

 

package sorting;

/** A class that implements SortingInterface. Has various methods

* to sort a list of elements. */

public class SortingImplementation implements SortingInterface {

 

/**

* Sorts the sublist of the given list (from lowindex to highindex)

* using insertion sort

* @param array array of Comparable-s

* @param lowindex the beginning index of a sublist

* @param highindex the end index of a sublist

* @param reversed if true, the list should be sorted in descending order

*/ @Override

public void insertionSort(Comparable[] array, int lowindex, int highindex, boolean reversed) {

// FILL ON CODE

 

}

 

/**

* Sorts the sublist of the given list (from lowindex to highindex)

* using the shaker sort (see pdf for description)

* @param array array of Comparable-s

* @param lowindex the beginning index of a sublist

* @param highindex the end index of a sublist

* @param reversed if true, the list should be sorted in descending order

*/

public void shakerSort(Comparable[] array, int lowindex, int highindex, boolean reversed) {

 

}

 

 

/**

* Sorts the sublist of the given list (from lowindex to highindex)

* using the following modification of quick sort:

* At each pass, it picks three elements of the sub-list:

* - the first element in the sublist (at index lowindex),

* - the middle element of the sublist (in the middle between lowindex and highindex)

* - the last element of the sublist (at index highindex)

* and chooses the median of these three elements as the pivot.

* How do you compute a median of three values?

* If we "sort" three elements, the median is the element in the middle

* (for instance, if the three elements are 5, 2, 19, the median is 5);

* note that it is different from mean! Do NOT take the average of the 3 numbers, pick the median instead.

*

* @param array array to sort

* @param lowindex the beginning index of a sublist

 

* @param highindex the end index of a sublist

*/ @Override

public void modifiedQuickSort(Comparable[] array, int lowindex, int highindex) {

// FILL ON CODE

}

 

 

/**

* Implements external sort method

* @param inputFile The file that contains the input list

* @param outputFile The file where to output the sorted list

* @param k number of elements that fit into memory at once

* @param m number of chunks

*/

public void externalSort(String inputFile, String outputFile, int k, int m) {

// FILL IN CODE

 

}

 

 

/**

* Takes two sorted arrays and returns an array of all the elements that occur in both arrays.

* For instance, if we pass the following two sorted arrays to the method:

* int[] arr1= {2, 10, 12, 34, 90};

* int[] arr2 = {4, 6, 8, 10, 11, 12, 14, 20, 26, 30, 34, 48, 50};

* then the method should return: {10, 12, 34}

* Note: your method should be general and work for any two sorted arrays of integers.

* It is required that it runs in linear time: Theta(n1+n2),

* where n1 and n2 are the sizes of the two lists and takes advantages of the fact that the input lists are sorted.

* Hint: you can modify the merge helper method we wrote in class to solve this problem.

* @param arr1 sorted array 1

* @param arr2 sorted array 2

* @return array of common elements in arr1 and arr2

*/

public int[] intersectionOfSortedArrays(int[] arr1, int[] arr2) {

// FILL IN CODE

int[] res = new int[arr1.length]; // you can computer the actual number of common elements as you go,

// and later return the array of the correct length using copyOf method in class Arrays

 

return res;

}

 

}

 

package sorting;

 

/** An interface that describes several algorithms for sorting a list */ public interface SortingInterface {

void insertionSort(Comparable[] array, int lowindex, int highindex, boolean reversed);

void shakerSort(Comparable[] array, int lowindex, int highindex, boolean reversed); void modifiedQuickSort(Comparable[] array, int lowindex, int highindex);

void externalSort(String inputFile, String outputFile, int k, int m);

 

}

 

This assignment has been answered 2 times in private sessions.