An algorithm is ...
- a well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output.
- a sequence of computational steps that transforms the input into the output.
- a tool for solving a well-specified computational problem
The sorting problem
Input: A sequence of \(n\) numbers \(\langle a_1, a_2,\ldots, a_n \rangle\).
Output: A permutation (reordering) \(\langle a'_1, a'_2,\ldots,a'_n \rangle\) of the input sequence such that \(a'_1 \leq a'_2 \leq \cdots \leq a'_n\).
- sorting is often used as an intermedeate step and thus a fundamental operation in computer science.
- there are a large number of available sorting algorithms
Factors for choosing the right algorithm
- number of items to be sorted
- to which extend the items are already sorted
- possible restrictions on the item values
- computer itself
An algorithm is correct if, for every input instance, it halts with the correct output. A correct algorithms solves the given problem. An incorrect algorithm might not halt on some input instances, or it might halt with an incorrect answer.
You can specify an algorithm in different ways (English, as a computer programm, ..) as long as it meets the only requirement, that the specification provides a precise description of the computational procdure.
- way to store and organize data in order to access or modify it
- every data structure has its own strengths and limitations
- for some problems no efficient solution exists
- problems that fall into this category are called NP-complete
- no one knows whether or not efficient algorithms exist for NP-complete problems
- if there is an efficient algorithm for one, then there is one for all
- efficient algorithm to sort a small amount of elements
- similar to sorting a hand of playing cards
- simple implementation
- most efficient in practice than other simple sorting algorithms
- adaptive: efficient for data sets that are already partially sorted
- stable: does not change the relative order of elements with the same key
- in-place: only requires a constant amount O(1) of additional memory space
Insertion sort iterates over the list. At each iteration, insertion sort removes one element from the list, finds the location where it belongs within the sorted list, and inserts it there. This will be repeated until the end of the list.
At each index it checks the value against the largest value in the sorted list, which is next to it. If larger, it leaves the element in place and moves to the next. If smaller, it will shift all the larger values up to make space, and insert it into the correct position.