forked from Mirrors/openclonk
132 lines
3.9 KiB
ReStructuredText
132 lines
3.9 KiB
ReStructuredText
------
|
|
sort.h
|
|
------
|
|
|
|
Overview
|
|
--------
|
|
|
|
sort.h is an implementation a ton of sorting algorithms in C with a
|
|
user-defined type, that is defined at include time.
|
|
|
|
This means you don't have to pay the function call overhead of using
|
|
standard library routine.
|
|
|
|
You get the choice of many extra sorting routines as well, including:
|
|
|
|
* Shell sort
|
|
* Binary insertion sort
|
|
* Heap sort
|
|
* Quick sort
|
|
* Merge sort
|
|
* Bubble sort (ugh)
|
|
* Tim sort
|
|
|
|
If you don't know which one to use, you should probably use Tim sort.
|
|
|
|
|
|
Usage
|
|
-----
|
|
|
|
To use this library, you need to do three things:
|
|
|
|
* #define SORT_TYPE to be the type of the elements of the array you
|
|
want to sort.
|
|
* #define SORT_NAME to be a unique name that will be prepended to all
|
|
the routines, i.e., #define SORT_NAME mine would give you routines
|
|
named mine_heap_sort, and so forth.
|
|
* #include "sort.h". Make sure that sort.h is in your include path,
|
|
obviously.
|
|
|
|
Then, enjoy using the sorting routines.
|
|
|
|
See demo.c for example usage.
|
|
|
|
If you are going to use your own custom type, you must redefine
|
|
SORT_CMP(x, y) with your comparison function, so that it returns
|
|
a value less than zero if x < y, equal to zero if x == y, and
|
|
greater than 0 if x > y.
|
|
|
|
The default just uses the builtin <, ==, and > operators:
|
|
|
|
#define SORT_CMP(x, y) ((x) < (y) ? -1 : ((x) == (y) ? 0 : 1))
|
|
|
|
It is often just fine to just subtract the arguments as well (though
|
|
this can cause some stability problems with floating-point types):
|
|
|
|
#define SORT_CMP(x, y) ((x) - (y))
|
|
|
|
Speed of routines
|
|
-----------------
|
|
|
|
The speed of each routine is highly dependent on your computer and the
|
|
structure of your data.
|
|
|
|
If your data has a lot of, like partially sorted sequences, then Tim sort
|
|
will beat the pants off of anything else.
|
|
|
|
In general, Tim sort is probably the best sorting algorithm in this library,
|
|
even for random data.
|
|
|
|
Tim sort is not as good if memory movement is many orders of magnitude more
|
|
expensive than comparisons (like, many more than for normal int and double).
|
|
If so, then quick sort is probably your routine. On the other hand, Tim
|
|
sort does extremely well if the comparison operator is very expensive,
|
|
since it strives hard to minimize comparisons.
|
|
|
|
Here is the output of demo.c, which will give you the timings for a run of
|
|
10,000 things on my old Mac Pro (2006-era 2.66 GHz Xeons, 64-bit) on OS X 10.6:
|
|
|
|
::
|
|
|
|
Running tests
|
|
quick sort time: 740.20 us per iteration
|
|
bubble sort time: 183914.60 us per iteration
|
|
merge sort time: 954.20 us per iteration
|
|
binary insertion sort time: 20472.70 us per iteration
|
|
heap sort time: 994.50 us per iteration
|
|
shell sort time: 1170.30 us per iteration
|
|
tim sort time: 708.50 us per iteration
|
|
|
|
|
|
Author
|
|
------
|
|
Christopher Swenson (chris@caswenson.com)
|
|
|
|
|
|
References
|
|
----------
|
|
|
|
* Wikipedia
|
|
* timsort.txt (under doc/)
|
|
|
|
|
|
License
|
|
-------
|
|
|
|
All code in this repository, unless otherwise specified, is hereby
|
|
licensed under the MIT Public License:
|
|
|
|
Copyright (c) 2010 Christopher Swenson
|
|
|
|
Permission is hereby granted, free of charge, to any person
|
|
obtaining a copy of this software and associated documentation
|
|
files (the "Software"), to deal in the Software without
|
|
restriction, including without limitation the rights to use,
|
|
copy, modify, merge, publish, distribute, sublicense, and/or sell
|
|
copies of the Software, and to permit persons to whom the
|
|
Software is furnished to do so, subject to the following
|
|
conditions:
|
|
|
|
The above copyright notice and this permission notice shall be
|
|
included in all copies or substantial portions of the Software.
|
|
|
|
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
|
|
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
|
|
OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
|
|
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
|
|
HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
|
|
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
|
|
FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
|
|
OTHER DEALINGS IN THE SOFTWARE.
|
|
|