BINARY TREES:

struct node
{
string data
node*left, *right;

node(stringd="",node*&=NULL,ode*r=NULL)
	{data=d;
	left=l;
	right=r;}
};

See 1.0

void insert (node*&r, string s)
{
if(r==NULL)
	r=new node(s);
r(r->data<S)
	insert(r->right,s);
else
	insert(r->left,s);
}

- need & percent to make sure the actual value is getting changed
- or else it would just get created and disappear

void print(node*n)
{
if (n==NULL)return;
print(n->left);
cout<<n->data;
print(n->right);
}

- make sure you use recursion for this.
- it goes to left until  it reaches null
- return in void makes function stop
- it will go through the left and print all of that, then go to the right of the left.  
- see 1.1
- function boxes are the shit, use them if you run into problems

bool contains(node*n, string s)
{
if (n==NULL)
	return false;
if(n->data > s)
	return contains(n->left,s)
else if (n->data < s)
	return contains(n->right, s);
else 
	return true;
return false;
}
 
- see 1.2
- if the string is greater or equal, it will go down to the next level to search.  if it is equal to a string, it will skip down to returning true.  if it gets all the way to NULL, then it will return false.  
- sorting algorithm for searching in binary chop is log n.  building might be nlogn?

QUICKSORT:

important: pivot, partitioning

possible places to start:
1) First
2) middle
3)random
4)mid of 3 1st, mid, last (too many calculations)
5) avg of 1st and last ((don't do, you need to go through whole data to compute)
6) last thing 

- these are ways to choose the pivot, or starting point.
- they're better in different circumstances
- so choose middle or random.  
- there's pros and cons of each
- EX: so choose middle or random.
- goal is to make partioning work better. 
- so you've chosen a pivot.
- see 2.0

- you'll have two pointers, p and q.
- you move the pivot to the beginning
- q points to things greater than pivot
- p points to things less than pivot
- if they're not, they swap the two things

- p stops if its pointed to something greater than the pivot, q stops if its pointing to something less than the pivot.
- at this point, the two objects are swapped and p and q still point to the same spot.
- then p is incremented and q is decremented.  
- you keep that shit up until everything is on the correct side of the pivot. 
- then you use recursion and set a new pivot for the two partitions and do it again until its sorted.

- most important: how to pick a pivot, how does partitioning work, and timing.
- timing: n log n

partitioning: goal of partitioning is to get all the data less than pivot to left, all the data greater than pivot to the right.  two pointers, one points at first after pivot, one points at last object.  if p is pointing to something greater you stop, if q points to something greater than pivot, you stop.  then you swap the two objects at these places and keep going.  
pivot:  be able to explain picking a pivot and the pros and cons of picking a certain pivot. (if the data is already partially sorted, etc)
timing: nlog n

Merge: n log n
Binary sort: n log n
Quicksort: n log n

- why do you use quicksort over merge sort?  you don't have to make a copy of the data to sort it, saving memory.  more efficient for an array.  not more efficient for a linked list though.
- use quicksort for arrays, mergesort for linked lists.

TIMING:

1 second to sort 100,000 merge sort.  how long for 1million

100,000 x log(2)100,000
100,000 x 2^17
1.7 million ops per second.
1sec/1.7miiion=K
K=.6 ms/op

1M x log(2)1M=20M x 1sec/1.7M = 10 sec

-in computers, its always base 2.  

1 sec to sort 100 items w 2^n how long for 200?

(K)(2^100)= 1sec
K=1/2^100

2^200/2^100=t
2^100 secs

VECTORS

struct v
{
int * arr;
int size,pos;

v()
{
size=10;
pos=0
arr=new int[size];
}

void add(int n)
{
arr[pos]=n;
post=1;
if(post>=size)
resize();
}

void resize()
{
size*=2;
int * arr2=newint[size];
for(int i=0;i<pos;i+=1)
	{arr2[i]=arr[i];}
	delete[]arr;
	arr=arr2;}

int get(int index)
{
return arr[index];
}

};