quicksort.c File Reference

#include <stdlib.h>
#include <string.h>
#include "utils_core.h"
#include "quicksort_template.h"
#include "quicksort_template_2.h"

Include dependency graph for quicksort.c:

Go to the source code of this file.

Macros
#define	YAC_QSORT_ARRAY_TYPE   int
#define	YAC_QSORT_INDEX_TYPE   int
#define	YAC_QSORT_NAME   yac_quicksort_index
#define	YAC_QSORT_ARRAY_TYPE   yac_int
#define	YAC_QSORT_INDEX_TYPE   size_t
#define	YAC_QSORT_NAME   yac_quicksort_index_yac_int_size_t
#define	YAC_QSORT_ARRAY_TYPE   yac_int
#define	YAC_QSORT_INDEX_TYPE   yac_int
#define	YAC_QSORT_NAME   yac_quicksort_index_yac_int_yac_int
#define	YAC_QSORT_ARRAY_TYPE   yac_int
#define	YAC_QSORT_INDEX_TYPE   uint64_t
#define	YAC_QSORT_NAME   yac_quicksort_index_yac_int_uint64_t
#define	YAC_QSORT_ARRAY_TYPE   yac_int
#define	YAC_QSORT_INDEX_TYPE   int
#define	YAC_QSORT_NAME   yac_quicksort_index_yac_int_int
#define	YAC_QSORT_ARRAY_TYPE   size_t
#define	YAC_QSORT_INDEX_TYPE   size_t
#define	YAC_QSORT_NAME   yac_quicksort_index_size_t_size_t
#define	YAC_QSORT_ARRAY_TYPE   uint64_t
#define	YAC_QSORT_INDEX_TYPE   size_t
#define	YAC_QSORT_NAME   yac_quicksort_index_uint64_t_size_t
#define	YAC_QSORT_ARRAY_TYPE   int
#define	YAC_QSORT_INDEX_TYPE   size_t
#define	YAC_QSORT_NAME   yac_quicksort_index_int_size_t
#define	YAC_QSORT_ARRAY_TYPE   size_t
#define	YAC_QSORT_INDEX_TYPE   yac_int
#define	YAC_QSORT_NAME   yac_quicksort_index_size_t_yac_int
#define	YAC_QSORT_ARRAY_TYPE   size_t
#define	YAC_QSORT_INDEX_TYPE   int
#define	YAC_QSORT_NAME   yac_quicksort_index_size_t_int
#define	YAC_QSORT_ARRAY_TYPE   size_t
#define	YAC_QSORT_INDEX_TYPE   void*
#define	YAC_QSORT_NAME   yac_quicksort_index_size_t_void_p
#define	YAC_QSORT_ARRAY_TYPE   int
#define	YAC_QSORT_INDEX_TYPE   yac_int
#define	YAC_QSORT_NAME   yac_quicksort_index_int_yac_int
#define	YAC_QSORT_ARRAY_TYPE   int
#define	YAC_QSORT_INDEX_TYPE   double
#define	YAC_QSORT_NAME   yac_quicksort_index_int_double
#define	YAC_QSORT_ARRAY_TYPE_A   size_t
#define	YAC_QSORT_ARRAY_TYPE_B   size_t
#define	YAC_QSORT_ARRAY_TYPE_C   double
#define	YAC_QSORT_NAME   yac_quicksort_index_size_t_size_t_double
#define	YAC_QSORT_ARRAY_TYPE_A   yac_int
#define	YAC_QSORT_ARRAY_TYPE_B   yac_int
#define	YAC_QSORT_ARRAY_TYPE_C   double
#define	YAC_QSORT_NAME   yac_quicksort_index_yac_int_yac_int_double
#define	YAC_QSORT_ARRAY_TYPE_A   yac_int
#define	YAC_QSORT_ARRAY_TYPE_B   yac_int
#define	YAC_QSORT_ARRAY_TYPE_C   size_t
#define	YAC_QSORT_NAME   yac_quicksort_index_yac_int_yac_int_size_t
#define	YAC_QSORT_ARRAY_TYPE_A   int
#define	YAC_QSORT_ARRAY_TYPE_B   size_t
#define	YAC_QSORT_ARRAY_TYPE_C   size_t
#define	YAC_QSORT_NAME   yac_quicksort_index_int_size_t_size_t
#define	YAC_QSORT_ARRAY_TYPE_A   int
#define	YAC_QSORT_ARRAY_TYPE_B   size_t
#define	YAC_QSORT_ARRAY_TYPE_C   yac_int
#define	YAC_QSORT_NAME   yac_quicksort_index_int_size_t_yac_int
#define	MAX_STACK_SIZE   (64)

Functions
void	yac_qsort_index (void *a_, size_t count, size_t size, int(*compare)(void const *, void const *), size_t *idx)

Macro Definition Documentation

MAX_STACK_SIZE

#define MAX_STACK_SIZE   (64)

Definition at line 164 of file quicksort.c.

YAC_QSORT_ARRAY_TYPE [1/13]

#define YAC_QSORT_ARRAY_TYPE   int

Definition at line 10 of file quicksort.c.

YAC_QSORT_ARRAY_TYPE [2/13]

#define YAC_QSORT_ARRAY_TYPE   yac_int

Definition at line 10 of file quicksort.c.

YAC_QSORT_ARRAY_TYPE [3/13]

#define YAC_QSORT_ARRAY_TYPE   yac_int

Definition at line 10 of file quicksort.c.

YAC_QSORT_ARRAY_TYPE [4/13]

#define YAC_QSORT_ARRAY_TYPE   yac_int

Definition at line 10 of file quicksort.c.

YAC_QSORT_ARRAY_TYPE [5/13]

#define YAC_QSORT_ARRAY_TYPE   yac_int

Definition at line 10 of file quicksort.c.

YAC_QSORT_ARRAY_TYPE [6/13]

#define YAC_QSORT_ARRAY_TYPE   size_t

Definition at line 10 of file quicksort.c.

YAC_QSORT_ARRAY_TYPE [7/13]

#define YAC_QSORT_ARRAY_TYPE   uint64_t

Definition at line 10 of file quicksort.c.

YAC_QSORT_ARRAY_TYPE [8/13]

#define YAC_QSORT_ARRAY_TYPE   int

Definition at line 10 of file quicksort.c.

YAC_QSORT_ARRAY_TYPE [9/13]

#define YAC_QSORT_ARRAY_TYPE   size_t

Definition at line 10 of file quicksort.c.

YAC_QSORT_ARRAY_TYPE [10/13]

#define YAC_QSORT_ARRAY_TYPE   size_t

Definition at line 10 of file quicksort.c.

YAC_QSORT_ARRAY_TYPE [11/13]

#define YAC_QSORT_ARRAY_TYPE   size_t

Definition at line 10 of file quicksort.c.

YAC_QSORT_ARRAY_TYPE [12/13]

#define YAC_QSORT_ARRAY_TYPE   int

Definition at line 10 of file quicksort.c.

YAC_QSORT_ARRAY_TYPE [13/13]

#define YAC_QSORT_ARRAY_TYPE   int

Definition at line 10 of file quicksort.c.

YAC_QSORT_ARRAY_TYPE_A [1/5]

#define YAC_QSORT_ARRAY_TYPE_A   size_t

Definition at line 114 of file quicksort.c.

YAC_QSORT_ARRAY_TYPE_A [2/5]

#define YAC_QSORT_ARRAY_TYPE_A   yac_int

Definition at line 114 of file quicksort.c.

YAC_QSORT_ARRAY_TYPE_A [3/5]

#define YAC_QSORT_ARRAY_TYPE_A   yac_int

Definition at line 114 of file quicksort.c.

YAC_QSORT_ARRAY_TYPE_A [4/5]

#define YAC_QSORT_ARRAY_TYPE_A   int

Definition at line 114 of file quicksort.c.

YAC_QSORT_ARRAY_TYPE_A [5/5]

#define YAC_QSORT_ARRAY_TYPE_A   int

Definition at line 114 of file quicksort.c.

YAC_QSORT_ARRAY_TYPE_B [1/5]

#define YAC_QSORT_ARRAY_TYPE_B   size_t

Definition at line 115 of file quicksort.c.

YAC_QSORT_ARRAY_TYPE_B [2/5]

#define YAC_QSORT_ARRAY_TYPE_B   yac_int

Definition at line 115 of file quicksort.c.

YAC_QSORT_ARRAY_TYPE_B [3/5]

#define YAC_QSORT_ARRAY_TYPE_B   yac_int

Definition at line 115 of file quicksort.c.

YAC_QSORT_ARRAY_TYPE_B [4/5]

#define YAC_QSORT_ARRAY_TYPE_B   size_t

Definition at line 115 of file quicksort.c.

YAC_QSORT_ARRAY_TYPE_B [5/5]

#define YAC_QSORT_ARRAY_TYPE_B   size_t

Definition at line 115 of file quicksort.c.

YAC_QSORT_ARRAY_TYPE_C [1/5]

#define YAC_QSORT_ARRAY_TYPE_C   double

Definition at line 116 of file quicksort.c.

YAC_QSORT_ARRAY_TYPE_C [2/5]

#define YAC_QSORT_ARRAY_TYPE_C   double

Definition at line 116 of file quicksort.c.

YAC_QSORT_ARRAY_TYPE_C [3/5]

#define YAC_QSORT_ARRAY_TYPE_C   size_t

Definition at line 116 of file quicksort.c.

YAC_QSORT_ARRAY_TYPE_C [4/5]

#define YAC_QSORT_ARRAY_TYPE_C   size_t

Definition at line 116 of file quicksort.c.

YAC_QSORT_ARRAY_TYPE_C [5/5]

#define YAC_QSORT_ARRAY_TYPE_C   yac_int

Definition at line 116 of file quicksort.c.

YAC_QSORT_INDEX_TYPE [1/13]

#define YAC_QSORT_INDEX_TYPE   int

Definition at line 11 of file quicksort.c.

YAC_QSORT_INDEX_TYPE [2/13]

#define YAC_QSORT_INDEX_TYPE   size_t

Definition at line 11 of file quicksort.c.

YAC_QSORT_INDEX_TYPE [3/13]

#define YAC_QSORT_INDEX_TYPE   yac_int

Definition at line 11 of file quicksort.c.

YAC_QSORT_INDEX_TYPE [4/13]

#define YAC_QSORT_INDEX_TYPE   uint64_t

Definition at line 11 of file quicksort.c.

YAC_QSORT_INDEX_TYPE [5/13]

#define YAC_QSORT_INDEX_TYPE   int

Definition at line 11 of file quicksort.c.

YAC_QSORT_INDEX_TYPE [6/13]

#define YAC_QSORT_INDEX_TYPE   size_t

Definition at line 11 of file quicksort.c.

YAC_QSORT_INDEX_TYPE [7/13]

#define YAC_QSORT_INDEX_TYPE   size_t

Definition at line 11 of file quicksort.c.

YAC_QSORT_INDEX_TYPE [8/13]

#define YAC_QSORT_INDEX_TYPE   size_t

Definition at line 11 of file quicksort.c.

YAC_QSORT_INDEX_TYPE [9/13]

#define YAC_QSORT_INDEX_TYPE   yac_int

Definition at line 11 of file quicksort.c.

YAC_QSORT_INDEX_TYPE [10/13]

#define YAC_QSORT_INDEX_TYPE   int

Definition at line 11 of file quicksort.c.

YAC_QSORT_INDEX_TYPE [11/13]

#define YAC_QSORT_INDEX_TYPE   void*

Definition at line 11 of file quicksort.c.

YAC_QSORT_INDEX_TYPE [12/13]

#define YAC_QSORT_INDEX_TYPE   yac_int

Definition at line 11 of file quicksort.c.

YAC_QSORT_INDEX_TYPE [13/13]

#define YAC_QSORT_INDEX_TYPE   double

Definition at line 11 of file quicksort.c.

YAC_QSORT_NAME [1/18]

#define YAC_QSORT_NAME   yac_quicksort_index

Definition at line 12 of file quicksort.c.

YAC_QSORT_NAME [2/18]

#define YAC_QSORT_NAME   yac_quicksort_index_yac_int_size_t

Definition at line 12 of file quicksort.c.

YAC_QSORT_NAME [3/18]

#define YAC_QSORT_NAME   yac_quicksort_index_yac_int_yac_int

Definition at line 12 of file quicksort.c.

YAC_QSORT_NAME [4/18]

#define YAC_QSORT_NAME   yac_quicksort_index_yac_int_uint64_t

Definition at line 12 of file quicksort.c.

YAC_QSORT_NAME [5/18]

#define YAC_QSORT_NAME   yac_quicksort_index_yac_int_int

Definition at line 12 of file quicksort.c.

YAC_QSORT_NAME [6/18]

#define YAC_QSORT_NAME   yac_quicksort_index_size_t_size_t

Definition at line 12 of file quicksort.c.

YAC_QSORT_NAME [7/18]

#define YAC_QSORT_NAME   yac_quicksort_index_uint64_t_size_t

Definition at line 12 of file quicksort.c.

YAC_QSORT_NAME [8/18]

#define YAC_QSORT_NAME   yac_quicksort_index_int_size_t

Definition at line 12 of file quicksort.c.

YAC_QSORT_NAME [9/18]

#define YAC_QSORT_NAME   yac_quicksort_index_size_t_yac_int

Definition at line 12 of file quicksort.c.

YAC_QSORT_NAME [10/18]

#define YAC_QSORT_NAME   yac_quicksort_index_size_t_int

Definition at line 12 of file quicksort.c.

YAC_QSORT_NAME [11/18]

#define YAC_QSORT_NAME   yac_quicksort_index_size_t_void_p

Definition at line 12 of file quicksort.c.

YAC_QSORT_NAME [12/18]

#define YAC_QSORT_NAME   yac_quicksort_index_int_yac_int

Definition at line 12 of file quicksort.c.

YAC_QSORT_NAME [13/18]

#define YAC_QSORT_NAME   yac_quicksort_index_int_double

Definition at line 12 of file quicksort.c.

YAC_QSORT_NAME [14/18]

#define YAC_QSORT_NAME   yac_quicksort_index_size_t_size_t_double

Definition at line 12 of file quicksort.c.

YAC_QSORT_NAME [15/18]

#define YAC_QSORT_NAME   yac_quicksort_index_yac_int_yac_int_double

Definition at line 12 of file quicksort.c.

YAC_QSORT_NAME [16/18]

#define YAC_QSORT_NAME   yac_quicksort_index_yac_int_yac_int_size_t

Definition at line 12 of file quicksort.c.

YAC_QSORT_NAME [17/18]

#define YAC_QSORT_NAME   yac_quicksort_index_int_size_t_size_t

Definition at line 12 of file quicksort.c.

YAC_QSORT_NAME [18/18]

#define YAC_QSORT_NAME   yac_quicksort_index_int_size_t_yac_int

Definition at line 12 of file quicksort.c.

Function Documentation

yac_qsort_index()

void yac_qsort_index	(	void *	a_,
		size_t	count,
		size_t	size,
		int(*	compare )(void const *, void const *),
		size_t *	idx )

Non-recursive stack version of Quicksort

... from N. Wirth's Pascal Book, 'Algorithms + Data Structures = Programms'. by Alan Miller ( 19 Jul 1995 )

taken from:

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

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

  see also:

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

Parameters

[in,out]	a_	data to be sorted
[in]	count	length of data
[in]	size	size of single data element
[in]	compare	compare routine for data elements
[out]	idx	old index of sorted returned a

Definition at line 185 of file quicksort.c.

Here is the caller graph for this function: