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

studied byStudied by 22 people
1.0(1)
Get a hint
Hint

selection sort

1 / 13

flashcard set

Earn XP

Description and Tags

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

14 Terms

1

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

New cards
2

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

New cards
3

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

New cards
4

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

New cards
5

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)

New cards
6

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

New cards
7

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

static methods have no implicit parameter this

New cards
8

what is it about parameters and values?

all parameters in Java are passed by value

New cards
9

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

New cards
10

which has higher precedence, && or ||?

&&

New cards
11

UMAREAOA

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

-multiplication

-additive

-relational

-equality (== or !=)

-and

-or

-assignment (+=, -=, etc)

New cards
12

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

New cards
13

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

An empty string is returned, NO EXCEPTION IS THROWN

New cards
14

What happens if a class has no constructor?

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

public class() {

}

New cards

Explore top notes

note Note
studied byStudied by 16 people
... ago
5.0(1)
note Note
studied byStudied by 142 people
... ago
5.0(1)
note Note
studied byStudied by 13 people
... ago
5.0(1)
note Note
studied byStudied by 4 people
... ago
5.0(1)
note Note
studied byStudied by 85 people
... ago
5.0(1)
note Note
studied byStudied by 5 people
... ago
5.0(1)
note Note
studied byStudied by 9 people
... ago
5.0(1)
note Note
studied byStudied by 1 person
... ago
5.0(1)

Explore top flashcards

flashcards Flashcard (46)
studied byStudied by 15 people
... ago
5.0(1)
flashcards Flashcard (28)
studied byStudied by 102 people
... ago
4.3(3)
flashcards Flashcard (30)
studied byStudied by 5 people
... ago
5.0(1)
flashcards Flashcard (100)
studied byStudied by 9 people
... ago
5.0(1)
flashcards Flashcard (23)
studied byStudied by 1 person
... ago
5.0(1)
flashcards Flashcard (20)
studied byStudied by 2 people
... ago
5.0(1)
flashcards Flashcard (36)
studied byStudied by 6 people
... ago
5.0(1)
robot