Linear/Sequential Search
A linear/sequential search algorithm looks at each element in the array until it finds what it's looking for. This is easy to do with a for loop.
Binary Search
A binary search algorithm only works for a sorted array of elements. The first element is "min", the last element is "max", and the element right in the middle is "mid". If the element you're searching for is above "mid", then mid+1 becomes the new "min". Or, if the element you're searching for is lower than mid, then mid-1 becomes the new "max". This continues until the value of the element you're searching for becomes mid, and the position of mid is returned. Or, if the element doesn't exist in the array, "min" becomes higher than "max", and -1 is returned.
Binary search is a lot more efficient than linear search, because the algorithm is able to continuously cut out half the elements in the array.
TMM26
Sorting Algorithms
Selection Sort
The selection sort algorithm orders array elements by finding the smallest element in the array. This element is exchanged with the first element in the array. Next, the algorithm finds the second smallest element in the array, and exchanges it with the second element. This continues until the array is sorted.
Insertion Sort
The insertion sort algorithm begins at the first element and considers it sorted. Then, the algorithm looks at the second element and compares it to the first. The second element is placed where it needs to be in relation to the first element. Now, the first two elements are sorted. The algorithm will look at the third element and compare it to the two sorted elements and place it where it needs to be. Now, the first three elements are sorted. This process continues until the array is sorted.
Merge Sort
The merge sort algorithm halves the array until the array is broken up into individual elements. The merge sort algorithm does this using recursion (the sort algorithm keeps calling itself). Once the elements are individualized, adjacent elements are merged together and sorted simultaneously. (they're merged back into groups of 2, then those groups of 2 are merged into 4, then 8, and so on). This continues until there is only 1 sorted group with all the elements.
The sorting algorithms here are listed from least efficient to most efficient (selection < insertion < merge), especially when working with large arrays.
The selection sort algorithm orders array elements by finding the smallest element in the array. This element is exchanged with the first element in the array. Next, the algorithm finds the second smallest element in the array, and exchanges it with the second element. This continues until the array is sorted.
Insertion Sort
The insertion sort algorithm begins at the first element and considers it sorted. Then, the algorithm looks at the second element and compares it to the first. The second element is placed where it needs to be in relation to the first element. Now, the first two elements are sorted. The algorithm will look at the third element and compare it to the two sorted elements and place it where it needs to be. Now, the first three elements are sorted. This process continues until the array is sorted.
Merge Sort
The merge sort algorithm halves the array until the array is broken up into individual elements. The merge sort algorithm does this using recursion (the sort algorithm keeps calling itself). Once the elements are individualized, adjacent elements are merged together and sorted simultaneously. (they're merged back into groups of 2, then those groups of 2 are merged into 4, then 8, and so on). This continues until there is only 1 sorted group with all the elements.
The sorting algorithms here are listed from least efficient to most efficient (selection < insertion < merge), especially when working with large arrays.
Recursion
A recursive function is one that calls itself in the method body.
A recursive function breaks down a problem into smaller iterative pieces. The function keeps iterating and calling itself until it reaches the "base case", or the simplest case. At this point, the function "winds back" to the first call.
A helpful method for tracing a recursive function is to write down each method call in a "staircase" formation. Once you reach the base case, start moving back up the staircase, figuring out what each method call returns until you get to the first method call.
A recursive function breaks down a problem into smaller iterative pieces. The function keeps iterating and calling itself until it reaches the "base case", or the simplest case. At this point, the function "winds back" to the first call.
A helpful method for tracing a recursive function is to write down each method call in a "staircase" formation. Once you reach the base case, start moving back up the staircase, figuring out what each method call returns until you get to the first method call.
ArrayLists
ArrayLists store a variable number of objects. The size of an ArrayList is not fixed.
We've got 6 methods of the ArrayList class:
We've got 6 methods of the ArrayList class:
- myArrayList.size() returns the number of elements in the arraylist
- myArrayList.add(e) adds an element e to the end of the arraylist
- myArrayList.add(int loc, e) adds an element e to the arraylist at position loc and will move all following elements down one position
- myArrayList.get(int loc) returns the element at position loc
- myArrayList.set(int loc, e) replaces the element at position loc with a new element e
- myArrayList.remove(loc) removes the element at position loc
To create an ArrayList:
ArrayList<Integer> myIntegers = new ArrayList<Integer>();
ArrayList<Double> myDoubles = new ArrayList<Double>();
ArrayList<String> words = new ArrayList<Double>();
ArrayList<Tree> myTrees = new ArrayList<Tree>();
Specify what kind of ArrayList by using < >. Inside the triangle brackets, write what type of objects are in the ArrayList. Note, for int and double variables, you must use Integer or Double objects, since the elements of an ArrayList must be objects.
As with arrays, for loops are used with arraylists a lot to cycle through each of the elements.
Arrays
Think of arrays as a list of variables or objects.
Here are some examples of constructing an array:
int[] n = new int[3];
double[] d = new double[5];
String[] str = new String[8];
You can also create arrays of objects, like this:
Car[] cars = new Car[50];
The number in the brackets is the length of the array, or how many elements are in the array. This is fixed. The length of the array is the same for the entire program. You can get the array length using .length. Using the above examples, n.length is 3, d.length is 5, and str.length is 8. Note: .length is an instance field, not a method, so don't use parentheses.
An array can only store a certain type of variables. Using the examples above, n can only store int variables, d can only store double variables, str can only store strings, and cars can only store car objects.
To access an element of an array, use [], and place the position inside the brackets (remember position starts counting from 0. So the third car of cars would be cars[2].
For loops are used with arrays a lot, because you can use them to go through each element of an array. For example:
double sum = 0;
for(int i=0; i<d.length; i++){
double x = d[i];
sum += x;
double x = d[i];
sum += x;
// rest of the loop
}
}
We also use for-each loops for arrays. A for each loop does the same thing as the above for loop. It accesses each element in an array from beginning to end.
double sum = 0;
for(double x: d){
for(double x: d){
// for each iteration, the element is assigned to x
sum += x;
// rest of the loop
}
// rest of the loop
}
The for each loop is cool, but you can only use it when you just want to access the elements in an array. Sometimes, you can't use a for each loop and you need to use a regular for loop if you want to, say, change the elements in an array, or if you need to use the position i in the body of the loop, or if you want to access multiple elements of the array at a time.
A two-dimensional array is an array of arrays. For example:
double[][] arr = new double[3][5];
double[][] arr = new double[3][5];
arr is an array of 3 double arrays, and each of those 3 arrays has 5 doubles. This is a matrix. The number in the first bracket is the number of rows, and the number in the second bracket is the number of columns.
arr.length tells us the number of rows. So how do we get the number of columns? Just get the number of columns of one of the rows: arr[0].length. You can use any position, but 0 is simple.
To access an element of a 2-dimensional array, use [i][j]. i is the row of the element, j is the column of the element.
We use nested for loops for 2-dimensional arrays:
for(int i=0; i<arr.length; i++){
for(int i=0; i<arr.length; i++){
for(int j=0; j<arr[0].length; j++){
//body of loop
}
}
Random class
Methods of the Random class:
nextInt() returns a random int
nextInt(int bound) returns a random int from 0 (inclusive) to bound(exclusive)
nextDouble() returns a random double from 0 (inclusive) to 1 (exclusive)
You can change the range of the random values, by adding a constant to the random number, or multiplying the random number by a constant.
nextInt() returns a random int
nextInt(int bound) returns a random int from 0 (inclusive) to bound(exclusive)
nextDouble() returns a random double from 0 (inclusive) to 1 (exclusive)
You can change the range of the random values, by adding a constant to the random number, or multiplying the random number by a constant.
DeMorgan's Law
!(A && B) is the same as !A || !B
!(A || B) is the same as !A && !B
Something cool to think about.
!(A || B) is the same as !A && !B
Something cool to think about.
Subscribe to:
Posts (Atom)
Searching Algorithms
Linear/Sequential Search A linear/sequential search algorithm looks at each element in the array until it finds what it's looking for. ...
-
A recursive function is one that calls itself in the method body. A recursive function breaks down a problem into smaller iterative pieces...
-
Linear/Sequential Search A linear/sequential search algorithm looks at each element in the array until it finds what it's looking for. ...
-
Cohesion - a class is cohesive if it has a single, well-defined purpose. If the class has methods and instance fields that don't exactly...