Vector sorting algorithms

Collaboration diagram for Vector sorting algorithms:

Functions
void	tpt_bitonic_sort_f32 (f32_t *aOutData, const f32_t *aInData, uint32_t aCount, bool aDir)
	Floating point bitonic sort. More...
void	tpt_bubble_sort_f32 (f32_t *aOutData, const f32_t *aInData, uint32_t aCount, bool aDir)
	Floating point bubble sort. More...
void	tpt_heap_sort_f32 (f32_t *aOutData, const f32_t *aInData, uint32_t aCount, bool aDir)
	Floating point heap sort. More...
void	tpt_insertion_sort_f32 (f32_t *aOutData, const f32_t *aInData, uint32_t aCount, bool aDir)
	Floating point insertion sort. More...
static void	tpt_topdown_merge (f32_t *pA, uint32_t begin, uint32_t middle, uint32_t end, f32_t *pB, uint8_t order)
	Floating point merge sort. More...
static void	tpt_merge_sort_core_f32 (f32_t *pB, uint32_t begin, uint32_t end, f32_t *pA, uint8_t order)
void	tpt_merge_sort_f32 (f32_t *aOutData, f32_t *aInData, uint32_t aCount, bool aDir)
	Floating point merge sort. More...
void	tpt_quick_sort_f32 (f32_t *aOutData, const f32_t *aInData, uint32_t aCount, bool aDir)
	Floating point quick sort. More...
void	tpt_selection_sort_f32 (f32_t *aOutData, const f32_t *aInData, uint32_t aCount, bool aDir)
	Floating point selection sort. More...
void	tpt_sort_f32 (f32_t *aOutData, const f32_t *aInData, uint32_t aCount, bool aDir)
	Default sorting function. More...

Detailed Description

Sort the elements of a vector

There are separate functions for floating-point, Q31, Q15, and Q7 data types.

Function Documentation

tpt_bitonic_sort_f32()

void tpt_bitonic_sort_f32	(	f32_t *	aOutData,
		const f32_t *	aInData,
		uint32_t	aCount,
		bool	aDir
	)

Floating point bitonic sort.

Parameters

[out]	aOutData	points to the block of output data
[in]	aInData	points to the block of input data.
[in]	aCount	number of samples to process.
[in]	aDir	Sorting order (direction) value = false : Descending order (9 to 0) value = true : Ascending order (0 to 9)

The aCount must be equal to a power of 2. If the aCount is not a power of 2, it will do nothing.

It's an in-place algorithm. In order to obtain an out-of-place function, a memcpy of the source vector is performed

tpt_bubble_sort_f32()

void tpt_bubble_sort_f32	(	f32_t *	aOutData,
		const f32_t *	aInData,
		uint32_t	aCount,
		bool	aDir
	)

Floating point bubble sort.

Parameters

[out]	aOutData	points to the block of output data
[in]	aInData	points to the block of input data.
[in]	aCount	number of samples to process.
[in]	aDir	Sorting order (direction) value = false : Descending order (9 to 0) value = true : Ascending order (0 to 9)

Algorithm

The bubble sort algorithm is a simple comparison algorithm that reads the elements of a vector from the beginning to the end, compares the adjacent ones and swaps them if they are in the wrong order. The procedure is repeated until there is nothing left to swap. Bubble sort is fast for input vectors that are nearly sorted.

It's an in-place algorithm. In order to obtain an out-of-place function, a memcpy of the source vector is performed.

tpt_heap_sort_f32()

void tpt_heap_sort_f32	(	f32_t *	aOutData,
		const f32_t *	aInData,
		uint32_t	aCount,
		bool	aDir
	)

Floating point heap sort.

Parameters

[out]	aOutData	points to the block of output data
[in]	aInData	points to the block of input data.
[in]	aCount	number of samples to process.
[in]	aDir	Sorting order (direction) value = false : Descending order (9 to 0) value = true : Ascending order (0 to 9)

Algorithm

The heap sort algorithm is a comparison algorithm that divides the input array into a sorted and an unsorted region, and shrinks the unsorted region by extracting the largest element and moving it to the sorted region. A heap data structure is used to find the maximum.

It's an in-place algorithm. In order to obtain an

out-of-place function, a memcpy of the source vector is performed.

tpt_insertion_sort_f32()

void tpt_insertion_sort_f32	(	f32_t *	aOutData,
		const f32_t *	aInData,
		uint32_t	aCount,
		bool	aDir
	)

Floating point insertion sort.

Parameters

[out]	aOutData	points to the block of output data
[in]	aInData	points to the block of input data.
[in]	aCount	number of samples to process.
[in]	aDir	Sorting order (direction) value = false : Descending order (9 to 0) value = true : Ascending order (0 to 9)

Algorithm

The insertion sort is a simple sorting algorithm that reads all the element of the input array and removes one element at a time, finds the location it belongs in the final sorted list, and inserts it there.

It's an in-place algorithm. In order to obtain an

out-of-place function, a memcpy of the source vector is performed.

tpt_merge_sort_core_f32()

static void tpt_merge_sort_core_f32 ( f32_t *  pB, uint32_t  begin, uint32_t  end, f32_t *  pA, uint8_t  order  )

static

tpt_merge_sort_f32()

void tpt_merge_sort_f32	(	f32_t *	aOutData,
		f32_t *	aInData,
		uint32_t	aCount,
		bool	aDir
	)

Floating point merge sort.

Parameters

[out]	aOutData	points to the block of output data
[in]	aInData	points to the block of input data.
[in]	aCount	number of samples to process.
[in]	aDir	Sorting order (direction) value = false : Descending order (9 to 0) value = true : Ascending order (0 to 9)

tpt_quick_sort_f32()

void tpt_quick_sort_f32	(	f32_t *	aOutData,
		const f32_t *	aInData,
		uint32_t	aCount,
		bool	aDir
	)

Floating point quick sort.

Parameters

[out]	aOutData	points to the block of output data
[in]	aInData	points to the block of input data.
[in]	aCount	number of samples to process.
[in]	aDir	Sorting order (direction) value = false : Descending order (9 to 0) value = true : Ascending order (0 to 9)

Algorithm

The quick sort algorithm is a comparison algorithm that divides the input array into two smaller sub-arrays and recursively sort them. An element of the array (the pivot) is chosen, all the elements with values smaller than the pivot are moved before the pivot, while all elements with values greater than the pivot are moved after it (partition).

In this implementation the Hoare partition scheme has been used [Hoare, C. A. R. (1 January 1962). "Quicksort". The Computer Journal. 5 (1): 10–16.] The first element has always been chosen as the pivot. The partition algorithm guarantees that the returned pivot is never placed outside the vector, since it is returned only when the pointers crossed each other. In this way it isn't possible to obtain empty partitions and infinite recursion is avoided.

It's an in-place algorithm. In order to obtain an out-of-place function, a memcpy of the source vector is performed.

tpt_selection_sort_f32()

void tpt_selection_sort_f32	(	f32_t *	aOutData,
		const f32_t *	aInData,
		uint32_t	aCount,
		bool	aDir
	)

Floating point selection sort.

Parameters

[out]	aOutData	points to the block of output data
[in]	aInData	points to the block of input data.
[in]	aCount	number of samples to process.
[in]	aDir	Sorting order (direction) value = false : Descending order (9 to 0) value = true : Ascending order (0 to 9)

Algorithm

The Selection sort algorithm is a comparison algorithm that divides the input array into a sorted and an unsorted sublist (initially the sorted sublist is empty and the unsorted sublist is the input array), looks for the smallest (or biggest) element in the unsorted sublist, swapping it with the leftmost one, and moving the sublists boundary one element to the right.

It's an in-place algorithm. In order to obtain an

out-of-place function, a memcpy of the source vector is performed.

tpt_sort_f32()

void tpt_sort_f32	(	f32_t *	aOutData,
		const f32_t *	aInData,
		uint32_t	aCount,
		bool	aDir
	)

Default sorting function.

Parameters

[out]	aOutData	points to the block of output data.
[in]	aInData	points to the block of input data.
[in]	aCount	number of samples to process.
[in]	aDir	Sorting order (direction) value = false : Descending order (9 to 0) value = true : Ascending order (0 to 9)

tpt_topdown_merge()

static void tpt_topdown_merge ( f32_t *  pA, uint32_t  begin, uint32_t  middle, uint32_t  end, f32_t *  pB, uint8_t  order  )

static

Floating point merge sort.

Parameters

[out]	aOutData	points to the block of output data
[in]	aInData	points to the block of input data.
[in]	aCount	number of samples to process.
[in]	aDir	Sorting order (direction) value = false : Descending order (9 to 0) value = true : Ascending order (0 to 9)

Algorithm

The merge sort algorithm is a comparison algorithm that divide the input array in sublists and merge them to produce longer sorted sublists until there is only one list remaining.

A work array is always needed. It must be allocated by the

user linked to the instance at initialization time.

It's an in-place algorithm. In order to obtain an

out-of-place function, a memcpy of the source vector is performed.