ArrayAlgorithms

• Let's start a program that will contain all of the array algorithms that we'll discuss the next few classes

• ArrayAlgorithms

• The main method will serve as a client for our algorithm methods

• We'll write an algorithm

• Our main method will use the algorithm

• We'll also write a test program as appropriate

 

Initializing Arrays - User Input

• Because arrays are indexed, using a loop to initialize arrays is really efficient

public static double[] getDoubleArray(int length) {

double[] array = new double[length];

Scanner in = new Scanner(System.in);

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

System.out.print("Double? ");

while (!in.hasNextDouble()) {

System.out.println("Not a double");

System.out.print("Double? ");

in.next(); //throw away the bad input

}

array[i] = in.nextDouble();

}

return array;

}

 

Initializing Arrays - Random

/**

* Fills the specified array with random values between 0 and

* the multiplier - 1 (i.e. between [0, multiplier))

* @param length the length of the array

* @param multiplier value to multiply Math.random by to fill

* the array

* @return the array of random values

*/

public static int[] fillRandom(int length, int multiplier) {

 

 

}

 

Arrays and Methods

public class ArrayAlgorithms {

public static void main(String[] args) {

int[] data = fillRandom(10, 4);

incrementAll(data);

}

/**

* Increments each value of the array by 1

* @param data array to increment

*/

public static void incrementAll(int[] data) {

}

}

 

This is easier to test...

/**

* Returns a String containing the contents

* of an array

* @param data the array to print

* @return A String containing the contents of

* the array, separated by a single space

*/

public static String printArray(int[] data) {

}

 

Exercises

• Build on our ArrayAlgorithms class and complete as many of the following exercises as you can

• Your main method should create arrays to pass into the methods your write and print any results with context!

• Each exercise will return an int, which you should print

• Use the printArray method to print array contents

• Create a test class, and test your methods as thoroughly as you can!

 

Exercise 1

• Write a method called lastIndexOf that accepts an array of integers and an integer value as its parameters, and returns the last index at which the value occurs in the array. The method should

return -1 if the value is not found.

• For example, in the array {74, 85, 102, 99, 101, 85, 56}, the last index of the value 85 is 5.

 

Exercise 2

• Write a method called range that returns the range of values in an array of integers. The range is defined as 1 more than the difference between the maximum and minimum values in the array.

• For example, if an array called list contains the values {36, 12, 25, 19, 46, 31, 22}, the call of range(list) should return 35 (46-12+1). You may assume that the array has at least one element.

 

Exercise 3

• Write a method called countInRange that accepts an array of integers, a minimum value, and a maximum value as parameters and returns the count of how many elements from the array fall between the minimum and maximum (inclusive).

• For example in the array {14, 1, 22, 17, 36, 7, -43, 5}, for minimum value 4 and maximum value 17, there are four elements whose values fall between 4 and 17.

 

Exercise 4

isSorted

• Write a method called isSorted that accepts an array of real numbers as a parameter and returns true if the list is in sorted (non-decreasing) order and false otherwise.

• For example, if arrays named array1 and array2 store {16.1, 12.3, 22.2, 14.4} and {1.5, 4.3, 7.0,

19.5, 19.5, 25.1, 46.2} respectively, the calls isSorted(array1) and isSorted(array2) should return false and true respectively.

• Assume the array has at least one element.

• A one-element array is considered to be sorted.

 

Exercise 5

append

• Write a method called append that accepts two integer arrays as parameters and returns a new array that contains the result of appending the second array's values at the end of the first array.

• For example, if array1 and array2 store {2, 4, 6} and {1, 2, 3, 4, 5} respectively, the call of append(array1, array2) should return a new array containing {2, 4, 6, 1, 2, 3, 4, 5}.

• If the arguments were reversed, the method would return an array containing {1, 2, 3, 4, 5, 2, 4, 6}.

 

Exercise 6

mode

• Write a method called mode that returns the most frequently occurring element of an array of integers.

• Assume that the array has at least one element.

• Break ties by choosing the lower value.

• For example, if the array passed contains the values {27, 15, 15, 11, 27}, your method should return 15.

 

Exercise 7

kthLargest

• Write a method called kthLargest that accepts an integer k and an array of integers as its parameters and returns the element such that k elements have greater or equal value.

• If k = 0, return the largest element; if k = 1, return the second largest element, and so on.

• For example, if the array passed contains the values {74, 85, 102, 99, 101, 56, 85}, and the integer k passed is 2, your method should return 99 because there are two values at least as large as 99 (101 and 102).

• Verify that 0 <= k < array.length

• Hint: Consider sorting the array or a copy of the array first.

 

Exercise 8

longestSortedSequence

• Write a method called longestSortedSequence that accepts an array of integers as a parameter and returns the length of the longest sorted (non-decreasing) sequence of integers in the array.

• For example, in the array {3, 8, 10, 1, 9, 14, -3, 0, 14, 207, 56, 98, 12}, the longest sorted sequence has four values (-3, 0, 14, 207), so your method would return 4.

• Non-decreasing means that there could be duplicates.

• Your method should return 0 if an empty array is passed in.

 

Exercise 9

2D arraysEqual

• Add a two-dimensional arraysEqual method to your ArrayAlgorithms class

• Return true if the arrays contain the same elements in the same order (assume both arrays contain only ints)

• If the arrays are not the same length in either dimension, your method should return false

 

 

import java.io.PrintStream;
import org.junit.Test;
import static org.junit.Assert.*;
public class ArrayAlgorithmsTest {
@Test
public void testFillRandom() {
int length = 0;
int multiplier = 0;
int expResult = null;
int result = ArrayAlgorithms.fillRandom(length, multiplier);
assertEquals(length, result.length);
//TODO: should also check each value to make sure it is &lt; the
multiplier
}
@Test
public void testIncrementAllWithEmptyArray() {
int data = {};
ArrayAlgorithms.incrementAll(data);
assertEquals(0, data.length);
}
@Test
public void testIncrementAll() {
int data = {1};
ArrayAlgorithms.incrementAll(data);
assertEquals(1, data.length);
assertEquals(2, data[0]);
data = new int{1, 2};
ArrayAlgorithms.incrementAll(data);
assertEquals(2, data.length);
assertEquals(2, data[0]);
assertEquals(3, data[1]);
data = new int{1, 2, 3};
ArrayAlgorithms.incrementAll(data);
assertEquals(3, data.length);
assertEquals(2, data[0]);
assertEquals(3, data[1]);
assertEquals(4, data[2]);
}
//@Test
public void testPrintArray_intArr_PrintStream() {
int data = null;
PrintStream output = null;
ArrayAlgorithms.printArray(data, output);
// TODO review the generated test code and remove the default call
to fail.
fail(&quot;The test case is a prototype.&quot;);
}
@Test
public void testPrintArrayWithEmptyArray() {
int data = {};
String expResult = &quot;&quot;;
String result = ArrayAlgorithms.printArray(data);
assertEquals(expResult, result);
} @Test
public void testPrintArrayWithOneElement() {
int data = {1};
String expResult = &quot;[1]&quot;;
String result = ArrayAlgorithms.printArray(data);
assertEquals(expResult, result);
}
@Test
public void testPrintArrayWithTwoElements() {
int data = {1, 2};
String expResult = &quot;[1, 2]&quot;;
String result = ArrayAlgorithms.printArray(data);
assertEquals(expResult, result);
}
@Test
public void testPrintArray() {
int data = {1, 2, 3, 4, 5};
String expResult = &quot;[1, 2, 3, 4, 5]&quot;;
String result = ArrayAlgorithms.printArray(data);
assertEquals(expResult, result);
}
@Test
public void testLastIndexOfWithEmptyArray(){
int data = {};
int expResult = -1;
int result = ArrayAlgorithms.lastIndexOf(data, 10); //with an empty
array, it should always return -1
assertEquals(expResult, result);
} 10)); @Test
public void testLastIndexOfWithValueNotFound(){
int expResult = -1;
assertEquals(expResult, ArrayAlgorithms.lastIndexOf(new int{1}, 10));
3}, 10));
} assertEquals(expResult, ArrayAlgorithms.lastIndexOf(new int{1, 2},
assertEquals(expResult, ArrayAlgorithms.lastIndexOf(new int{1, 2, @Test
public void testLastIndexOfWithValueFound(){
assertEquals(0, ArrayAlgorithms.lastIndexOf(new
assertEquals(0, ArrayAlgorithms.lastIndexOf(new
assertEquals(1, ArrayAlgorithms.lastIndexOf(new
assertEquals(0, ArrayAlgorithms.lastIndexOf(new
assertEquals(1, ArrayAlgorithms.lastIndexOf(new
assertEquals(2, ArrayAlgorithms.lastIndexOf(new
assertEquals(5, ArrayAlgorithms.lastIndexOf(new
99, 101, 85, 56}, 85));
} int{1}, 1));
int{1, 2}, 1));
int{1, 2}, 2));
int{1, 2, 3}, 1));
int{1, 2, 3}, 2));
int{1, 2, 3}, 3));
int{74, 85, 102, @Test
public void testRange(){
assertEquals(1, ArrayAlgorithms.range(new int{1}));
assertEquals(3, ArrayAlgorithms.range(new int{1, 2, 3}));
assertEquals(35, ArrayAlgorithms.range(new int{36, 12, 25, 19, 46,
31, 22}));
assertEquals(35, ArrayAlgorithms.range(new int{12, 36, 25, 19, 31,
22, 46})); 22, 12}));
22, -12}));
} 5)); assertEquals(35, ArrayAlgorithms.range(new int{46, 36, 25, 19, 31,
assertEquals(59, ArrayAlgorithms.range(new int{46, 36, 25, 19, 31, @Test
public void testCountInRange(){
assertEquals(3, ArrayAlgorithms.countInRange(new int{1, 2, 3}, 0, assertEquals(4, ArrayAlgorithms.countInRange(new int{14, 1, 22,
17, 36, 7, -43, 5}, 4, 17));
assertEquals(3, ArrayAlgorithms.countInRange(new int{4, 1, 2, 3,
4, 5, 6, 7, 4}, 4, 4));
try{
3}, 5, 0)); assertEquals(3, ArrayAlgorithms.countInRange(new int{1, 2,
fail(&quot;IllegalArgumentException expected&quot;);
} catch (IllegalArgumentException ex){
} }
@Test
public void testCountInstances(){
assertEquals(0, ArrayAlgorithms.countInstances(null, 0)); //test
with a null array
assertEquals(0, ArrayAlgorithms.countInstances(new int[0], 0));
assertEquals(3, ArrayAlgorithms.countInstances(new int{1,2,1,4,1},
1));
}
@Test
public void testIndexOf(){
assertEquals(-1, ArrayAlgorithms.indexOf(null, 0)); //test with a
null array
assertEquals(-1, ArrayAlgorithms.indexOf(new int[0], 0));
assertEquals(-1, ArrayAlgorithms.indexOf(new int{1,2,1,4,1}, 5));
assertEquals(0, ArrayAlgorithms.indexOf(new int{1,2,1,4,1}, 1));
} assertEquals(3, ArrayAlgorithms.indexOf(new int{1,2,1,4,1}, 4)); @Test
public void testNextIndexOf(){
assertEquals(-1, ArrayAlgorithms.nextIndexOf(null, 0, 0)); //test
with a null array
assertEquals(-1, ArrayAlgorithms.nextIndexOf(new int[0], 0, 0));
assertEquals(-1, ArrayAlgorithms.nextIndexOf(new int{1,2,1,4,1},
5, 10));
try{
assertEquals(4, ArrayAlgorithms.nextIndexOf(new int
{1,2,1,4,1}, 1, -10));
fail(&quot;Expected an IllegalArgumentException&quot;);
} catch(IllegalArgumentException ex){
}
assertEquals(0, ArrayAlgorithms.nextIndexOf(new int{1,2,1,4,1}, 1, 0)); assertEquals(4, ArrayAlgorithms.nextIndexOf(new int{1,2,1,4,1}, 1, 3));
} @Test
public void testReplaceAll(){ } int data = new int{1,2,1,4,1};
ArrayAlgorithms.replaceAll(data, 1, 5);
assertArrayEquals(new int{5,2,5,4,5}, data); @Test
public void testSwap(){
int data = new int{1,2,3,4,5};
ArrayAlgorithms.swap(data, 0, 4);
assertArrayEquals(new int{5,2,3,4,1}, data);
//ArrayAlgorithms.swap(null, 0, 4);
}
}