Sorting Algorithms and Summation Approximations

These flashcards cover key concepts related to sorting algorithms and summation approximations from the lecture notes.

Summation Approximations

Used to estimate the value of a summation by comparing it to an integral.

Quicksort

A divide and conquer sorting algorithm that partitions an array around a pivot element and recursively sorts subarrays.

Counting Sort

A non-comparison-based sorting algorithm for integers in a limited range.

Bucket Sort

Distributes elements into buckets, sorts each bucket, and concatenates the results.

Radix Sort

Sorts integers by processing individual digits from least to most significant.

Selection (Quickselect)

Selects the k-th smallest element in an array using the partitioning method.

Best Case Runtime of Quicksort

Θ(n log n)

Worst Case Runtime of Quicksort

Θ(n²), occurs with poor pivot choices.

Stable Sort

A sorting algorithm that maintains the relative order of records with equal keys.

In-place Sort

A sorting algorithm that requires only a small amount of additional memory to perform the sort.

Θ(n + k)

Runtime for Counting Sort, where n is the number of elements and k is the range of values.

Unstable Sort

A sorting algorithm that does not guarantee to preserve the order of equal elements.

Theta Notation (Θ)

Mathematical notation to describe the asymptotic behavior of functions.

Mean of Three-Pivot Selection

A strategy to improve pivot selection in Quicksort, reducing the chance of worst-case runtime.

LSD Variant of Radix Sort

Processes digits from least to most significant.

Upper Bound Using Integration

The technique to estimate the upper limit of a summation based on an integral.

Lower Bound Using Integration

The technique to estimate the lower limit of a summation based on an integral.

Median of Medians

A pivot selection strategy that guarantees linear time for Selection in the worst case.