Software Projects - Algorithms in C
I have listed here some generic algorithms I have written in C. A description is given detailing the requirements for the source code to run. They are not the fastest implementation you will find on the web (although I hope they are not too bad either!), but they should be relatively easy to follow, and a good starting point if you wish to develop your own code either in C or another language. At the bottom of the page are some links to external web pages.
The 'algorithm' image was copied from http://www.csie.ntu.edu.tw/~wcchen/ where it is used in the description of Range searching (Multi-key searching). It is not related to any algorithms on these pages, but looked like a cool generic algorithm image.
Quick Sort
Sorts the supplied list of integers in place. The function uses a pointer to the list and the length of the list. The routine is based on the Quick sort method. Basically you place a pointer at each end of the list 'S' and 'E' for start and end, then...
- Take the value at the centre of the list (pivot) for comparisons - this is why its faster if the list is partially sorted.
- Move the lower pointer (S) up until it reaches a value higher than the pivot value.
- Move the upper pointer (E) down until it reaches a value lower than the pivot value.
- Swap the values at S and E and repeat.
- Eventually when S and E meet, all the values higher than the pivot value will be in the upper part of the list, with the lower values in the lower part of the list.
- Then recursively call Quick sort on the lower part of the list and on the upper part.
When all the calls have returned the array will be sorted. This can be very efficient, especially if the list is mostly sorted, as only the minimum number of comparisons are made. However, in some circumstances, such as a list with high values in the middle, Quick sort will take a long time. In general, this is one of the fastest sorting methods.
Interpolated Search
Searches the supplied list of integers, which MUST BE SORTED. The function uses a pointer to the list and the length of the list. The routine starts by checking the length of the list. If it is short a direct comparison of all elements is made until the value is found or not found. If the array is long, a guess is made as to where the element will be by using the values at the start and end of the array and assuming the elements are evenly spread. The guessed element is compared, and if it is too high, the list below the element is searched, otherwise the list above the element is searched.
The computation involved with the estimation can be expensive if the list is small or unevenly distributed. In this case the variable estimated_fraction can be set to 0.5 in order to perform a binary search. If the value to be found is in the list more than once, the index of any of the occurrences may be returned.
Radix-2 FFT
Computes the Fast Fourier Transform of the given complex array and replaces the given array with the result. The data is supplied in two C-style arrays of real and imaginary values, which are of fixed length defined by FFT_LENGTH. This length must be a power of 2 (e.g. 32, 64, 256, 1024 etc). An Inverse FFT is also provided (IFFT).
Sin(x) values are computed once and stored in a lookup table. The function then re-orders the given data so that an efficient in-place Radix-2 transform can be carried out. The first two passes are carried out in separate FOR loops as Omega is either +/-1, 0 or +/-i for multiples of pi/2. The remaining passes are then carried out in the FOR loop at the end of the function.
Links
- The NIST Dictionary of Algorithms, Data Structures, and Problems - for a concise definition of many (if not most) algorithms
- Signal processing algorithms - from http://www.sourceforge.net/
- Mathtools - Download packages to learn about various algorithms
- C 2 HTML - Program used to generate HTML from source code