COT 3400 - Week 1 (Mon): Algorithms & Insertion Sort

Vocabulary flashcards covering core concepts from Day 1: what an algorithm is, insertion sort, the role of the sorted portion, insertion steps, runtime implications, and tracing an algorithm.

Algorithm

A finite, well-defined sequence of steps that, when executed, produces an output and terminates in finite time.

Insertion Sort

A sorting algorithm that builds a sorted prefix by inserting each new element into its correct position within the prefix, using comparisons and swaps as needed.

Sorted portion (sorted prefix)

The portion of the array that has already been arranged in non-decreasing order by the algorithm.

Insertion operation

The step of placing the current element into its correct position within the sorted portion by shifting/swapping elements.

Runtime depends on input order

The amount of time an algorithm takes can vary with how the input is arranged; for insertion sort, best-case occurs with already-sorted input, worst-case with reverse-ordered input.

Trace (algorithm trace)

A step-by-step recording of an algorithm’s execution showing values of variables and decisions to illustrate flow.

Input order effect

The influence of the initial arrangement of input elements on performance; in insertion sort, reverse order increases work compared to sorted order.