click below
click below
Normal Size Small Size show me how
Computer Science 345
Term | Definition |
---|---|
Stable | A sorting algorithm is __________ if it preserves the original relative ordering of records that match on the key value being sorted. |
Internal | An algorithm is __________ if it processes and sorts data entirely within the computer's memory; i.g. all the data it works with fits into memory |
In-place | An algorithm is said to be a(n) __________ algorithm if it does not require additional memory (or very little, i.g. temporary local variables) to operate. |
External | An algorithm is __________ if it processes and sorts data within the computer's external memory; the data may be larger than what can fit into memory. |
Bubble Sort | procedure( A[]:list ){ do{ didSwap = false; for(int i=1; i<=A.length;i++){ if( A[i-1] > A[i]) { swap( A[i-1], A[i] ) didSwap = true; } } } while(didSwap); } |
Optimized bubble sort | procedure( A[]:list ){ n =A.length; do{ didSwap = false; for(int i=1; i<=n-1;i++){ if( A[i-1] > A[i]) { swap( A[i-1], A[i] ) didSwap = true; } } n = n - 1; } while(di |
Graph | A Graph G=(V,E) is described by a set of vertices V, and a set of ordered pairs E, such that |V|≠0 and E is a binary relation on V. |
Path | Sequence of Connected Vertices. |