Archive for July, 2012

The heap sort algorithm

Introduction The heapsort algorithm is a sorting algorithm which has time complexity O(n log n) and does not need additional space. Merge sort has the same time complexity but usually needs additional space. As opposed to merge sort, the heap sort algorithm is not stable i.e. it might reverse the order of equal elements. The […]

,

Leave a comment

Lattices — Partial order with supremum and infimum

Introduction Types which satisfy the concept of a partial order (i.e. which are descendants of the type PARTIAL_ORDER) have a binary relation “<=” which is reflexive, transitive and antisymmetric, i.e. for every three objects “a”, “b”, and “c” the following conditions are satisfied: reflexive: a<=a transitive: a<=b => b=>c => a=>c antisymmetric: a<=b => b=>a […]

Leave a comment

The insertion sort algorithm

Introduction Insertion sort is one of the simplest sorting algorithms. It is quite efficient for small arrays. Its runtime increases with the square of the number of elements to be sorted. Therefore it should not be used with large data sets. For large data sets algorithms like merge sort or heap sort are far more […]

Leave a comment