   EXAMS Education 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. 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. Linear median algorithm. The linear median algorithm, can find the i-st 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 i-st 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.

Data Structures

 BB[a] tree. BB[a] tree is a weighted-balanced 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]. Union Find. 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 weighted-union rule and the path compression technique. So a sequence of n-1 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 node-oriented 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.