| A | B |
|---|
| bubble sort | a sort that rearranges elements of an array until they are in either ascending or descending order. Consecutive elements are compared to move the elements to the top or bottom accordingly on each pass |
| selection sort | a sorting algorithm that sorts the components of an array in either ascending or descending order. This process puts the smallest or largest element in the top position and repeats the process on the remaining array components. |
| insertion sort | sorts an array of elements that starts with an empty array and inserts elements one at a time in their proper order |
| best case | The arrangement of data items prior to the start of a sort function to finish in the least amount of time for that particular set of items - minimum number of comparisons required for the algorithm |
| worse case | The arrangement of data items prior to the beginning of the sort procedure which causes that procedure to take the longest amount of time for that particular set of items 0 maximum number of comparisons required for the algorithm |
| order of magnitude | power of ten. Two numbers have the same order of magnitude if their representations in scientific notation have identical exponents to designate the power of ten |
| big-O notation | saying that an algorithm is O(f(n)) indicates that the function f(n) may be useful in characterizing how efficiently the algorithm performs for large n. For such n, we are assured that the operations required by the algorithm will be bounded by the product of a constant and f(n) |
| logarithmic algorithms | an algorithm whose effiency is dominated by a term of the form log n |
| linear algorithms | a polynomial algorithm in which the highest nonzero term is n |
| quadratic algorithms | a polynomial algorithm in which the highest nonzero term in n-squared |
| cubic algorithms | a polynomial algorithm in which the highest nonzero term in n-cubed |
| exponential algorithms | an algorithm whose efficiency is dominated by a term of the form k n. |
| physically sorted | data to be arranged in order within the array being sorted |
| logical order | an ordering of data items according to some defined criterion such as alphabetic, increasing numeric and so forth. That logical order of the data may or may not be the physical order of the data as stored in the computer |
| pointer | a memory location containing the location of another data item |
| pointer sort | a sort in which pointers to the data are manipulated rather than the data themselves |
| data about data | what pointers store |
| time/space trade off | the maxim that an attempt to make a program more efficient in terms of time will only come as a result of a corresponding decrease in efficiency in terms of space, and vice versa |
| radix sort | sorts integer data by repeatedly placing the items into bins and then collecting the bins, starting with the least significant digit for the first pass and finishing with the most significant digit |
| bin sort | radix sort |
| search algorithms | find a particular data item in a large collection of such items |
| sequential search | the process of searching a list by examining the first component and then examining successive components in the ordere in which they occur |
| compiler symbol table | list of identifiers maintained by a compiler as it parses a source program |
| binary search | the process of examining a middle value of a sorted array to see which half contains the value in question and halving until the value is located |
| profiling an algorithm | a means of empirically measuring the execution of an algorighm by inserting counters to keep track of the number of times certain instructions are executed during a run of the program |
| watch object | a monitoring object that measures work in terms of time |
| counter object | measures work simply by counting specific kinds of operations performed by the algorithm |
| paging algorithm | is responsible for bringing into main memory the page the program requests |
| log2n search algorithm | a search algorithm whose efficiency is dominated by a term of the form log2n |
| polynomial algorithjm | an algorithm whose efficiency can be expressed in terms of a polynomial |
| state space | the space of all possible states which can be generated in the solution to a given problem |
| virtual memory | memory divided into pages some stored on disks |
| dominant term | the highest powers of n in a polynomial. For large n, the behavior of the entire polynomial will approach the behavior of a polynomial that contains only that term |
| heuristics | rules of thumb that cut doen on the number of possible choices to examine. They often lead to quick solutions but do not guarantee a solution the way an algorithm does |
| big-O analysis | a technique for estimating the time and space requirements of an algorithm in terms of order of magnitude |
| linear search | sequential search |
