IT279: Algorithm and Data Structures Recap 2/3

HeapSort

Step1: Heapify O(n)

Step2: n-1 deleteMax operations O(log n) = (n-1) * O(log n)

total: O(n log n)

 

advantages:

Guaranteed O(n log n)

Space cost of n + 1

 

disadvantages:

Higher overhead than other n log n sorts

Not a stable sort

 

ShellSort

avg: O(n(logn)^2)

worst: O(n^2)

inspection gap is reduced at each stage

 

MergeSort

We have two sorted lists of equal length.

The length is n. What is the time required to merge the two lists into a single sorted list? O(n)

number of division : O(log n)

What is the worst-case running time for mergesort? O(n log n)

10  6  3  5  12  20  4  15  2  11  13  1

Merge Sort: break, sort, merge

10 6 3 5 12 20 / 4 15 2 11 13 1

3 5 6 10 12 20 / 1 2 4 11 13 15

(1, 2, 3, 4, 5, 6, 10, 11, 12, 13, 15, 20)

 

Top-Down MergeSort (use more memory)

10 6 3 5 12 20 / 4 15 2 11 13 1

10 6 3 / 5 12 20 / 4 15 2 11 13 1

10 6/ 3 / 5 12 20 / 4 15 2 11 13 1

10 / 6 / 3 / 5 12 20 / 4 15 2 11 13 1

6 10 / 3 / 5 12 20 / 4 15 2 11 13 1

3 6 10 / 5 12 20 / 4 15 2 11 13 1

3 6 10 / 5 12 / 20 / 4 15 2 11 13 1

3 6 10 / 5 12 20 / 4 15 2 11 13 1

3 5 6 10 12 20 / 4 15 2 11 13 1

keep doing merge sort on right side.

 

Bottom-up Mergesort

(6, 10) (3, 5) (12, 20) (4, 15) (2, 11) (1, 13)

(3, 5, 6, 10) (4, 12, 15, 20) (1, 2, 11, 13)

(3, 4, 5, 6, 10, 12, 15, 20) (1, 2, 11, 13)

(1, 2, 3, 4, 5, 6, 10, 11, 12, 13, 15, 20)

 

QuickSort

select pivot

compare i(from left) and j(from right) with the pivot and swap(i stop when bigger than pivot and j will stop when smaller than pivot)

if i and j counters cross each other swap i and pivot. The pivot is in place at the time.

Then we have the left and right partition divided by the pivot.

The next pivot is the rightmost of the left partition (the left side of the previous pivot.)

time complexity: O(n log n)

Very low overhead

Space cost of only n + 1

Worst case: Performance on presorted data & reverse data: n^2

 

Improved QuickSort: if partition length <= the cutoff, insertion sort it

Improved Pivot Selection: Median of 3

sort the first, mid, and last elements and swap the middle element with the next-to-last element(now the pivot)

Performance: guaranteed O(n log n) for sorted or reverse data

- pivot is the middle element

Slight constant increase in time to select the pivot

Sorting time complexity table

Disjoint Sets(Union-Find)

A root is a negative int in Disjoint Sets.

Union:

- locate the root of each tree

- Point the root of the second argument's tree at the root of the first argument's tree

- Union should only be done after confirming that the items are in different sets

- Union by size vs Union by height

 

Path Compression: when we do a find all the elements in the path will point to the root. O(1)

Should not be used with union by height.

if array[index] < 0 

     return index

else

    return find(array[index])

 

 

Graph

representation: Adjacency matrix & Adjacency list

 

topological ordering: queue(we push 0 indegree vertex in the queue) & indegree array

 

Breadth First Search: finding shortest paths in unweighted graphs

- Queue(From, to, Cost)

- Path and Costs Array

 

Dijkstra's algorithm

- Path and Cost Arrays + priority queue(from, to, cost)

- greedy algorithm: smallest path cost

basic(V^2) vs using priority queue((V+E) log v)

 

Prim's algorithm

- Edge and Cost Array + priority queue

Very similar to Dijkstra's using a priority queue

The focus is not on paths but on the cost of the individual edge

Pick a starting vertex

Add edges to our priority queue only if the other vertex is not yet part of our tree.

Stop when everything is in the tree

- or the priority queue is empty - meaning we don't have a connected graph

 

 

Kruskal's algorithm

- Disjoint Set Array + Edge List

Sort the edges of the tree

Start out with a forest of trees - each with one vertex

Until we're down to one tree (or out of edges)

- if the vertices for the next edge in the list are not in the same tree

- Add that edge to the minimum spanning tree

- connect the two trees

 

Use disjoint sets where vertices are the objects in the sets

Use union by size to facilitate recognizing when the tree is complete