General Definitions Flashcards
Binary Search
Searching an array by recursively chopping it in half
Insertion Sort
Inserting element x into the sorted portion of the array 0..x
Selection Sort
Building the sorted portion of the array (0..x) by selecting the smallest element in the unsorted portion (x..L) and placing it at x.
Merge Sort
Recursively dividing the array in half, then (effectively) performing selection sort when “working back up”/rebuilding the array
Quick Sort
Choose an element as pivot (p), move elements less than p to left, elements greater than p to right. Do this recursively.
Radix Sort
Element length must be equal!
Place each element in the array into queue buckets, then pull from buckets to rebuild array. Do this for each character in the element’s “key”/value
Abstract Data Type
Semantic behavior of a data structure
Data Structures
A specific implementation of an ADT
Pre-condition
A statement that must be true before method execution
Caller’s responsibility
Post-condition
A statement that must be true after the method execution
Implementer’s responsibility
Loop invariant
A statement that must always remain true, including during execution
Constant time operation
An operation that does not depend on the input size
e.g. reading/writing memory, math, returns
asymptotic runtime complexity
Number of constant time operations an algorithm performs relative to the input size.
Big O classes
The asymptotic runtime complexity of an algorithm with lower-order terms dropped
e.g. N!, K^N, N^K, N log(N), N, log(N), 1
Recursion
A method that calls itself during execution