ap csa - things that i personally might forget/need to memorize

notes: most sources say that there is no need to memorize the CODE for all of these algorithms, but to just know their functionality

selection sort

“search-and-swap” method. Find smallest, swap with arr[l0], second smallest, arr[0], and so on

Number of comparisons does not depend on initial arrangement of elements

insertion sort

checks if one behind is smaller, then swaps if it is (“inserts” itself there)

-wrost case: array is inticially sorted in reverse order

-best case: array is already sorted in increasing order

selection sort

“search-and-swap” method. Find smallest, swap with arr[l0], second smallest, arr[0], and so on

Number of comparisons does not depend on initial arrangement of elements

insertion sort

checks if one behind is smaller, then swaps if it is (“inserts” itself there)

-wrost case: array is inticially sorted in reverse order

-best case: array is already sorted in increasing order

merge sort (ALWAYS recursive)

“divide and conquer”

break into half, merge sort left half, merge sort right half, merge the two subarrays into a sorted array

-major disadvantage: needs a temporary array that is as large as the orriginal array. Could be problem if space is a factor

- Best, worst, and aerage cases have similar run times bc merge sort is not affected by the initila ordering of the elements

quicksort (recursive)

---

if there are at least two elements in the array, partition the array, quick sort the left subarray, and quick sort the right subarray.

---

partition method: splits array into 2 subarrays w/pivot element chosen at random from array (or is just 1st element and placed so that all items to the left of the pivot are less than or equal to the pivot, wheraes those to the right are greater than or equal to it

fastest run time: array should be partitioned into 2 parts of roughly the same size

pivot is the smallest or largest element: 2 subarray is empty, and quicksort will turn into a slow, recurisve version of selection sort and is very inefficient

worstcase: partitioning algorithm repeateldy divides array into pieces of size 1 and n-1

sequential sort

starts at element 1, compares with every other element until key is found or there are no more elements io examine in the list

best case scenario: key is in first ot

worst case: key is in last slot or not in list

average: there will be n/2 comparisons (n is number of elements)

binary search

must be sorted array

split in half, find mid, if key is higher then look at elements after mid

best case: key is found on the first try (middle)

worst case: key is not in array or is at an enpoint of the array

what is it about static methods on the implicit parameter this?

static methods have no implicit parameter this

what is it about parameters and values?

all parameters in Java are passed by value

2 different constructros in same class, amount of parameters

they can have the same number of parameters, as long as they are different object types

which has higher precedence, && or ||?

&&

UMAREAOA

-unary (!, ++, —, etc)

-multiplication

-additive

-relational

-equality (== or !=)

-and

-or

-assignment (+=, -=, etc)

linear search

-basic array traversal

-data does not have to be in order

-loops through entire array (or arraylist) and returns index position if key is found

- if key is not found, returns -1

What happens if s.substring(s.length()) is called?

An empty string is returned, NO EXCEPTION IS THROWN

What happens if a class has no constructor?

Compiler makes default, no argument consuctor, which will look like this:

public class() {

}