Loop invariants Flashcards
(19 cards)
What is the main idea behind selection sort?
Repeatedly find the smallest element and move it to the front of the unsorted portion.
What is the time complexity of selection sort?
O(n²)
What is a loop invariant?
A logical condition that remains true before, during, and after each loop iteration.
Why is a loop invariant useful?
It helps prove the correctness of an algorithm.
What is the loop invariant for selection sort?
At iteration i, the first i elements are sorted and smaller than all remaining elements.
What is the loop invariant for insertion sort?
At iteration i, the first i elements are sorted and the array is a permutation of the original.
What does insertion sort do at each iteration?
Inserts the current element into its correct position among the previously sorted elements.
When is insertion sort most efficient?
When the input array is already or nearly sorted.
What is the best-case time complexity of insertion sort?
O(n)
What is the worst-case time complexity of insertion sort?
O(n²)
What causes the worst-case performance in insertion sort?
If the array is in reverse order — each insertion requires shifting many elements.
How does selection sort find the next element to place?
By scanning the unsorted portion for the minimum value.
Is selection sort stable?
No — it can swap equal elements out of order.
Is insertion sort stable?
Yes — it preserves the order of equal elements.
Why is insertion sort considered simple and intuitive?
It mimics how humans sort items like cards — inserting new items one at a time.
How can you formally prove a sorting algorithm is correct?
By defining and validating a loop invariant.
What does the invariant guarantee at the end of insertion sort?
The entire array is sorted.
Why is selection sort not ideal for large datasets?
Because its O(n²) time complexity scales poorly as n increases.
What is a potential downside of using timing-based measurements for complexity?
Timing is affected by hardware, system load, and other noise — it’s not reliable.
