Teaching Lessons
Merge Sort - 4/18
Notes
- splits array into 2 parts, sorts each half individually
- most effective way to implement is to use a recursive function
Hacks
#1
Use the integer mergesort that we created and adapt it to sort an array of Java String objects. We recommend using the compareTo() method of the String class for this.
/**
* Main class for MergeSortPractice.java
*
*/
public class MergeSortPractice
{
private static String[] cars =
{ "Volvo", "BMW", "Ford", "Mazda" };
/**
* merge
*
* @param cars
* @param left
* @param middle
* @param right
*/
public static void merge(String[] cars, int left, int middle, int right)
{
// finds sizes of 2 subarrays
int n1 = middle - left + 1; // lower
int n2 = right - middle; // upper
String[] lower = new String[n1];
String[] upper = new String[n2];
// copies data from first array to lower array
for (int Lloop = 0; Lloop < n1; Lloop++)
{
lower[Lloop] = cars[left + Lloop];
}
// copies data from first array to upper array
for (int Rloop = 0; Rloop < n2; Rloop++)
{
upper[Rloop] = cars[middle + 1 + Rloop];
}
int i = 0;
int j = 0;
int k = left;
while ((i < n1) && (j < n2))
{
if ((lower[i].compareTo(upper[j])) >= 0)
{
cars[k] = upper[j];
j++;
}
else
{
cars[k] = lower[i];
i++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1)
{
cars[k] = lower[i];
i++;
k++;
}
/* Copy remaining elements of R[] if any */
while (j < n2)
{
cars[k] = upper[j];
j++;
k++;
}
}
/**
* sort
*
* @param arr
* @param left
* @param right
*/
static void sort(String arr[], int left, int right)
{
if (left < right)
{
// COMMENT A
int m = left + (right - left) / 2;
// COMMENT B
sort(arr, left, m);
sort(arr, m + 1, right);
// COMMENT C
merge(arr, left, m, right);
}
}
/**
* main
*
* @param args
*/
public static void main(String[] args)
{
for (int i = 0; i < cars.length; i++)
{
System.out.println(cars[i]);
}
System.out.println();
sort(cars, 0, cars.length - 1);
for (int i = 0; i < cars.length; i++)
{
System.out.println(cars[i]);
}
}
}
MergeSortPractice.main(null);
Binary Sort - 4/18
Notes
- data must be sorted beforehand
- one of the fastest searching algorithms
Hacks
#1
Given an int array[] = {1, 3, 5, 7, 9, 23, 45, 67}, search the number 45 and give it's index with Binary search, BUT do this using recursion. Make sure to include informative comments to explain the code as you write the algorithm.
/**
* Main class for BinarySearchPractice.java
*
*/
public class BinarySearchPractice
{
/**
* sort
*
* @param arr
* @param left
* @param right
* @param num
* @return
*/
public int sort(int arr[], int left, int right, int num)
{
if(right >= left)
{
// middle elements
int middle = left + (right - 1) / 2;
if (arr[middle] == num)
{
return middle;
}
if (arr[middle] > num)
{
return sort(arr, left, middle-1, num);
}
// returns sort method
return sort(arr, left, middle + 1, num);
}
return -1;
}
/**
* main
*
* @param args
*/
public static void main (String[] args)
{
BinarySearchPractice test = new BinarySearchPractice();
int arr[] = {1, 3, 5, 7, 9, 23, 45, 67};
int num = 45;
int sorted = test.sort(arr, arr.length/2, arr.length/2, 45);
System.out.println(sorted);
System.out.printf("\n");
for(int i = 0; i < arr.length; i++)
{
System.out.printf("%d\n", arr[i]);
}
}
}
BinarySearchPractice.main(null);
/**
* Main class for ExtraPractice.java
*
*/
public class ExtraPractice
{
public static int[] arr = {5, 6, 3, 1, 8, 9, 4, 7, 2};
/**
* merge
*
* @param arr
* @param l
* @param m
* @param r
*/
public static void merge(int arr[], int l, int m, int r)
{
// Find the sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */
int[] L = new int[n1];
int[] R = new int[n2];
/* Copy data to temp arrays */
for (int i = 0; i < n1; ++i)
L[i] = arr[l + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[m + 1 + j];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarray array
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = R[j];
j++;
}
else {
arr[k] = L[i];
i++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of R[] if any */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
/**
* sort
*
* @param arr
* @param l
* @param r
*/
public static void sort(int arr[], int l, int r)
{
if (l < r) {
// the middle element
int m = l + (r - l) / 2;
// calls sort method
sort(arr, l, m);
sort(arr, m + 1, r);
// merges the array
merge(arr, l, m, r);
}
}
/**
* main
*
* @param args
*/
public static void main (String[] args)
{
System.out.println("Before Sort:");
for (int i = 0; i < arr.length; i++)
{
System.out.printf("%d ", arr[i]);
}
System.out.println("\n");
sort(arr, 0, arr.length - 1);
System.out.println("After Sort:");
for (int i = 0; i < arr.length; i++)
{
System.out.printf("%d ", arr[i]);
}
// searches for the number 7
BinarySearchPractice test = new BinarySearchPractice();
int num = 7;
System.out.println("\n");
System.out.printf("Binary Search for %d:\n", num);
// prints arrays
for (int i = 0; i < arr.length; i++)
{
System.out.printf("%d ", arr[i]);
}
System.out.println();
// prints which element that has the value 7
for(int i = 0; i < arr.length; i++)
{
if(arr[i] == num)
{
System.out.printf("%d has been found in element %d.\n", num, i);
}
}
}
}
ExtraPractice.main(null);
/**
* setArray
*
* @param arr
* @param n
*/
public static void setArray(int[] arr, int n)
{
// your code here
for (int i = 0; i < arr.length; i++)
{
arr[i] = n;
}
}
int[] array = new int[10];
setArray(array, 10);
for (int i = 0; i<array.length; i++)
{
System.out.println(array[i]);
}
//Finds the average in an array
public static int average(int[] array)
{
int avg = 0;
for(int i = 0; i < array.length; i++)
{
avg += array[i];
}
avg /= array.length;
return avg;
}
//tester array
int[] test = {3, 5, 7, 2, 10};
//returns the average
System.out.println("Average: " + average(test));
/**
* averageDiagonal
*
* @param array2D
* @return
*/
public static int averageDiagonal (int[][] array2D)
{
int avg = 0;
int num = 0;
for(int row = 0; row < numRows; row++)
{
for (int col = 0; col < numCols; col++)
{
if(row == col)
{
avg += array2D[row][col];
num++;
}
}
}
avg /= num;
return avg;
}
int[][] arr =
{
{1,2,3,4,5,6},
{7,8,9,10,11,12},
{0,1,2,3,4,5},
{10,11,12,13,14,15},
{15,16,17,18,19,20}
};
int numRows = 5;
int numCols = 6;
for(int row = 0; row < numRows; row++)
{
for (int col = 0; col < numCols; col++)
{
if(row == col)
{
System.out.printf("[%d]\t", arr[row][col]);
}
else
{
System.out.printf("%d\t", arr[row][col]);
}
}
System.out.printf("\n");
}
System.out.println("\nAverage: " + averageDiagonal(arr));
public class ArrayTester
{
final static int NUM_ROWS = 4;
final static int NUM_COLS = 3;
/** Returns an array containing the elements of column c of arr2D in the same order as
* they appear in arr2D.
* Precondition: c is a valid column index in arr2D.
* Postcondition: arr2D is unchanged.
*/
public static int[] getColumn (int [][] arr2D, int c)
{
int[] arr = new int[arr2D.length];
for(int row = 0; row < arr2D.length; row++)
{
arr[row] = arr2D[row][c];
}
return arr;
}
/** Returns an array containing the elements of row r of arr2D in the same order as
* they appear in arr2D.
* Precondition: c is a valid column index in arr2D.
* Postcondition: arr2D is unchanged.
*/
public static int[] getRow (int [][] arr2D, int r)
{
int[] arr = new int[arr2D.length];
for(int col = 0; col < arr2D[0].length; col++)
{
arr[col] = arr2D[r][col];
}
return arr;
}
/** Returns true if and only if every value in arr1 appears in arr2.
* Precondition: arr1 and arr2 have the same length.
* Postcondition: arr1 and arr2 are unchanged.
*/
public static boolean hasAllValues(int[] arr1, int[] arr2)
{
/* implementation not shown */
return true;
}
/** Returns true if arr contains any duplicate values;
* false otherwise.
*/
public static boolean containsDuplicates(int[] arr)
{
/* implementation not shown */
return true;
}
/** Returns true if square is a Latin square as described in part (b);
* false otherwise.
* Precondition: square has an equal number of rows and columns.
* square has at least one row.
*/
public static boolean isLatin(int[][] square)
{
/* to be implemented in part (b) */
int[] arr1 = new int[square.length];
int[] arr2 = new int[square.length];
for(int i = 0; i < square.length; i++)
{
arr1 = ArrayTester.getColumn(square, i);
arr2 = ArrayTester.getRow(square, i);
}
if((hasAllValues(arr1, arr2)) && (containsDuplicates(arr1)))
{
return true;
}
return false;
}
public static void main(String[] args)
{
int[][] arr2D = { { 0, 1, 2 },
{ 3, 4, 5 },
{ 6, 7, 8 },
{ 9, 5, 3 } };
int[] result = ArrayTester.getColumn(arr2D, 1);
for(int i = 0; i< result.length; i++)
{
System.out.println(result[i]);
}
int[][] square = { {1, 2, 3},
{2, 3, 1},
{3, 1, 2}};
System.out.printf("\nSquare:\n");
for(int row = 0; row < square.length; row++)
{
for (int col = 0; col < square.length; col++)
{
System.out.printf("%d\t", square[row][col]);
}
System.out.printf("\n");
}
boolean result1 = ArrayTester.isLatin(square);
System.out.println("\n" + result1);
}
}
ArrayTester.main(null);
/**
* Main class for Position.java
*
*/
public class Position
{
/** Constructs a Position object with row r and column c. */
public Position(int r, int c)
{
/* implementation not shown */
}
// There may be instance variables, constructors, and methods that are not shown.
/**
* findPosition
*
* @param num
* @param intArr
* @return
*/
public static Position findPosition (int num, int[][] intArr)
{
for(int row = 0; row < intArr.length; row++)
{
for(int col = 0; col < intArr[0].length; col++)
{
if (intArr[row][col] == num)
{
return new Position(row, col);
}
}
}
return null;
}
/**
* getSuccessorArray
*
* @param intArr
* @return
*/
public static Position[][] getSuccessorArray(int[][] intArr)
{
Position[][] newArr = new Position[intArr.length][intArr[0].length];
for (int row = 0; row < intArr.length; row++)
{
for (int col = 0; col < intArr[0].length; col++)
{
newArr[row][col] = findPosition(intArr[row][col] + 1, intArr);
}
}
return newArr;
}
/**
* main
*
* @param args
*/
public static void main(String[] args)
{
int[][] arr2D = {{15, 5, 9, 10},
{12, 16, 11, 6},
{14, 8, 13, 7}};
Position position = findPosition(8, arr2D);
System.out.println(position);
System.out.println(getSuccessorArray(arr2D));
}
}
Position.main(null);
import java.util.ArrayList;
/**
* Main class for StringFormatter.java
*
*/
public class StringFormatter
{
/**
* totalLetters
*
* @param wordList
* @return
*/
public static int totalLetters(List<String> wordList)
{
int total = 0;
for (String word : wordList)
{
total += word.length();
}
return total;
}
/**
* basicGapWidth
*
* @param wordList
* @param formattedLen
* @return
*/
public static int basicGapWidth(List<String> wordList, int formattedLen)
{
int total = totalLetters(wordList);
int arrSize = wordList.size();
int gapWidth = (formattedLen - total) / (arrSize - 1);
return gapWidth;
}
/**
* leftoverSpaces
*
* @param wordList
* @param formattedLen
* @return
*/
public static int leftoverSpaces(List<String> wordList, int formattedLen)
{
return 0;
}
/**
* format
*
* @param wordList
* @param formattedLen
* @return
*/
public static String format(List<String> wordList, int formattedLen)
{
String formatted = "";
int gapWidth = basicGapWidth(wordList, formattedLen);
int leftovers = leftoverSpaces(wordList, formattedLen);
for (int w = 0; w < wordList.size() - 1; w++)
{
formatted += wordList.get(w);
for (int i = 0; i < gapWidth; i++)
{
formatted += " ";
}
if (leftovers > 0)
{
formatted += " ";
leftovers--;
}
}
formatted += wordList.get(wordList.size() - 1);
return formatted;
}
/**
* main
*
* @param args
*/
public static void main(String[] args)
{
ArrayList <String> wordList = new ArrayList <String>();
wordList.add("AP");
wordList.add("COMP");
wordList.add("SCI");
wordList.add("ROCKS");
int length = wordList.size();
System.out.println(basicGapWidth(wordList, length));
System.out.println(totalLetters(wordList));
System.out.println(format(wordList, length));
}
}
StringFormatter.main(null);
/**
* Main class for LargestSum.java
*
*/
public class LargestSum
{
/**
* highestSum
*
* @param arr
* @return
*/
public static int highestSum(int[][] arr)
{
int[] sums = new int[arr2D[0].length];
// number of columns
int c = sums.length;
// iterates through each column of 2D array and adds each value together
for (int col = 0; col < c; col++)
{
int sum = 0;
for(int row = 0; row < arr2D.length; row++)
{
sum += arr2D[row][col];
// adds sum into an array w/ collection of the sums from each column
sums[row] = sum;
}
}
// compares each element in the column sums array
int max = sums[0];
for (int i = 0; i < sums.length; i++)
{
if (sums[i] > max)
{
max = sums[i];
}
}
// returns max sum
return max;
}
/**
* main
*
* @param args
*/
public static void main (String[] args)
{
int[][] arr2D = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9}};
System.out.printf("Largest column sum: %d", highestSum(arr2D));
}
}
LargestSum.main(null);