Yet Another eXchange Tool  0.9.0
Macros | Functions
quicksort.c File Reference

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"
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_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)
 

Detailed Description

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:

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/4]

#define SORT_TYPE   idxpos_type

Definition at line 134 of file quicksort.c.

◆ SORT_TYPE [2/4]

#define SORT_TYPE   int

Definition at line 134 of file quicksort.c.

◆ SORT_TYPE [3/4]

#define SORT_TYPE   Xt_int

Definition at line 134 of file quicksort.c.

◆ SORT_TYPE [4/4]

#define SORT_TYPE   int

Definition at line 134 of file quicksort.c.

◆ SORT_TYPE_CMP_EQ [1/4]

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

Definition at line 138 of file quicksort.c.

◆ SORT_TYPE_CMP_EQ [2/4]

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

Definition at line 138 of file quicksort.c.

◆ SORT_TYPE_CMP_EQ [3/4]

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

Definition at line 138 of file quicksort.c.

◆ SORT_TYPE_CMP_EQ [4/4]

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

Definition at line 138 of file quicksort.c.

◆ SORT_TYPE_CMP_LE [1/4]

#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.

◆ SORT_TYPE_CMP_LE [2/4]

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

Definition at line 137 of file quicksort.c.

◆ SORT_TYPE_CMP_LE [3/4]

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

Definition at line 137 of file quicksort.c.

◆ SORT_TYPE_CMP_LE [4/4]

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

Definition at line 137 of file quicksort.c.

◆ SORT_TYPE_CMP_LT [1/4]

#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.

◆ SORT_TYPE_CMP_LT [2/4]

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

Definition at line 136 of file quicksort.c.

◆ SORT_TYPE_CMP_LT [3/4]

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

Definition at line 136 of file quicksort.c.

◆ SORT_TYPE_CMP_LT [4/4]

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

Definition at line 136 of file quicksort.c.

◆ SORT_TYPE_SUFFIX [1/4]

#define SORT_TYPE_SUFFIX   idxpos

Definition at line 135 of file quicksort.c.

◆ SORT_TYPE_SUFFIX [2/4]

#define SORT_TYPE_SUFFIX   int

Definition at line 135 of file quicksort.c.

◆ SORT_TYPE_SUFFIX [3/4]

#define SORT_TYPE_SUFFIX   xt_int_permutation

Definition at line 135 of file quicksort.c.

◆ SORT_TYPE_SUFFIX [4/4]

#define SORT_TYPE_SUFFIX   int_permutation

Definition at line 135 of file quicksort.c.

◆ XT_SORT_EXTRA_ARGS_ADVANCE [1/2]

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

Definition at line 141 of file quicksort.c.

◆ XT_SORT_EXTRA_ARGS_ADVANCE [2/2]

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

Definition at line 141 of file quicksort.c.

◆ XT_SORT_EXTRA_ARGS_DECL [1/2]

#define XT_SORT_EXTRA_ARGS_DECL   , int *restrict permutation

Definition at line 139 of file quicksort.c.

◆ XT_SORT_EXTRA_ARGS_DECL [2/2]

#define XT_SORT_EXTRA_ARGS_DECL   , int *restrict permutation

Definition at line 139 of file quicksort.c.

◆ XT_SORT_EXTRA_ARGS_PASS [1/2]

#define XT_SORT_EXTRA_ARGS_PASS   , permutation

Definition at line 140 of file quicksort.c.

◆ XT_SORT_EXTRA_ARGS_PASS [2/2]

#define XT_SORT_EXTRA_ARGS_PASS   , permutation

Definition at line 140 of file quicksort.c.

◆ XT_SORT_EXTRA_ARGS_SWAP [1/2]

#define XT_SORT_EXTRA_ARGS_SWAP (   i,
 
)
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 142 of file quicksort.c.

◆ XT_SORT_EXTRA_ARGS_SWAP [2/2]

#define XT_SORT_EXTRA_ARGS_SWAP (   i,
 
)
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 142 of file quicksort.c.

Function Documentation

◆ xt_quicksort_index()

void xt_quicksort_index ( Xt_int v_idx,
int  n,
int *  v_pos,
int  reset_pos 
)
Examples
test_sort.c.

Definition at line 80 of file quicksort.c.

Here is the call graph for this function:
Here is the caller 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: