Transcript Data Structures and Search Algorithms

Data Structures, Search and Sort
Algorithms
Kar-Hai Chu
[email protected]
Data structures
Storage
 Insertion, deletion
 Searching
 Sorting
 Big O

Stacks
LIFO
 Push, pop
 O(1) operations

Linked lists v. Arrays

Linked lists:
– Resizable
– Insertion/deletion

Arrays:
– Faster index
– O(1) lookup
– Preset size
Hash tables
Keys and values
 O(1) lookup
 Hash function

– Good v fast
Clustering
 Databases

Selection sort :-(
O(n2)
 Algorithm:

– Find the minimum value
– Swap with 1st position value
– Repeat with 2nd position down
Insertion sort :-)
O(n2)
 O(1) space
 Great with small number of elements
(becomes relevant later)
 Algorithm:

– Move element from unsorted to sorted list
Bubble sort :-(
O(n2)
 Algorithm:

– Iterate through each n, and sort with n+1
element
Maybe go n-1 steps every iteration?
 Great for big numbers, bad for small
 Totally useless?

Merge sort :-)
O(nlogn)
 Requires O(n) extra space
 Parallelizable
 Algorithm:

– Break list into 2 sublists
– Sort sublist
– Merge
Quick sort :-)
Average O(nlogn), worst O(n2)
 O(n) extra space (can optimized for O(logn))
 Algorithm:

– pick a pivot
– put all x < pivot in less, all x > pivot in more
– Concat and recurse through less, pivot, and more

Advantages also based on caching, registry
(single pivot comparison)
 Variations: use fat pivot
Linear search :-(
O(n)
 Examines every item

Binary search :-)
Requires a sorted list
 O(log n)
 Divide and conquer

Trees
Almost like linked lists!
 Traverse: Pre-order v. Post-order v. Inorder
 Node, edge, sibling/parent/child, leaf

Binary trees
0, 1, or 2 children per node
 Binary Search Tree: a binary tree where
node.left_child < node.value and
node.right_child >= node.value

Balanced binary
trees
Minimizes the level of nodes
 Compared with “bad” binary tree?
 Advantages:

– Lookup, insertion, removal: O(log n)

Disadvantages:
– Overhead to maintain balance
Heaps (binary)
Complete: all leafs are at n or n-1,
toward the left
 Node.value >= child.value
 In binary min/max heap

– Insert = O(logn) .. add to bottom, bubble-up
– deleteMax = O(logn) .. Move last to root
and bubble-down
Heapsort
O(nlogn)
 Algorithm:

– Build a heap
– deleteMax (or Min) repeatedly

O(1) overhead
Why bother?

Tries (say trees)
– Position determines the key
– Great for lots of short words
– Prefix matching

But..
– Long strings..
– Complex algorithms
Chess!


Minimax:
B: B1
B: B2
B: B3
A: A1
+3
-2
+2
A: A2
-1
0
+4
A: A3
-4
-3
+1
Alpha-beta pruning - pick a bag!
– ordering
Useful

http://www.cs.pitt.edu/~kirk/cs1501/anim
ations/Sort3.html