Bryan Bishop
Sept. 12th, 02005

Moderately Useless Notes of Questionable Nature and Intent

Insertion Sort

Google Insertion sort, once these notes are completed.

Required for AP CS exam: Performance is the performance analysis for selection sort. "Performance analysis" (after notes: I assume this is about "performance analysis" of COMPUTATIONAL ALGORITHMS)

The way you do analysis.. you check the for loop first.

for() {
}

bubble sort: has a for loop inside that one (it's a nested for loop)
--> i starts at 0, goes to less than n, and so does the one nested for loop. The swaping goes inside he nested for loop. This is bubble sort.

The way you check effeciency is by using something called Big O notation. This is the order of something. "Big Oh Notation"

Big O notation for bubble sort is n*n. This is because it goes through the number of elements in the array n times, and then go through it again (a total of n times). 

O(n^2) = bubble sort
Big O is performance analysis.

Selection sort? Pick the lowest value and then compare it with the rest, swapping the lowest value with the first most position. Pick smallest value and move it to the first element. Once you go through the array once, you move the starting index. 

Analysis for selection sort?
The first for lop does the outer searching for the smallest value. The inner forloop just checks from which point it has to start. It leaves the parts taht it has already checked (it = inner for loop). The inner forloop starts at n-1, to n-2, n-3, ... until 1. (where n is the size of the array).

n(n+1)/2  ----------> a sequence, see it in mathematics class. 
which goes to
n^2+n/2
-----------> he did not explain how to derive that sequence or series
The order of selection sort is ... . O(n^2) -> You take the variable of the largest value and you put it as the order
Take the largest power and that's the order.