Skip to content

Algorithms

Definition

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.

Data structures

  • way to store and organize data in order to access or modify it
  • every data structure has its own strengths and limitations

Hard problems

  • 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

Insertion sort

  • 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.

References


Last update: November 23, 2020