A GPL C library of sorting algorithms found on Wikipedia and a sorting algorithm visualizer.
These tables list the implemented sorting algorithms and provide their time complexities and links to their corresponding Wikipedia pages.
When two cases have the same time complexity, this is indicated with =[case].
| Name | Worst | Average | Best |
|---|---|---|---|
| Bubble sort | =Average | O(n^2) | O(n) |
| Quicksort | O(n^2) | O(nlogn) | O(n)/O(nlogn) |
| Odd-even sort | =Average | O(n^2) | O(n) |
| Comb sort | O(n^2) | Θ(nlogn) | Ω(n^2/2^p) where p is the number of increments |
| Cocktail sort | =Average | O(n^2) | O(n) |
| Gnome sort | =Average | O(n^2) | Ω(n) |
| Stooge sort | =Best | =Best | O(n^log3/log1.5) = O(n^2.7095) |
| Slowsort | =Best | =Best | Ω(n^(logn / (2 + ε))) for ε > 0 |
| Bogosort | Unbounded (random), =Average (deterministic) | O((n + 1)!) | O(n) |
| Name | Worst | Average | Best |
|---|---|---|---|
| Selection sort | =Best | =Best | O(n^2) comparisons, O(n) swaps |
| Cycle sort | =Best | =Best | Θ(n^2) |
| Heapsort | =Average | O(nlogn) | O(nlogn) (distinct keys); O(n) (equal keys) |
| Cartesian Tree Sort | O(nlogk) | O(nlogn) | O(n) |
| Name | Worst | Average | Best |
|---|---|---|---|
| Insertion sort | =Average | O(n^2) comparisons and swaps | O(n) comparisons, O(1) swaps |
| Shellsort | O(n^2) worst known gaps, O(nlog^2n) best known gaps | depends on gaps | O(nlogn) |
| Patience Sorting | =Average | O(nlogn) | O(n) |
| Tree sort | O(n^2) | =Best | O(nlogn) |
| Splaysort | =Average | O(nlogn) | O(n) |
| Name | Worst | Average | Best |
|---|---|---|---|
| Merge sort | =Average | O(nlogn) | O(n)/O(nlogn) |
| Name | Worst | Average | Best |
|---|---|---|---|
| Radix sort | =Best | =Best | O(wn) |
| Counting sort | =Best | =Best | O(n + k) |
| Bucket sort | O(nlogn) | Θ(n + k) | Ω(n + k) |
| Pigeonhole sort | =Best | =Best | O(n + k) |
| Name | Worst | Average | Best |
|---|
| Name | Worst | Average | Best |
|---|---|---|---|
| Introsort | =Best | =Best | O(nlogn) |
| Timsort | =Average | O(nlogn) | O(n) |
| Name | Worst | Average | Best |
|---|---|---|---|
| Pancake sorting | =Average | O(n^2) | O(n) |
A void pointer can't be dereferenced in C and the language doesn't allow arrays to contain arbitrary information. Instead, this implementation circumvents the problem by making it the responsibility of the caller to specify the relevant data type sizes. Arrays are stored as void**. A custom advancing function (void** adv(void**, int)) is used to access memory locations at any arbitrary distance from the beginning of the given memory location. Element comparison is delegated to a separate function, indicated with a function pointer. This can either be a predefined one from the library or it can be defined in the calling program. Together, these techniques mean that the memory is never accessed directly by the library, so no type information needs to be stored or specified, allowing arrays of any type to be sorted.
In the data folder in the repository's root, there are programs and spreadsheets that generate and contain data regarding the runtimes of sorting algorithms, respectively. This information is available for use under CC BY-NC-SA 4.0. The source code of those programs is still available under GPLv3. If you would like to have data regarding the runtime of sorting algorithms under your own terms, you may compile the test programs using the included Makefile and generate your own data.
Use the included Makefiles to compile the WikiSort library and the test programs. When compiling the library, you can define the variables _32BITMODE and VISUALIZER to enable 32 bit mode and visualization function calls, respectively. In 32 bit mode, pointers are advanced using uint32_t instead of uint64_t.
In src/wikisort.h, there are type definitions for function pointers that are called when swapping elements or advancing pointers. These are only compiled when visualizer mode is enabled. When creating a sorting algorithm visualizer or other program that needs to be notified when elements in a list are swapped, define VISUALIZER when calling make to enable these features. During linking, appropriate functions must be defined and set.
Refer to examples/random.c for an example of how this might be used.
The repository also includes a visualizer for the sorting algorithms. The visualizer uses ImGui for its interface. The visualizer output can also be recorded to video files (MPEG, .mpg) using the OpenGL recorder library available under GPLv3. A Makefile to compile the visualizer is included in the folder; the submodules must also be cloned before compilation.
Project available under GPLv3. See LICENSE for full license text. ImGui is available under the MIT license.
Text obtained from Wikipedia (algorithm time complexities) available under Creative Commons Attribution-ShareAlike 3.0 license.