Yet Another eXchange Tool
0.9.0
|
Non-recursive stack version of Quicksort. More...
#include <stdbool.h>
#include <stddef.h>
#include <stdlib.h>
#include "xt/quicksort.h"
#include "xt/sort_common.h"
#include "core/ppm_xfuncs.h"
#include "xt_quicksort_base.h"
Go to the source code of this file.
Macros | |
#define | SORT_TYPE idxpos_type |
#define | SORT_TYPE_SUFFIX idxpos |
#define | SORT_TYPE_CMP_LT(a, b, ...) ((a).idx < (b).idx || ((a).idx == (b).idx && (a).pos < (b).pos)) |
#define | SORT_TYPE_CMP_LE(a, b, ...) ((a).idx < (b).idx || ((a).idx == (b).idx && (a).pos <= (b).pos)) |
#define | SORT_TYPE_CMP_EQ(a, b, ...) ((a).idx == (b).idx && (a).pos == (b).pos) |
#define | SORT_TYPE int |
#define | SORT_TYPE_SUFFIX int |
#define | SORT_TYPE_CMP_LT(a, b, ...) (a < b) |
#define | SORT_TYPE_CMP_LE(a, b, ...) (a <= b) |
#define | SORT_TYPE_CMP_EQ(a, b, ...) (a == b) |
#define | SORT_TYPE Xt_int |
#define | SORT_TYPE_SUFFIX xt_int_permutation |
#define | SORT_TYPE_CMP_LT(u, v, i, j) ((u) < (v) || (u == v && permutation[(i)] < permutation[(j)])) |
#define | SORT_TYPE_CMP_LE(u, v, i, j) ((u) < (v) || (u == v && permutation[(i)] <= permutation[(j)])) |
#define | SORT_TYPE_CMP_EQ(u, v, i, j) ((u) == (v) && permutation[(i)] == permutation[(j)]) |
#define | XT_SORT_EXTRA_ARGS_DECL , int *restrict permutation |
#define | XT_SORT_EXTRA_ARGS_PASS , permutation |
#define | XT_SORT_EXTRA_ARGS_ADVANCE(adv) permutation += (adv) |
#define | XT_SORT_EXTRA_ARGS_SWAP(i, j) |
#define | SORT_TYPE int |
#define | SORT_TYPE_SUFFIX int_permutation |
#define | SORT_TYPE_CMP_LT(u, v, i, j) ((u) < (v) || (u == v && permutation[(i)] < permutation[(j)])) |
#define | SORT_TYPE_CMP_LE(u, v, i, j) ((u) < (v) || (u == v && permutation[(i)] <= permutation[(j)])) |
#define | SORT_TYPE_CMP_EQ(u, v, i, j) ((u) == (v) && permutation[(i)] == permutation[(j)]) |
#define | XT_SORT_EXTRA_ARGS_DECL , int *restrict permutation |
#define | XT_SORT_EXTRA_ARGS_PASS , permutation |
#define | XT_SORT_EXTRA_ARGS_ADVANCE(adv) permutation += (adv) |
#define | XT_SORT_EXTRA_ARGS_SWAP(i, j) |
Functions | |
void | xt_quicksort_xt_int_permutation (Xt_int *a, size_t n, int *restrict permutation) |
void | xt_quicksort_index (Xt_int *v_idx, int n, int *v_pos, int reset_pos) |
Non-recursive stack version of Quicksort.
based on N. Wirth's Pascal Book, 'Algorithms + Data Structures = Programms'. by Alan Miller ( 19 Jul 1995 )
based on:
http://www.nag.com/nagware/Examples/nur.f90
see also:
Definition in file quicksort.c.
#define SORT_TYPE idxpos_type |
Definition at line 134 of file quicksort.c.
#define SORT_TYPE int |
Definition at line 134 of file quicksort.c.
#define SORT_TYPE Xt_int |
Definition at line 134 of file quicksort.c.
#define SORT_TYPE int |
Definition at line 134 of file quicksort.c.
#define SORT_TYPE_CMP_EQ | ( | a, | |
b, | |||
... | |||
) | ((a).idx == (b).idx && (a).pos == (b).pos) |
Definition at line 138 of file quicksort.c.
#define SORT_TYPE_CMP_EQ | ( | a, | |
b, | |||
... | |||
) | (a == b) |
Definition at line 138 of file quicksort.c.
#define SORT_TYPE_CMP_EQ | ( | u, | |
v, | |||
i, | |||
j | |||
) | ((u) == (v) && permutation[(i)] == permutation[(j)]) |
Definition at line 138 of file quicksort.c.
#define SORT_TYPE_CMP_EQ | ( | u, | |
v, | |||
i, | |||
j | |||
) | ((u) == (v) && permutation[(i)] == permutation[(j)]) |
Definition at line 138 of file quicksort.c.
#define SORT_TYPE_CMP_LE | ( | a, | |
b, | |||
... | |||
) | ((a).idx < (b).idx || ((a).idx == (b).idx && (a).pos <= (b).pos)) |
Definition at line 137 of file quicksort.c.
#define SORT_TYPE_CMP_LE | ( | a, | |
b, | |||
... | |||
) | (a <= b) |
Definition at line 137 of file quicksort.c.
#define SORT_TYPE_CMP_LE | ( | u, | |
v, | |||
i, | |||
j | |||
) | ((u) < (v) || (u == v && permutation[(i)] <= permutation[(j)])) |
Definition at line 137 of file quicksort.c.
#define SORT_TYPE_CMP_LE | ( | u, | |
v, | |||
i, | |||
j | |||
) | ((u) < (v) || (u == v && permutation[(i)] <= permutation[(j)])) |
Definition at line 137 of file quicksort.c.
#define SORT_TYPE_CMP_LT | ( | a, | |
b, | |||
... | |||
) | ((a).idx < (b).idx || ((a).idx == (b).idx && (a).pos < (b).pos)) |
Definition at line 136 of file quicksort.c.
#define SORT_TYPE_CMP_LT | ( | a, | |
b, | |||
... | |||
) | (a < b) |
Definition at line 136 of file quicksort.c.
#define SORT_TYPE_CMP_LT | ( | u, | |
v, | |||
i, | |||
j | |||
) | ((u) < (v) || (u == v && permutation[(i)] < permutation[(j)])) |
Definition at line 136 of file quicksort.c.
#define SORT_TYPE_CMP_LT | ( | u, | |
v, | |||
i, | |||
j | |||
) | ((u) < (v) || (u == v && permutation[(i)] < permutation[(j)])) |
Definition at line 136 of file quicksort.c.
#define SORT_TYPE_SUFFIX idxpos |
Definition at line 135 of file quicksort.c.
#define SORT_TYPE_SUFFIX int |
Definition at line 135 of file quicksort.c.
#define SORT_TYPE_SUFFIX xt_int_permutation |
Definition at line 135 of file quicksort.c.
#define SORT_TYPE_SUFFIX int_permutation |
Definition at line 135 of file quicksort.c.
#define XT_SORT_EXTRA_ARGS_ADVANCE | ( | adv | ) | permutation += (adv) |
Definition at line 141 of file quicksort.c.
#define XT_SORT_EXTRA_ARGS_ADVANCE | ( | adv | ) | permutation += (adv) |
Definition at line 141 of file quicksort.c.
#define XT_SORT_EXTRA_ARGS_DECL , int *restrict permutation |
Definition at line 139 of file quicksort.c.
#define XT_SORT_EXTRA_ARGS_DECL , int *restrict permutation |
Definition at line 139 of file quicksort.c.
#define XT_SORT_EXTRA_ARGS_PASS , permutation |
Definition at line 140 of file quicksort.c.
#define XT_SORT_EXTRA_ARGS_PASS , permutation |
Definition at line 140 of file quicksort.c.
#define XT_SORT_EXTRA_ARGS_SWAP | ( | i, | |
j | |||
) |
Definition at line 142 of file quicksort.c.
#define XT_SORT_EXTRA_ARGS_SWAP | ( | i, | |
j | |||
) |
Definition at line 142 of file quicksort.c.
void xt_quicksort_index | ( | Xt_int * | v_idx, |
int | n, | ||
int * | v_pos, | ||
int | reset_pos | ||
) |
Definition at line 80 of file quicksort.c.
void xt_quicksort_xt_int_permutation | ( | Xt_int * | a, |
size_t | n, | ||
int *restrict | permutation | ||
) |