Chapter 7 Arrays Flashcards
Declaring Array Variables: (syntax)
datatype[] arrayRefVar;
ex: double[] myList;
Creating Arrays: (syntax)
datatype[] arrayRefVar = new datatype[arraySize];
ex:
double[] myList = new double[10];
myList[0] = the FIRST element in the array
myList[9] = is the last element in the array[10]
The length of an array: (syntax)
Find size using:
arrayRefVar.length
Find last index using:
arrayRefVar.length-1
*An out of bounds error will occur if you attempt to reference elements beyond the bounds of an array
Default values:
When an array is created, its elements are assigned the default value of:
0 for numeric primitive tyoes
‘\u0000’ for char types
false for boolean types
Indexed Variables/using them
The. number in the brackets. Can be used like regular variables.
arrayRefVar[index];
myList[2] = myList[0] + myList[1];
Declaring, creating, and initializing using the shorthand notation
double[] myList = {1.9, 2.9, 3.4, 3.5};
8 Ways of processing arrays
- Initializing arrays with input values
- Printing arrays
- Initializing arrays with random values
- Summing all elements
- Finding the largest element
- Random Shuffling
- Shifting elements
Initializing arrays with input values
Scanner input = new Scanner(System.in);
System.out.print(“Enter “ + myList.length + “ values: “);
for (int i = 0; i < myList.length; i++){
myList[i] = input.nextDouble();
}
Printing arrays
for (int i = 0; i < myList.length; i++){
System.out.print(myList[i] + “ “);
}
or
for-each
for(int i: myList){
System.out.print(i);
}
Initializing arrays with random values:
for (int i = 0; i < myList.length; i++){
myList[i] = Math.random() * 100;
}
Summing all elements
double total = 0;
for (int i = 0; i < myList.length; i++){
total += myList[i];
}
Finding the largest element
double max = myList[0];
for (int i = 1; i < myList.length; i++){
if (myList[i] > max) {
max = myList[i];
}
}
Random shuffling
for (int i=0; i < myList.length - 1; i++){
//generate an index j randomly
int j = (int)(Math.random() * myList.length);
//swap myList[i] with myList[j]
double temp = myList[i];
myList[i] = myList[j];
myList[j] = temp;
}
Shifting elements
double temp = myList[0] // Retain the first element
// Shift elements left
for (int [i] = 1; i < myList.length; i++){
myList[i - 1] = myList[i];
}
// Move the first element to fill the last position
myList[myList.length - 1] = temp;
Enhanced for loop (for each loop)
Display the following code displays all elements in the array myList
*Note you still have to use an index variable if you wish to traverse the array in a different order or change the elements in the array
// The following code displays all elements in the array myList
for (double value: myList){
System.out.println(value);
}
// The syntax is:
for (elementType value: arrayRefVar){
// Process the value
}
Copying arrays:
Duplicating an array or part of an array
list2 = list1;
Copying arrays:
Using a loop
int[] source array = {2,3,1,5,10};
int[] targetArray = new int [sourceArray.length];
for (int i = 0; i < sourceArrays.length; i++)
targetArray[i] = sourceArray[i];
Passing arrays to methods
public static void printArray(int[] array){
for (int i = 0; i < array.length; i++){
System.out.print(array[i] + “ “ );
}
}
// Invoke the method
int[] list = {3,1,2,6,4,2};
printArray(list);
//Invoke the method (anonymous array)
printArray(new int[] {3,1,2,6,4,2});
The array copy Utility Syntax
arraycopy(sourceArray, src_pos, targetArray, tar_pos, length);
Anonymous array syntax
new dataType[] {literal 1, 2, 3, };
Pass by value: Primitive types.
For a parameter of this type the actual value is passed. Changing the value of the local parameter does not affect the value of the variable outside the method.
Pass by value: Array types.
For a parameter of this type the value contains a reference to an array; this reference us passed to the method. Any changes to the array that occur inside the method body will effect the original array that was passed as the argument.
Heap memory
The JVM stores the array in an area of memory called heap, which is used for dynamic memory allocation where blocks of memory are allocated and freed in arbitrary order.
Call stack
Keeps track of method calls. First in last out.
swap method
ex swap(int n1, int n2);
Returning an array from a method
List {1,2,3,4,5,6} becomes
List 2 {6,5,4,3,2,1}
int[] list1 = {1,2,3,4,5}
int[] list2 = reverse(list1);
public static int[] reverse (int[] list){
int[] result = new int[list.length];
for (int i = 0, j = result.length - 1; i < list.length; i++, j++);{
result[j] = list[i];
}
return result;
}
or
int temp;
for( int i = 0; i < arr.length / 2; i++){
temp = arr[i];
arr[i] = arr[arr.length - 1 - i];
arr[arr.length -1 - i] = temp;
}
}
Variable-length arguments
A variable number of arguments of the same type can be passed to a method and treated as an array.
typeName… parameterName
public class searching{
public static void main (String[] args){
printValues(1,2,3,4,5);
}
public static void printValues(int…arr){
for (int x: arr){
System.out.print(x + “ “);
}
System.out.println();
}
}
Searching Arrays:
List the two types
linear search and binary search
Searching arrays:
Describe a method for finding a key in the list, such as whether a certain score is included in the list of scores.
public class linear search {
public static int linearSearch(int[] list, int key){
for (int i = 0; i < list.length; i++)
if (key == list[i])
return i;
return -1;
}
}
Linear Search (Basic search)
The linear search approach compares the key element, key, sequentially with each element in the array list.
This method continues to do so until the key matches an element in the list or the list is exhausted without a match being found.
If a match is made, the linear search returns the index of the element in the array that matches the key, if no match is found, the search returns -1.
/** The method for finding a key in the list */
public static int linearSearch(int[] list, int key) {
for (int i = 0; i < list.length; i++)
if (key == list[i])
return i;
return -1;
}
Binary search
*The elements must already be in ascending order
Narrowing search
The binary search compares the key with the element in the middle of the array
The binary method returns the INDEX of the element in the list that matches the search key if it is contained in the list
Binary Search: if the key is less than the middle element
you only have to search the first half of the array
Binary search: if the key is equal to the middle element
the search ends with a match
Binary search: if the key is greater than the middle element
you only need to search the key in the second element
Use binary search to find the key in the list
public static int binarySearch(int[] list, int key){
int low = 0;
int high - list.length - 1;
while (high >= low){
int mid - (low + high) / 2;
if (key < list[mid])
high - mid - 1;
else if (key == list[mid])
return[mid];
else
low - mid + 1;
}
return -1;
}
Since binary search is frequently used in programming, Java provides several overloaded binarySearch methods for searching a key in an array of int, double, char, short, long, and float in the
java.util.Arrays class.
int[] list = {2, 4, 7, 10, 11, 45, 50, 59, 60, 66, 69, 70, 79};
System.out.println(“Index is “ +
java.util.Arrays.binarySearch(list, 11));
//return is 4
index = java.util.Arrays.binarySearch(agesOfZombies, age);
if (index >= 0){
System.out.println(“The zombie with the age of “ + age +
“ is at index “ + index);
}else{
System.out.print(“No match”);
}
Selection sort definition
Selection sort finds the smallest number in the list and places it in first. Then it finds the smallest number remaining and places it in second, and so on until the list contains only a single number.
Selection sort method
public static void selectionSort(double[] list){
for(int i = 0; i < list.length; i++){
//Find the minimum in the length
double currentmin = list[i];
int currentMinIndex = i;
for (int j = i + 1; j < list.length; j++){
if (currentMin > list[j]){
currentMin = list[j];
currentMinIndex = j;
}
}
// swap list[i] with list[currentMinIndex} if necessary;
if currentMinIndex != i) {
list[currentMinIndex] = list[i];
list[i] = currentMin;
} } }
What is overloading a method
naming two methods with the same name but differentiating by using different parameters
Overloading sort methods for arrays of numbers
double[] numbers = {1.1,2.2,3.3,4.4,5.5};
java.util.Arrays.sort(numbers);
Overloading sort methods for arrays of chars
char[] chars = {‘a’, ‘A’, ‘4’, ‘F’, ‘D’, ‘P’};
java.util.Arrays.sort(chars);
Java 8 multicore for fast sorting
Arrays.parallelSort(list)
The method to return a string representation for the list
Arrays.toString(list)
Processing command line parameters
(Passing in Casper Dracula Frankenstein in terminal as arguments)
In the main method, get the arguments from args[0], args[1], …, args[n], which corresponds to arg0, arg1, …, in the command line
A variable is declared using the syntax:
elementType[] arrayRefVar;
Unlike declarations for primitive data type variables, the declaration of an array variables does what:
the declaration of an array does not allocate any space in memory for the array
Is an array variable a primitive data type?
No. An array variable contains a reference to an array.
You can only assign elements to an array if:
It has already been created.
Create a new array:
dataType[] arrayRefVar = new elementType[arraySize];
An index (arrayRefVar[index]) must be an:
integer or an integer expression
*this is the syntax for representing each element in the array
After an array is created, its size becomes permanent and can be obtained using:
arrayRefVar.length-1
*an out of bounds error will occur if you attempt to reference elements beyond the bounds of an array
Index off by one error
mistaking the first element with index 1 instead of 0
When an array is created, its elements are assigned the default values of:
0 for numeric and primitive data types
‘\u000’ for char types
false for boolean
Java uses short hand notation which is known as the array initializer which combines declaring an array, creating an array, and initializing an array in one statement, using the syntax:
elementType[] arrayRefVar = {value0, value1, …, valuek};
When you pass an array argument to a method, you are actually passing the _______ of the array.
reference.
The called method can modify the elements in the callers original array.
If an array is sorted, _____ search is more efficient than ______ search for finding an element in the array.
binary search is more efficient than linear search for finding an element in a sorted array.
What does the selection sort method do:
Selection sort finds the smallest number in the list and swaps it with the first element.
It then finds the smallest number remaining and swaps it with the first element in the remaining list and so on, until only a single number remains.
