Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output in a finite amount of time. An algorithm is thus a sequence of computational steps that transform the input into the output.
An algorithm for a computational problem is correct if, for every problem instance provided as input, it halts—finishes its computing in finite time—and outputs the correct solution to the problem instance. A correct algorithm solves the given computational problem.
This book also presents several data structures. A data structure is a way to store and organize data in order to facilitate access and modifications. Using the appropriate data structure or structures is an important part of algorithm design.
To express an algorithm, we will use pseudocode. What separates pseudocode from real code is that in pseudocode, we employ whatever expressive method is most clear and concise to specify a given algorithm.
Another difference between pseudocode and real code is that pseudocode often ignores aspects of software engineering—such as data abstraction, modularity, and error handling—in order to convey the essence of the algorithm more concisely.
Our first algorithm, insertion sort, solves the sorting problem:
Input: A sequence of $n$ numbers $\braket{a_1, a_2, \ldots, a_n}$.
Output: A permutation (reordering) $\braket{a'_1, a'_2, \ldots, a'_n}$ of the input sequence such that:
$$ ⁍ $$
The numbers to be sorted are also known as the keys. When we want to sort numbers, it's often because they are the keys associated with other data, which we call satellite data. Together, a key and satellite data form a record.
<aside>
Insertion-Sort$(A)$
for $i := 2$ to $n$ do $key := A[i]$ $j := i - 1$
while $j > 0$ and $A[j] > key$ do $A[j + 1] := A[j]$ $j := j - 1$ $A[j + 1] := key$
</aside>