Sorting and searching algorithms
 Quicksort.
 Mergesort.
 Bucketsort.
 Insertionsort.

Implementation in C of the most used sorting algorithms.
Quicksort needs O(nlogn) comparisons in average, and O(n^2) in worst case.
Mergesort needs O(nlogn) (so near optimal).
Bucketsort needs O(nlog(n/k) where k is the bucket size.
Insertionsort needs O(n^2) comparisons.

This is a complete demonstration application which enables you to experiment with the algorithms. You can feed the input either with an input file (numbers separated with ; or [space]), or give input from the keyboard.
The sorted output is writen to out.srt file.
The package includes the following files:
algosort.cpp  The main file (implementation of the algorithms).
algoutil.cpp  A collection of auxiliary functions used by the algorithms.
algorithms.h  Declarations of the functions /structures.
reverse.cpp  A second auxiliary program which reverses the elements of a file (suitable for a worst case input in the algorithms).
algosort.exe  Windows binary.
reverse.exe  Windows binary.
Download Algosort.

 Binary search.
 Interpolation search (with exponential and binary steps).

Implementation in C of the most used searching algorithms.
Binary search needs (worst case) O(log(n)) comparisons.
Interpolation search (with exponential and binary steps) needs O(loglog(n)) in average case and O(log(n)) in worst case.

A complete demonstration application which enables you to experiment with the binary search and interpolation search algorithms. You can give either a sorted list of floating point numbers in a text file, or leave the program automatically generate a list of random numbers. Then using a searching algorithm you can find the position of an item.
The package includes the following files:
algosearch.cpp  The main file (implementation of the algorithms).
algoutil.cpp  A collection of auxiliary functions used by the algorithms.
algorithms.h  Declarations of the functions /structures.
algosearch.exe  Windows binary.
Download Algosearch.


The linear median algorithm, can find the ist smallest element in an array with only O(n) comparisons.

A complete application for the experimentation of the linear median algorithm. You can feed the input either with an input file, or with random elements generated from the program. You also provide the ist element (starting from 1), you want to find. The program responds with the answer.
The package includes the following files:
select.cpp  The main file (implementation of the algorithm).
algoutil.cpp  A collection of auxiliary functions used by the algorithms.
algorithms.h  Declarations of the functions /structures.
select.exe  Windows binary.
Download Select.

Data Structures

BB[a] tree is a weightedbalanced dynamic tree. We use the parameter a in order to adjust the balance of the tree.
The BB[a] tree, is the only tree with the weight quality: A node v needs rebalance only after Ω(Τv) nodes have been inserted or deleted from the subtree Tv.

A nice interactive application which enables you to make operations over a BB[a] tree. You can either set inputs by hand, or let the program insert/ delete nodes at random.
The package includes the following files:
bba.cpp  The main file (implementation of the tree).
algoutil.cpp  A collection of auxiliary functions used by the algorithms.
algorithms.h  Declarations of the functions /structures.
bba.exe  Window binary.
Download BB[a].


The union find problem is to develop a data structure which supports the operations find and unite among a set of sets.
This specific implementation uses the weightedunion rule and the path compression technique. So a sequence of n1 unions and m finds costs O(m*a(m,n)), where a(m,n) is the inverse of Ackermann's function (so it is a function which grows very very slow).

A nice interactive application which enables you to make operations over a universe of sets. You can unite the sets (which initially have size one), or find an element inside a set. Each set is represented with a nodeoriented tree. You can control the operations manually or let the program do some operations at random.
The package includes the following files:
unionfind.cpp  The main file (implementation of the data structure).
algoutil.cpp  A collection of auxiliary functions used by the algorithms.
algorithms.h  Declarations of the functions /structures.
unionfind.exe  Windows binary.
Download UnionFind.
