Sorting Info

Question 1

Bubble Sort: Best, Average, Worst, Stable?, In Place?, Use

Answer 1

Best: O(n)
Average: O(n^2)
Worst: O(n^2)
Stable? Yes
In Place? Yes
Use: Small nearly sorted sets

Question 2

Selection Sort: Best, Average, Worst, Stable?, In Place?, Use

Answer 2

Best: O(n^2)
Average: O(n^2)
Worst: O(n^2)
Stable? No, changes relative order of equal elements
In Place? Yes, doesn’t require extra memory
Use: Small nearly sorted sets

Question 3

Insertion Sort: Best, Average, Worst, Stable?, In Place?, Use

Answer 3

Best: O(n)
Average: O(n^2)
Worst: O(n^2)
Stable? Yes
In Place? Yes
Use: Small nearly sorted sets, timsort

Question 4

Merge Sort: Best, Average, Worst, Stable?, In Place?, Use

Answer 4

Best: O(nlogn)
Average: O(nlogn)
Worst: O(nlogn)
Stable? Yes
In Place? No
Use: large dataset, extra space not a concern

Question 5

Quick Sort: Best, Average, Worst, Stable?, In Place?, Use

Answer 5

Best: O(nlogn)
Average: O(nlogn)
Worst: O(n^2)
Stable? No
In Place? Yes
Use: general purpose, efficient, speed, large dataset. avoid worst case.

Question 6

Stack (FILO) First in Last Out Running Time and Uses

Answer 6

Running Time: O(1)

Undo Redo
Browser Back
Memory

Question 7

Queue (FIFO) First in, first out

Answer 7

Running Time: O(1)

Simulations Traffic/Airport
Print spools
Process/job queue

Question 8

Min max Priotity Queue Running Time and Uses

Answer 8

Running time: O(1)

Process/CPU Schedules
Task List
Ticketing System

Question 9

Ordered Map and Set

Answer 9

Running Time: O(log(n))

Question 10

Unordered map and set

Answer 10

Running Time: O(1)

Question 11

Array/vector Running Time (back, middle, front)

Answer 11

Running Time: O(1) for access and insertion at back
O(n) for insertion and removal elsewhere

Question 12

List

Answer 12

Running Time: O(1) for insertion and removal, but not for random access

Question 13

Stack, queue, priority queue Running Time

Answer 13

O(1) for adding to, removing from, wnd accessing proper ends