Sorting Algorithms (Module 5) PART 1 Flashcards
What is the process of arranging data in a specific order?
sorting
What is sorting fundamental for?
- efficient data organization
- retrieval
- manipulation
Each sorting algorithm is optimized for and offers trade-offs to which 3 things?
speed, memory usage, complexity
Why might we consider input size when selecting a sorting algorithm?
small datasets can favor simpler algorithms, while larger datasets need more efficient algorithms
Why might we consider time complexity when selecting a sorting algorithm?`
worst and best-case scenarios
What type of sorting maintains the relative order of equal elements?
stable sorting
Why might we consider the nature of input data when selecting a sorting algorithm?
pre-sorted, nearly sorted data, and random data might favor different sorting algorithms
Why might we consider real-time constraints when selecting a sorting algorithm?
real-time systems might prioritize algorithms with predictable performance
Sorting algorithms generally fall into which 2 runtime complexities?
O(n log n) and O(n^2)
What are the two O(n^2) sorting algorithms?
insertion sort and selection sort
What are the two O(n log n) sorting algorithms?
Quick sort and merge sort
Which type of sorting algorithm sorts by swapping elements within the same array?
in-place sorting algorithms
Do in-place sorting algorithms require additional memory for another array?
no!
Does out-of-place require extra memory for the output array?
yes!
What makes a sorting algorithm “stable”?
if the relative order of the identical keys in the input is preserved in the output
When is the stability of a sorting algorithm important?
when entries with identical keys are already ordered
What is the formula for finding pairs of numbers?
(n 2) = n(n-1) / 2
What refers to a pair of elements in a sequence that are out of their desired order?
inversion
Why do the number of inversions matter?
each pair in a random ordering has an equal chance of being inverted or ordered
The number of inversions in a list is an indicator of what?
how far the list is being sorted
A sorted array has how many inversions?
0
A completely reversed list has the ________ number of inversions
maximum
Insertion sort performs better when the number of inversions is _______
small
Which sorting algorithm uses inversions to calculate the number of swaps needed to sort a list?
merge sort
