exam 2

Binary Search

Bubble sort

Selection Sort

Insertion Sort

Merge Sort

Quick Sort

Binary search

Range style: cuts the lists inhalf unitl elemtn is mid

Invariant: all candidates are in L[left: right)

Time: O(log n)

Space: O(log n) recursion

Needs: sorted array

Returns: True/False (contains check)

Bubble sort

• Basic: scan left→right swapping out-of-order neighbors; largest “bubbles” to the end each pass.

• Best Θ(n) (already sorted w/ early exit) • Avg/Worst Θ(n²) • Space O(1)

• Stable: Yes • In-place: Yes • Adaptive: Yes (with early exit)

selection sort

• Basic: repeatedly pick the min/max from the unsorted part and place it at the boundary.

• Best/Avg/Worst Θ(n²) • Space O(1)

• Stable: No • In-place: Yes • Adaptive: No

insertion sort

• Basic: insert each item into the correct spot of the already-sorted left side.

• Best Θ(n) (nearly sorted) • Avg/Worst Θ(n²) • Space O(1)

• Stable: Yes • In-place: Yes • Adaptive: Yes

merge sort

• Basic: split into halves, sort each, then merge two sorted lists.

• Best/Avg/Worst Θ(n log n) • Space O(n)

• Stable: Yes • In-place: No • Adaptive: No

quick sort

• Basic: choose pivot, partition into < and > pivot, recurse on parts.

• Best/Avg Θ(n log n) • Worst Θ(n²) (bad pivots like sorted data) • Space O(log n) stack

• Stable: No • In-place: Yes • Adaptive: No