Chapter 5 Algorithms Flashcards
how to compare all values in 1D array
double for loop, triangular pattern
for(int i = 1; i < n; i++)
for(int j = 0; j<i; j++)
if(a[i] = a[j])
count++;
Total number of comparisons is 1 + 2 + . . . + (n-1) = n(n-1)/2
Insert in Order //shifts values a[k]. /// . a[n-1] apporpirately into a[k+1}, ...,a[n] and inserts newValue into a[k] so that the ascending order is prserved //precondition: a[0]
void insertInOrder (int[]a, int n, int newValue){
//shift values to the right by one until you find the place to insert:
int k = n;
while( k>0 && a[k-1] > newValue){
a[k] = a[k-1];
k--;
}
a{k] = newValue;
}
Loop invariant
an assertion about the loop that is
(1) relevant to the purpose of hte loop
(2) holds true before and after each iteration through the loop
if you can establish that an assertion is true before the first iteration, and also prove that for any iteration if the assertion is true before that iteration it will remain true after that iteration, then your assertion is a loop invariant.
loop invariant question
Consider the following code segment:
int count = 0; int n = 41; int = 2;
while (k
C.
Think about it. and or read page 101 of Be Prepared
How does sequential search work(in finding the value “target” in the array a in the range [a[0], a[n-1]])?
public int sequentialSearch(int[]a a, int n, int target){
for(int k = 0; k < n; k++){
if(a[k] == target)
return k;
}
return -1;
}
Sequential Search works for any array: the values in the array may be in ramdom order. f an array is sorted (that is, if its elements are arranged in ascending or descending order), then Binary Search is a much more efficient method.
Binary Search
Divide and conquer method for quickly finding a target value in a sorted array. Suppose the array is sorted in ascending order. We take an aelement in the middle (or approximately in the middle) of te array and compare it to the target. If they are equal< we’re done. If the target is grater, we continue the search in the right half of the array; if it’s smaller we continue in the left half;
public int binarySearch(int[]a a, int n, int target){
int left = 0, right = n -1, middle;
while(left < a[middle])
right = middle - 1;// continue search in the left half
else left = middle +1;//continue search in the right half
}
return -1;
Binary SEarch in an array of 2^ k - 1 elements requires at most k iterations.
Book says “binary Saerchi n an array of n elements requires log base 2 of n iterations.
But I say it should be log base 2 of n+1 iterations. I may be wrong I would think that If you have to compare 30 elements it would take 5 iterations (32 = 2^ 5). if you have to compare 32 elements it would take 6 comparisons. In other words Binary Search in an array of n elements ceiling(log(base2, n+1)) iterations. Eg. for 32 elements it would take log base 2 of 33, which equals 5.04, so we round up to 6.
Suppose that two programs, one using Binary Search and the other using Sequential Search, take (on average) the same amount of time to find a random target value in a sorted array of 30 elements. Rougthly how much faster than the sequential Search program will hte Binary search program run on an array of 1000 elemetns?
Binary Search takes 5 iterations for 30 elements (32 = 2^ 5) and 10 iterations for 1000 elements (1024 = 2^ 10). So binary Search iwllrun roughly two times longer on a 1000element array than on a 30 element array. sequential search will run roughly 33 times longer (1000 = 30 * 33). On 1000 elements, Binary Search will be 33/2 = 16.5 times faster.
Sorting, as opposed to searching means
arranging a list of items in ascending or descending order, according to hte avlues of the items or some key that is part of an item
Selection Sort and Insertion Sort are called
quadratic sorts
becaues they use two straihtforward nested loops and hte number of required comparison is approximately proportional to n^ 2.
Linear search
also known as sequential search
Selection Sort
Sort of like a triangular search. It finds the largest of the unsorted elements and puts the largest at the at the top of the unsorted elements via swapping. It then continues to find the largest in the remaining unsorted elements and so on.
You could do the same with minimums.
//array is range a[0], a[n-1]
public void selectionSort(int[]a, int n)
{
int maxpos;
for(int k = n; k >= 2; k--){
maxPos = 0;
for (int i =1; i < k; i++){
if (a[i] > a[maxpos])
maxPos = i;
}
//swap a[maxPos], a[k-1]
int tem = a[maxPos]; a[maxPos] = a,k-s]; a[k-1] = temp;
The total number of comparisons in Selection sort is always
the same.
(n-1) + (n-2) + … + 1 = n(n-1)/2
Insertion Sort
The Insertion Sort works by arranging the first two elements in order; then
placing the third element in its correct position relative to the first two elements; and
continuing that way until all elements have been placed.
After p steps, the first p+1 elements are arranged in order.
package com.java2novice.algos;
public class MyInsertionSort {
public static void main(String[] args) {
int[] input = { 4, 2, 9, 6, 23, 12, 34, 0, 1 };
insertionSort(input);
}
private static void printNumbers(int[] input) {
for (int i = 0; i < input.length; i++) {
System.out.print(input[i] + ", ");
}
System.out.println("\n");
}
public static void insertionSort(int array[]) {
int n = array.length;
for (int j = 1; j < n; j++) {
int key = array[j];
int i = j-1;
while ( (i > -1) && ( array [i] > key ) ) {
array [i+1] = array [i];
i--;
}
array[i+1] = key;
printNumbers(array);
}
}
}
Output:
2, 4, 9, 6, 23, 12, 34, 0, 1,
2, 4, 9, 6, 23, 12, 34, 0, 1,
2, 4, 6, 9, 23, 12, 34, 0, 1,
2, 4, 6, 9, 23, 12, 34, 0, 1,
2, 4, 6, 9, 12, 23, 34, 0, 1,
2, 4, 6, 9, 12, 23, 34, 0, 1,
0, 2, 4, 6, 9, 12, 23, 34, 1,
0, 1, 2, 4, 6, 9, 12, 23, 34,
public static void insersionSort(int[] input){
int key;
for(int i=1;i-1&&(input[j]>key)){
input[j+1]=input[j];
input[j]=key;
j--;
}
}
for(int i=0;i
Worst case for Be Prepared’s implementation of insertion sort (p105) is
average case
best case
when the array is sorted in reverse order
of comparisons = 1 + 2 + … + (n-1) = n(n-1)/2
average case = n(n-1)/4
best case = n-1
Binary Search can also be implemented
recursively
