numpy  2.0.0
src/npysort/heapsort.c.src File Reference
#include <stdlib.h>
#include "npy_sort.h"
#include "npysort_common.h"

Defines

#define NPY_NO_DEPRECATED_API   NPY_API_VERSION
#define NOT_USED   NPY_UNUSED(unused)
#define PYA_QS_STACK   100
#define SMALL_QUICKSORT   15
#define SMALL_MERGESORT   20
#define SMALL_STRING   16

Functions

int heapsort_ suff (@type @*start, npy_intp n, void *NOT_USED)
int aheapsort_ suff (@type @*v, npy_intp *tosort, npy_intp n, void *NOT_USED)
int heapsort_ suff (@type @*start, npy_intp n, PyArrayObject *arr)
int aheapsort_ suff (@type @*v, npy_intp *tosort, npy_intp n, PyArrayObject *arr)
int npy_heapsort (void *base, size_t num, size_t size, npy_comparator cmp)

Define Documentation

#define NOT_USED   NPY_UNUSED(unused)
#define NPY_NO_DEPRECATED_API   NPY_API_VERSION
The purpose of this module is to add faster sort functions that are type-specific. This is done by altering the function table for the builtin descriptors.
These sorting functions are copied almost directly from numarray with a few modifications (complex comparisons compare the imaginary part if the real parts are equal, for example), and the names are changed.
The original sorting code is due to Charles R. Harris who wrote it for numarray.
Quick sort is usually the fastest, but the worst case scenario can be slower than the merge and heap sorts. The merge sort requires extra memory and so for large arrays may not be useful.
The merge sort is stable, meaning that equal components are unmoved from their entry versions, so it can be used to implement lexigraphic sorting on multiple keys.
The heap sort is included for completeness.
#define PYA_QS_STACK   100
#define SMALL_MERGESORT   20
#define SMALL_QUICKSORT   15
#define SMALL_STRING   16

Function Documentation

int npy_heapsort ( void *  base,
size_t  num,
size_t  size,
npy_comparator  cmp 
)
end repeat*

* GENERIC SORT **

This sort has almost the same signature as libc qsort and is intended to provide a heapsort for array types that don't have type specific sorts. The difference in the signature is an error return, as it might be the case that a memory allocation fails.

Referenced by PyArray_ArgSort().

int heapsort_ suff ( @type @*  start,
npy_intp  n,
void *  NOT_USED 
)

* NUMERIC SORTS **

begin repeat <blockquote>

TYPE = BOOL, BYTE, UBYTE, SHORT, USHORT, INT, UINT, LONG, ULONG,
LONGLONG, ULONGLONG, HALF, FLOAT, DOUBLE, LONGDOUBLE, CFLOAT, CDOUBLE, CLONGDOUBLE#
suff = bool, byte, ubyte, short, ushort, int, uint, long, ulong,
longlong, ulonglong, half, float, double, longdouble, cfloat, cdouble, clongdouble#
#type = npy_bool, npy_byte, npy_ubyte, npy_short, npy_ushort, npy_int,
npy_uint, npy_long, npy_ulong, npy_longlong, npy_ulonglong, npy_ushort, npy_float, npy_double, npy_longdouble, npy_cfloat, npy_cdouble, npy_clongdouble#

</blockquote>

The array needs to be offset by one for heapsort indexing

References TYPE.

int aheapsort_ suff ( @type @*  v,
npy_intp tosort,
npy_intp  n,
void *  NOT_USED 
)
The arrays need to be offset by one for heapsort indexing

References TYPE.

int heapsort_ suff ( @type @*  start,
npy_intp  n,
PyArrayObject arr 
)
end repeat*

* STRING SORTS **

begin repeat <blockquote> TYPE = STRING, UNICODE# suff = string, unicode# #type = npy_char, npy_ucs4#</blockquote>

References TYPE.

int aheapsort_ suff ( @type @*  v,
npy_intp tosort,
npy_intp  n,
PyArrayObject arr 
)
The array needs to be offset by one for heapsort indexing