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

Defines

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

Functions

int quicksort_ suff (void *start, npy_intp num, void *NOT_USED)
int aquicksort_ suff (void *vv, npy_intp *tosort, npy_intp num, void *NOT_USED)
int npy_quicksort (void *start, npy_intp num, void *varr)
int npy_aquicksort (void *vv, npy_intp *tosort, npy_intp num, void *varr)

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 is O(N^2) so the code switches to the O(NlogN) worst case heapsort if not enough progress is made on the large side of the two quicksort partitions. This improves the worst case while still retaining the speed of quicksort for the common case. This is variant known as introsort.

def introsort(lower, higher, recursion_limit=log2(higher - lower + 1) * 2):

# sort remainder with heapsort if we are not making enough progress # we arbitrarily choose 2 * log(n) as the cutoff point if recursion_limit < 0:

System Message: ERROR/3 (<string>, line 12) Unexpected indentation.

<blockquote> heapsort(lower, higher) return</blockquote>

if lower < higher:

pivot_pos = partition(lower, higher) # recurse into smaller first and leave larger on stack # this limits the required stack space if (pivot_pos - lower > higher - pivot_pos):

System Message: ERROR/3 (<string>, line 20) Unexpected indentation.

<blockquote> quicksort(pivot_pos + 1, higher, recursion_limit - 1) quicksort(lower, pivot_pos, recursion_limit - 1)</blockquote>

System Message: WARNING/2 (<string>, line 22) Block quote ends without a blank line; unexpected unindent.
else:
quicksort(lower, pivot_pos, recursion_limit - 1) quicksort(pivot_pos + 1, higher, recursion_limit - 1)
the below code implements this converted to an iteration and as an additional minor optimization skips the recursion depth checking on the smaller partition as it is always less than half of the remaining data and will thus terminate fast enough
#define PYA_QS_STACK   (NPY_BITSOF_INTP * 2)
pushing largest partition has upper bound of log2(n) space we store two pointers each time
#define SMALL_MERGESORT   20
#define SMALL_QUICKSORT   15
#define SMALL_STRING   16

Function Documentation

int npy_aquicksort ( void *  vv,
npy_intp tosort,
npy_intp  num,
void *  varr 
)
quicksort partition
push largest partition on stack
insertion sort
int npy_quicksort ( void *  start,
npy_intp  num,
void *  varr 
)
end repeat*

* GENERIC SORT **

quicksort partition
Generic comparisons may be buggy, so don't rely on the sentinals to keep the pointers from going out of bounds.
push largest partition on stack
insertion sort
int quicksort_ suff ( void *  start,
npy_intp  num,
void *  varr 
)

* NUMERIC SORTS **

begin repeat <blockquote>

TYPE = BOOL, BYTE, UBYTE, SHORT, USHORT, INT, UINT, LONG, ULONG,
LONGLONG, ULONGLONG, HALF, FLOAT, DOUBLE, LONGDOUBLE, CFLOAT, CDOUBLE, CLONGDOUBLE, DATETIME, TIMEDELTA#
suff = bool, byte, ubyte, short, ushort, int, uint, long, ulong,
longlong, ulonglong, half, float, double, longdouble, cfloat, cdouble, clongdouble, datetime, timedelta#
#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, npy_datetime, npy_timedelta#

</blockquote>

end repeat*

* STRING SORTS **

begin repeat <blockquote> TYPE = STRING, UNICODE# suff = string, unicode# #type = npy_char, npy_ucs4#</blockquote>
quicksort partition
push largest partition on stack
insertion sort
quicksort partition
push largest partition on stack
insertion sort
int aquicksort_ suff ( void *  vv,
npy_intp tosort,
npy_intp  num,
void *  NOT_USED 
)
quicksort partition
push largest partition on stack
insertion sort
quicksort partition
push largest partition on stack
insertion sort

References INTP_SWAP, and TYPE.