Array Basics
Default Values:
Unless specific values are given in a {…} list, all the elements are initialized to the default value: 0 for numbers, false for booleans, null for objects.
Note: Remember if you use a method on a null object you will get a null-pointer exception at runtime.
Initializing:
String [] words = new String[3];
words[0] = “APCS”;
words[1] = “is”;
words[2] = “hard”;
OR:
String[] words = {“APCS”, “is” , “hard”};
Passing Arrays to methods:
• As other objects, an array is passed to a method as a reference.
• The elements of the original array are not copied and are accessible in the method’s code.
Returning Arrays from methods:
• As any object, an array can be returned from a method.
• i.e. public double[] getNumbers() //returns an array of double type numbers
Example 1:
public int sumNumbers(int[] numbers)
{
int sum = 0;
for (int i = 0; i < numbers.length; i++)
sum+= numbers[i];
return sum;
}
Example 2:
public boolean[] isBiggerThan5(double[] dubs)
{
boolean[] bigger = new boolean[dubs.length];//same length
for (int i = 0; i < bigger.length; i++)
{
if(dubs[i]>5) bigger[i] = true;
else bigger[i] = false; //false is the default so this is really not needed
}
return bigger;
}
Searching and Sorting Algorithms
Searching: returning the index of a list/array in which a desired object is located.
Sequential Search – start at index 0 and check the elements to see if they are equal to value you are searching for.
public int sequentialSearch(Object [ ] arr, Object value)
{
for (int i = 0; i < arr.length ; i++)
{
if (value.equals(arr [i]))
return i;
}
return -1;
}
Note: could use == instead of .equals if you are using primitive data.
Note: Best case number of comparisons: 1
Worse case number of comparisons: number of elements
Average case number of comparisons: number of elements/2
Binary Search - a “divide and conquer” approach that checks the middle element to determine if it is equal, less, or equal to the value we are searching for. If it is equal it returns that index, if it less than the value we are searching for, we eliminate the values prior to that number and check the values higher than that. A comparable idea is used if it is greater than the value we are searching for.
public int binarySearch (int [ ] arr, int value, int left, int right)
{
if (right < left)
return -1; // Not found
int middle = (left + right) / 2;
if (value == arr [middle] )
return middle;
else if (value < arr[middle])
return binarySearch (arr, value, left, middle - 1);
else // if ( value > arr[middle])
return binarySearch (arr, value, middle + 1, right);
}
Note: A list must be in order for binary search to work.
Note: Sequential search would be faster than binary search if the value is very close to the beginning, but in general binary search is much faster.
Note: an array with n elements, the worst case scenario is log base 2 of n (rounded down).
SORTING:
Sort: means to arrange the elements in ascending or descending order.
Selection Sort-
1. Select the max among the first n elements:
2. Swap it with the n-th element :
3. Decrement n by 1 and repeat from Step 1 (while n > 1)
public void selectionSort (double [ ] arr)
{
for (int n = arr.length-1; n > 0; n--)
{
int maxPos = 0;
for (int k = 1; k <= n; k++)
if (arr [k] > arr [maxPos] )
maxPos = k;
//swap
double temp = arr [maxPos];
arr [maxPos] = arr [n];
arr [n] = temp;
}
}
Note: The total number of comparisons is always (no average, worst, or best case)
(n-1) + (n-2) + ... + 1 = n(n-1) / 2
Searching and Sorting Values (APCS)
Selection Sort (named specifically on standards)
Unit 3 Problem Set:
Create a method largestValue that returns the largest value in an array.
public int largestValue(int[] values)
Create a method called averageValue that accepts an array of floats and returns the average value.
public float averageValue(float[] floats)
Create a method that accepts a 2D array called ticTacToe and returns 1 if “X” wins, -1 if “O” wins, and 0 if the game is a tie
Precondition: board contains 0s (empty cell), 1s (X in the cell), and -1s (O in the cell).
public int ticTacToe(int[][] board)
4. Create a method that accepts a float array and returns the range (max - min).
Precondition: The values in the array are in ascending order.
public float getRange(float[] numbers)
5. Create a method that accepts two boolean arrays (representing an answer sheet and an answer key for a true/false test) and returns the proportion of questions answered correctly
Precondition: answerSheet and key have the same length.
public float getGrade(boolean[] answerSheet, boolean[] key)
6. Use the method provided below to answer questions A, B, and C.
public int search(int[] values, int target)
{
for (int i = 0; i < values.length; i++)
{
if (values[i]==target) return i;
}
return -1;
}
A) How many comparisons would search make in the best case scenario?
B) How many comparisons would search make in the worst case scenario?
C) How many comparisons would search make on average?
7. Use the method provided below to answer questions A, B, and C.
public int search(double[] numbers, double number)
{
int low = 0;
int high = numbers.length - 1;
int mid = (low + high)/2;
while (low <= high)
{
if (numbers[mid]==number) return mid;
else if (numbers[mid] > number) high = mid - 1;
else low = mid + 1;
mid = (low + high)/2;
}
return -1;
}
A) How many comparisons would search make in the best case scenario?
B) How many comparisons would search make in the worst case scenario?
8. Create a code segment that will rotate the following array by 3.
int example = {3,5,7, 2, 1, 9,11,14};
rotated by 3 would be 9, 11, 14, 3, 5, 7, 2, 1
9. Write a method called scramble that accepts a String. You should assign each letter to an element to create a char array consisting of single letters. Then scramble the letters and return a String that is the original String scrambled.
10. Write a program to generate a random playing field for the game Minesweeper. Begin the program by asking what the dimensions of the field should be (max: 10 x 10). Then ask for the number of mines to be placed (error-check to make sure that there are enough spaces for the specified number of mines). Next, randomly place the mines on the field. Then display the field to the screen showing:
X's for squares containing mines
A number corresponding the number of adjacent mines for each box that is adjacent to at least one mine
0’s for squares that are not adjacent to mines
Here is an example for a 5x5 field with 6 mines:
More practice on Unit 3 and related concepts: Work on the Programming Module Part 1 from GADOE
(parts of a class, special case methods, instantiating a class, example: rectangle, Rectangle main method and encapsulation)
Before Unit 4: Read notes on classes and objects on Unit 4