apcsa quiz 21-26

this has extra vocab words!! other set w/ only the required words is also available on my profile

quick sort

Chooses arbitrary value from somewhere in list (usually middle value), roughly sorts lists into two left/right sublists (smaller values on left, greater values on right), recursively sorts until a list of one value is obtained

merge sort

Divides list in half until sublists are 1/2  values in length, then calls merge algorithm on small sublists before merging progressively larger sublists

bubble sort

Finds largest item and places it at end of item, removes largest item most recently found from set to be searched, repeats until # of items to be searched is 0

insertion sort

Finds correct insert point and right shifts any values between the start and insertion point

selection sort

Makes comparison between item and smallest/largest item found so far in passage through items, causing swapping to only occur once each for each pass

binary search

Divides a list in half, checks to see if the value in the middle of the list equals the value being searched for, and repeats for the appropriate sublist until the value is found

abstract class

a class in which some or all methods are declared abstract and left without code

polymorphism

Greek for “many shapes” - The principle that the actual type of the object determines the method to be called; The same computation works for objects of many forms and adapts itself to the nature of the objects

inheritance

The process of deriving new classes from existing classes

stub

an incomplete routine which can be called but does not solve anything yet

concrete class

A class where all the methods are fully defined and which has no abstract fields; a program can only create objects out of these classes

interface

a blueprint or design specification, encapsulates only abstract methods and constants -  lists a few methods, giving their names, return types, and argument lists, but does not give any code

order of algorithms

based on the number of steps that it takes to complete a task, used to compare algorithms

superclass

The more general class that forms the basis for inheritance

subclass

The more specialized class that inherits from the superclass

swap

Exchanging two values in a list, takes 3 lines of code and uses a temporary variable

cubic

The number of steps increases as a cube of N

linear

the number of steps is directly proportional to the size of the data set

constant

the size of the data set does not affect the number of steps this type of algorithm takes

recursion

When a method calls itself to solve a simpler version of the problem

instance

a specific realization of any object

early binding

the compiler picks the correct method when translating the program, before the program ever runs, applied w/ overloaded methods

late binding

Correct selection of a method takes place when a program runs, based on principle that the actual type of the object determines the method that runs

merge

Combines two sorted sublists into one completely sorted list

quadratic

the number of steps required to solve a problem increases as a function of the square of N

Big O Notation

Function written with capital O (order), signifying notation of an order of an algorithm

log2N

Involves splitting data in half repeatedly - the number of steps increases as a function of log2N

N\*log2N

Algorithms of this type have a log2N concept that must be applied N times

nondecreasing order

no element is less than the element before it