Vector sorting algorithms

Sort the elements of a vector. More...

Functions
void	riscv_bitonic_sort_f32 (const riscv_sort_instance_f32 *S, float32_t *pSrc, float32_t *pDst, uint32_t blockSize)
void	riscv_bubble_sort_f32 (const riscv_sort_instance_f32 *S, float32_t *pSrc, float32_t *pDst, uint32_t blockSize)
void	riscv_heap_sort_f32 (const riscv_sort_instance_f32 *S, float32_t *pSrc, float32_t *pDst, uint32_t blockSize)
void	riscv_insertion_sort_f32 (const riscv_sort_instance_f32 *S, float32_t *pSrc, float32_t *pDst, uint32_t blockSize)
void	riscv_merge_sort_f32 (const riscv_merge_sort_instance_f32 *S, float32_t *pSrc, float32_t *pDst, uint32_t blockSize)
void	riscv_merge_sort_init_f32 (riscv_merge_sort_instance_f32 *S, riscv_sort_dir dir, float32_t *buffer)
void	riscv_quick_sort_f32 (const riscv_sort_instance_f32 *S, float32_t *pSrc, float32_t *pDst, uint32_t blockSize)
void	riscv_selection_sort_f32 (const riscv_sort_instance_f32 *S, float32_t *pSrc, float32_t *pDst, uint32_t blockSize)
void	riscv_sort_f32 (const riscv_sort_instance_f32 *S, float32_t *pSrc, float32_t *pDst, uint32_t blockSize)
	Generic sorting function. More...
void	riscv_sort_init_f32 (riscv_sort_instance_f32 *S, riscv_sort_alg alg, riscv_sort_dir dir)

Detailed Description

Sort the elements of a vector.

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

Function Documentation

riscv_bitonic_sort_f32()

void riscv_bitonic_sort_f32 ( const riscv_sort_instance_f32 *  S, float32_t *  pSrc, float32_t *  pDst, uint32_t  blockSize  )

private

Parameters

[in]	S	points to an instance of the sorting structure.
[in]	pSrc	points to the block of input data.
[out]	pDst	points to the block of output data
[in]	blockSize	number of samples to process.

riscv_bubble_sort_f32()

void riscv_bubble_sort_f32 ( const riscv_sort_instance_f32 *  S, float32_t *  pSrc, float32_t *  pDst, uint32_t  blockSize  )

private

Parameters

[in]	S	points to an instance of the sorting structure.
[in]	pSrc	points to the block of input data.
[out]	pDst	points to the block of output data
[in]	blockSize	number of samples to process.

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

riscv_heap_sort_f32()

void riscv_heap_sort_f32 ( const riscv_sort_instance_f32 *  S, float32_t *  pSrc, float32_t *  pDst, uint32_t  blockSize  )

private

Parameters

[in]	S	points to an instance of the sorting structure.
[in]	pSrc	points to the block of input data.
[out]	pDst	points to the block of output data
[in]	blockSize	number of samples to process.

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.

riscv_insertion_sort_f32()

void riscv_insertion_sort_f32 ( const riscv_sort_instance_f32 *  S, float32_t *  pSrc, float32_t *  pDst, uint32_t  blockSize  )

private

Parameters

[in]	S	points to an instance of the sorting structure.
[in]	pSrc	points to the block of input data.
[out]	pDst	points to the block of output data
[in]	blockSize	number of samples to process.

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.

riscv_merge_sort_f32()

void riscv_merge_sort_f32	(	const riscv_merge_sort_instance_f32 *	S,
		float32_t *	pSrc,
		float32_t *	pDst,
		uint32_t	blockSize
	)

Parameters

[in]	S	points to an instance of the sorting structure.
[in]	pSrc	points to the block of input data.
[out]	pDst	points to the block of output data
[in]	blockSize	number of samples to process.

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

riscv_merge_sort_init_f32()

void riscv_merge_sort_init_f32	(	riscv_merge_sort_instance_f32 *	S,
		riscv_sort_dir	dir,
		float32_t *	buffer
	)

Parameters

[in,out]	S	points to an instance of the sorting structure.
[in]	dir	Sorting order.
[in]	buffer	Working buffer.

riscv_quick_sort_f32()

void riscv_quick_sort_f32 ( const riscv_sort_instance_f32 *  S, float32_t *  pSrc, float32_t *  pDst, uint32_t  blockSize  )

private

Parameters

[in]	S	points to an instance of the sorting structure.
[in,out]	pSrc	points to the block of input data.
[out]	pDst	points to the block of output data.
[in]	blockSize	number of samples to process.

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.

riscv_selection_sort_f32()

void riscv_selection_sort_f32 ( const riscv_sort_instance_f32 *  S, float32_t *  pSrc, float32_t *  pDst, uint32_t  blockSize  )

private

Parameters

[in]	S	points to an instance of the sorting structure.
[in]	pSrc	points to the block of input data.
[out]	pDst	points to the block of output data
[in]	blockSize	number of samples to process.

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.

riscv_sort_f32()

void riscv_sort_f32	(	const riscv_sort_instance_f32 *	S,
		float32_t *	pSrc,
		float32_t *	pDst,
		uint32_t	blockSize
	)

Generic sorting function.

Parameters

[in]	S	points to an instance of the sorting structure.
[in]	pSrc	points to the block of input data.
[out]	pDst	points to the block of output data.
[in]	blockSize	number of samples to process.

riscv_sort_init_f32()

void riscv_sort_init_f32	(	riscv_sort_instance_f32 *	S,
		riscv_sort_alg	alg,
		riscv_sort_dir	dir
	)

Parameters

[in,out]	S	points to an instance of the sorting structure.
[in]	alg	Selected algorithm.
[in]	dir	Sorting order.