Skip to content
Implementation of some of comparison based sorting algorithms
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
data
demo
inc
src Change CMake command to run tests Nov 28, 2018
test
.clang-format
.gitattributes
.gitignore
LICENSE.md
README.md

README.md

GitHub forks GitHub stars

Sort

Some of comparision based sorting algorithms implemented in generic form using C

Usage

You can use any of these implementation by including to the source. Most of algorithms implemented std qsort() fashion void qsort( void *ptr, size_t count, size_t size, int (*cmp)(const void *, const void *) )

If you want to use insertion sort for example, you should try

void insertionSort( void *ptr, size_t count, size_t size, int (*cmp)(const void *, const void *) )

where

  • ptr is pointer to array
  • count is number of elements in the array
  • size is size of every single element of the array
  • cmp is comparision function, an function pointer that takes two const pointer to void and return an integer -1, +1, 0 similar to strcmp

To see empirical implementation correctness tests, go to test/ directory and run following commands:

$ mkdir build && cd build
$ cmake ..
$ cmake --build .

Sort Worst Case Average Case Best Case
Bogo O((n+1)!) O((n+1)!) O(n)
Bubble O(n2) O(n2) O(n)
Cocktail Shaker O(n2) O(n2) O(n)
Selection O(n2) O(n2) O(n2)
Gnome O(n2) O(n2) O(n2)
Comb O(n2) O(nlogn) O(nlogn)
Insertion O(n2) O(n2) O(n)
Shell O(n(log(n))2) O(n(log(n))2) O(nlogn)
Merge Sort O(nlogn) O(nlogn) O(nlogn)
Quick Sort O(n2) O(nlogn) O(nlogn)
Heap Sort O(nlogn) O(nlogn) O(nlogn)
You can’t perform that action at this time.