notes from lecture

Two point curve for the latest lab section
No curve for other section

fear not! there will be other quizzes

computer concepts
___________________
algorithm - like a recipe

task: take a bunch of nums, in any random order, and make them appear in ascending order
Bubblesort
Selection sort
Insertion sort

As the cardinality of numbers get really big, time to carry it out can get out of control
Analysis of Algorithms


Bubblesort: "Are they in the right order?"
if yes, leave alone. if no, swap
http://en.wikipedia.org/wiki/Bubblesort

How long will Bubblesort take? in worst scenario, best, average?
thinking about worst
we have N numbers we want to sort
how many operations will it take?

O(n^2)
10 x 10 == 100

hertz
kilahertz
megahertz
gigahertz

2.8 gigahertz
that's a lot

1 million numbers

Moore's Law

selection sort: "scan for the smallest number and put it into the correct position"
we do less swaps, but still is O(n^2)
http://en.wikipedia.org/wiki/Selection_sort

understand the animations at Wikipedia

x is pos in array (in the collection)
y is size of the number

check BlackBoard soon for the Excel spreadsheet from class