Sorting Algorithms and Summation Approximations

0.0(0)
studied byStudied by 0 people
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
Card Sorting

1/117

flashcard set

Earn XP

Description and Tags

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

Study Analytics
Name
Mastery
Learn
Test
Matching
Spaced

No study sessions yet.

118 Terms

1
New cards

Summation Approximations

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

2
New cards

Quicksort

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

3
New cards

Counting Sort

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

4
New cards

Bucket Sort

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

5
New cards

Radix Sort

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

6
New cards

Selection (Quickselect)

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

7
New cards

Best Case Runtime of Quicksort

Θ(n log n)

8
New cards

Worst Case Runtime of Quicksort

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

9
New cards

Stable Sort

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

10
New cards

In-place Sort

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

11
New cards

Θ(n + k)

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

12
New cards

Unstable Sort

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

13
New cards

Theta Notation (Θ)

Mathematical notation to describe the asymptotic behavior of functions.

14
New cards

Mean of Three-Pivot Selection

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

15
New cards

LSD Variant of Radix Sort

Processes digits from least to most significant.

16
New cards

Upper Bound Using Integration

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

17
New cards

Lower Bound Using Integration

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

18
New cards

Median of Medians

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

19
New cards
20
New cards
21
New cards
22
New cards
23
New cards
24
New cards
25
New cards
26
New cards
27
New cards
28
New cards
29
New cards
30
New cards
31
New cards
32
New cards
33
New cards
34
New cards
35
New cards
36
New cards
37
New cards
38
New cards
39
New cards
40
New cards
41
New cards
42
New cards
43
New cards
44
New cards
45
New cards
46
New cards
47
New cards
48
New cards
49
New cards
50
New cards
51
New cards
52
New cards
53
New cards
54
New cards
55
New cards
56
New cards
57
New cards
58
New cards
59
New cards
60
New cards
61
New cards
62
New cards
63
New cards
64
New cards
65
New cards
66
New cards
67
New cards
68
New cards
69
New cards
70
New cards
71
New cards
72
New cards
73
New cards
74
New cards
75
New cards
76
New cards
77
New cards
78
New cards
79
New cards
80
New cards
81
New cards
82
New cards
83
New cards
84
New cards
85
New cards
86
New cards
87
New cards
88
New cards
89
New cards
90
New cards
91
New cards
92
New cards
93
New cards
94
New cards
95
New cards
96
New cards
97
New cards
98
New cards
99
New cards
100
New cards