Midterm Flashcards
Summarize Selection Sort
Best Case: (1/2)N^2
Average Case: (1/2)N^2
Worst Case: (1/2)N^2
Stability: No
In-Place: Yes
Improvement: None
Summarize Insertion Sort
Best Case: N
Average Case: (1/4)N^2
Worst Case: (1/2)N^2
Stability: Yes
In-Place: Yes
Improvement: Move Large Entries to the right one space rather than doing full exchanges
Advantage: Good for small arrays
Summarize Shell Sort
Best Case: Nlog_3(N)
Average Case: N/A
Worst Case: cN^(3/2)
Stability: No
In-Place: Yes
Improvement: N/A
Advantage: Good for very large arrays
Summarize Merge Sort
Best Case: (1/2)Nlog(N)
Average Case: Nlog(N)
Worst Case: Nlog(N)
Stability: Yes
In-Place: No
Improvement: Insertion Sort for Small Subarrays
Summarize Quick Sort
Best Case: Nlog(N)
Average Case: Nlog(N)
Worst Case: N^2
Stability: Yes
In-Place: Yes
Improvement: Cutoff to Insertion
How do you determine the time complexity relationship between two functions f and g?
take the limit of (f(n)/g(n)) as n goes to infinity. Let’s say that value is L
If L = 0 then f is in O(g(n)) if L = c where c is some constant then
f is in Theta(g(n)) if L = inf then f is in Omega(g(n))
What is the definition of O(g(n))?
O(g(n)) implies that there are positive constants m and n_0 for which
0 <= f(n) <= m*g(n) for n >= n_0
How do you implement a stack?
Page 148
How do you implement a queue?
Page 150
How do you implement a bag?
Page 154
How do you make something iterable?
Page 154
How do you implement selection sort?
Page 248
How do you trace selection sort?
Page 249
How do you implement insertion sort?
Page 250
How do you trace insertion sort?
Page 251
How do you implement shell sort?
Page 258
How do you trace shell sort?
Page 256
How do you implement top down merge?
Page 270, 274
How do you trace top down merge?
Page 273
How do you implement a bottom up merge?
Page 270, 277
How do you trace a bottom up merge?
Page 278
How do you implement quick sort?
Page 288, 290
How do you trace quick sort?
Page 291
What is the time complexity of union-find cases for n nodes?
Quick Find:
Constructor: n
Union: n
Find: 1
Quick Union:
Constructor: n
Union: Tree Height
Find: Tree Height
Weighted Quick Union:
Constructor: n
Union: log(n)
Find: log(n)
