Yet Another eXchange Tool 0.11.3
Loading...
Searching...
No Matches
Macros | Functions
quicksort.c File Reference

recursive version of Quicksort More...

#include <stdbool.h>
#include <stddef.h>
#include <stdlib.h>
#include "xt/xt_sort.h"
#include "xt/quicksort.h"
#include "xt/sort_common.h"
#include "core/ppm_xfuncs.h"
#include "xt_quicksort_base.h"
Include dependency graph for quicksort.c:

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
 
#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 *restrict v_idx, int n, int *restrict v_pos, int reset_pos)
 

Detailed Description

recursive version of Quicksort

Author
Jörg Behrens behre.nosp@m.ns@d.nosp@m.krz.d.nosp@m.e Moritz Hanke hanke.nosp@m.@dkr.nosp@m.z.de Thomas Jahns jahns.nosp@m.@dkr.nosp@m.z.de

Definition in file quicksort.c.

Macro Definition Documentation

◆ SORT_TYPE [1/5]

#define SORT_TYPE   idxpos_type

Definition at line 61 of file quicksort.c.

◆ SORT_TYPE [2/5]

#define SORT_TYPE   int

Definition at line 61 of file quicksort.c.

◆ SORT_TYPE [3/5]

#define SORT_TYPE   Xt_int

Definition at line 61 of file quicksort.c.

◆ SORT_TYPE [4/5]

#define SORT_TYPE   Xt_int

Definition at line 61 of file quicksort.c.

◆ SORT_TYPE [5/5]

#define SORT_TYPE   int

Definition at line 61 of file quicksort.c.

◆ SORT_TYPE_CMP_EQ [1/5]

#define SORT_TYPE_CMP_EQ ( a,
b,
... )   ((a).idx == (b).idx && (a).pos == (b).pos)

Definition at line 65 of file quicksort.c.

◆ SORT_TYPE_CMP_EQ [2/5]

#define SORT_TYPE_CMP_EQ ( a,
b,
... )   ((a) == (b))

Definition at line 65 of file quicksort.c.

◆ SORT_TYPE_CMP_EQ [3/5]

#define SORT_TYPE_CMP_EQ ( a,
b,
... )   ((a) == (b))

Definition at line 65 of file quicksort.c.

◆ SORT_TYPE_CMP_EQ [4/5]

#define SORT_TYPE_CMP_EQ ( u,
v,
i,
j )    ((u) == (v) && permutation[(i)] == permutation[(j)])

Definition at line 65 of file quicksort.c.

◆ SORT_TYPE_CMP_EQ [5/5]

#define SORT_TYPE_CMP_EQ ( u,
v,
i,
j )   ((u) == (v) && permutation[(i)] == permutation[(j)])

Definition at line 65 of file quicksort.c.

◆ SORT_TYPE_CMP_LE [1/5]

#define SORT_TYPE_CMP_LE ( a,
b,
... )   ((a).idx < (b).idx || ((a).idx == (b).idx && (a).pos <= (b).pos))

Definition at line 64 of file quicksort.c.

◆ SORT_TYPE_CMP_LE [2/5]

#define SORT_TYPE_CMP_LE ( a,
b,
... )   ((a) <= (b))

Definition at line 64 of file quicksort.c.

◆ SORT_TYPE_CMP_LE [3/5]

#define SORT_TYPE_CMP_LE ( a,
b,
... )   ((a) <= (b))

Definition at line 64 of file quicksort.c.

◆ SORT_TYPE_CMP_LE [4/5]

#define SORT_TYPE_CMP_LE ( u,
v,
i,
j )    ((u) < (v) || ((u) == (v) && permutation[(i)] <= permutation[(j)]))

Definition at line 64 of file quicksort.c.

◆ SORT_TYPE_CMP_LE [5/5]

#define SORT_TYPE_CMP_LE ( u,
v,
i,
j )   ((u) < (v) || (u == v && permutation[(i)] <= permutation[(j)]))

Definition at line 64 of file quicksort.c.

◆ SORT_TYPE_CMP_LT [1/5]

#define SORT_TYPE_CMP_LT ( a,
b,
... )   ((a).idx < (b).idx || ((a).idx == (b).idx && (a).pos < (b).pos))

Definition at line 63 of file quicksort.c.

◆ SORT_TYPE_CMP_LT [2/5]

#define SORT_TYPE_CMP_LT ( a,
b,
... )   ((a) < (b))

Definition at line 63 of file quicksort.c.

◆ SORT_TYPE_CMP_LT [3/5]

#define SORT_TYPE_CMP_LT ( a,
b,
... )   ((a) < (b))

Definition at line 63 of file quicksort.c.

◆ SORT_TYPE_CMP_LT [4/5]

#define SORT_TYPE_CMP_LT ( u,
v,
i,
j )    ((u) < (v) || ((u) == (v) && permutation[(i)] < permutation[(j)]))

Definition at line 63 of file quicksort.c.

◆ SORT_TYPE_CMP_LT [5/5]

#define SORT_TYPE_CMP_LT ( u,
v,
i,
j )   ((u) < (v) || (u == v && permutation[(i)] < permutation[(j)]))

Definition at line 63 of file quicksort.c.

◆ SORT_TYPE_SUFFIX [1/5]

#define SORT_TYPE_SUFFIX   idxpos

Definition at line 62 of file quicksort.c.

◆ SORT_TYPE_SUFFIX [2/5]

#define SORT_TYPE_SUFFIX   int

Definition at line 62 of file quicksort.c.

◆ SORT_TYPE_SUFFIX [3/5]

#define SORT_TYPE_SUFFIX   xt_int

Definition at line 62 of file quicksort.c.

◆ SORT_TYPE_SUFFIX [4/5]

#define SORT_TYPE_SUFFIX   xt_int_permutation

Definition at line 62 of file quicksort.c.

◆ SORT_TYPE_SUFFIX [5/5]

#define SORT_TYPE_SUFFIX   int_permutation

Definition at line 62 of file quicksort.c.

◆ XT_SORT_EXTRA_ARGS_ADVANCE [1/2]

#define XT_SORT_EXTRA_ARGS_ADVANCE ( adv)    permutation += (adv)

Definition at line 125 of file quicksort.c.

◆ XT_SORT_EXTRA_ARGS_ADVANCE [2/2]

#define XT_SORT_EXTRA_ARGS_ADVANCE ( adv)    permutation += (adv)

Definition at line 125 of file quicksort.c.

◆ XT_SORT_EXTRA_ARGS_DECL [1/2]

#define XT_SORT_EXTRA_ARGS_DECL   , int *restrict permutation

Definition at line 123 of file quicksort.c.

◆ XT_SORT_EXTRA_ARGS_DECL [2/2]

#define XT_SORT_EXTRA_ARGS_DECL   , int *restrict permutation

Definition at line 123 of file quicksort.c.

◆ XT_SORT_EXTRA_ARGS_PASS [1/2]

#define XT_SORT_EXTRA_ARGS_PASS   , permutation

Definition at line 124 of file quicksort.c.

◆ XT_SORT_EXTRA_ARGS_PASS [2/2]

#define XT_SORT_EXTRA_ARGS_PASS   , permutation

Definition at line 124 of file quicksort.c.

◆ XT_SORT_EXTRA_ARGS_SWAP [1/2]

#define XT_SORT_EXTRA_ARGS_SWAP ( i,
j )
Value:
do { \
size_t i_ = (size_t)(i), j_ = (size_t)(j); \
int tp = permutation[i_]; \
permutation[i_] = permutation[j_]; \
permutation[j_] = tp; \
} while (0)

Definition at line 126 of file quicksort.c.

◆ XT_SORT_EXTRA_ARGS_SWAP [2/2]

#define XT_SORT_EXTRA_ARGS_SWAP ( i,
j )
Value:
do { \
size_t i_ = (size_t)(i), j_ = (size_t)(j); \
int tp = permutation[i_]; \
permutation[i_] = permutation[j_]; \
permutation[j_] = tp; \
} while (0)

Definition at line 126 of file quicksort.c.

Function Documentation

◆ xt_quicksort_index()

void xt_quicksort_index ( Xt_int *restrict a,
int n,
int *restrict idx,
int reset_index )

quicksort changing values and indices

Parameters
[in,out]aarray to be sorted
[in]nnumber of elements in a and idx
[in,out]idxold index of sorted returned a
[in]reset_indexoverride given idx by identity idx
Examples
test_sort.c.

Definition at line 71 of file quicksort.c.

Here is the call graph for this function:

◆ xt_quicksort_xt_int_permutation()

void xt_quicksort_xt_int_permutation ( Xt_int * a,
size_t n,
int *restrict permutation )
Here is the caller graph for this function: