Merge sort is not an in-place sort, it requires space

Insertion sort is an in-place sort, O(n) if already sort, so good on almost sorted stuff

Heap sort is an in-place sort, "who is where in the heap?" impossible, because it's not a binary search tree. A max-heap is good for job scheduling on a shared computer (highest priority); a min-heap is good for an event-driven simulator (smallest time/key must run first, or future events might got messed up =p) p. 138

Quick sort is an in-place sort, O(n^2) if the stuff is already sorted

why? each iteration will need n times (sort in place), if partition is so bad, we divide the array n times, so n*n, if partition is good, we divide logn time, so n*log n

A hash function is a mathematical function that maps keys to integers.

The result is unique identifier numbers, but they are so large they will quickly

exceed the number of slots in our hash table (denoted by m). We must reduce this

number to an integer between 0 and m−1, by taking the remainder of H(S) mod m

(ideally m is a large prime not too close to 2i − 1) p.101

why?

Collision- chaining (bucket), open addressing (next value), Cuckoo hashing(hash twice)

compare: cryptographic hashing

compare: database index http://en.wikipedia.org/wiki/Index_(database) http://mattfleming.com/node/192

## No comments:

Post a Comment