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

Functions
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:

• http://www.nag.com/nagware/examples.asp

• http://www.nag.com/nagware/Examples/nur.f90

  see also:

• http://en.wikipedia.org/wiki/Quicksort

Copyright

Copyright (C) 2016 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

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

#define SORT_TYPE   idxpos_type

Definition at line 213 of file quicksort.c.

SORT_TYPE [2/2]

#define SORT_TYPE   int

Definition at line 213 of file quicksort.c.

SORT_TYPE_CMP_EQ [1/2]

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

Definition at line 217 of file quicksort.c.

SORT_TYPE_CMP_EQ [2/2]

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

Definition at line 217 of file quicksort.c.

SORT_TYPE_CMP_LE [1/2]

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

Definition at line 216 of file quicksort.c.

SORT_TYPE_CMP_LE [2/2]

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

Definition at line 216 of file quicksort.c.

SORT_TYPE_CMP_LT [1/2]

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

Definition at line 215 of file quicksort.c.

SORT_TYPE_CMP_LT [2/2]

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

Definition at line 215 of file quicksort.c.

SORT_TYPE_SUFFIX [1/2]

#define SORT_TYPE_SUFFIX   idxpos

Definition at line 214 of file quicksort.c.

SORT_TYPE_SUFFIX [2/2]

#define SORT_TYPE_SUFFIX   int

Definition at line 214 of file quicksort.c.

Function Documentation

xt_quicksort_index()

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

quicksort changing values and indices

Parameters

[in,out]	a	data to be sorted
[in]	n	length of data
[in,out]	idx	old index of sorted returned a
[in]	reset_index	override given idx by identity idx

Examples:

test_sort.c.

Definition at line 77 of file quicksort.c.

Here is the caller graph for this function: