# Vector sorting algorithms

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_sort_f32(const riscv_sort_instance_f32 *S, float32_t *pSrc, float32_t *pDst, uint32_t blockSize)
void riscv_sort_init_f32(riscv_sort_instance_f32 *S, riscv_sort_alg alg, riscv_sort_dir dir)
group Sorting

Sort the elements of a vector.

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

Functions

void riscv_bitonic_sort_f32(const riscv_sort_instance_f32 *S, float32_t *pSrc, float32_t *pDst, uint32_t blockSize)
Parameters
• S[in] points to an instance of the sorting structure.

• pSrc[in] points to the block of input data.

• pDst[out] points to the block of output data

• blockSize[in] number of samples to process.

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

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

Parameters
• S[in] points to an instance of the sorting structure.

• pSrc[in] points to the block of input data.

• pDst[out] points to the block of output data

• blockSize[in] number of samples to process.

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

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.

Parameters
• S[in] points to an instance of the sorting structure.

• pSrc[in] points to the block of input data.

• pDst[out] points to the block of output data

• blockSize[in] number of samples to process.

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

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.

Parameters
• S[in] points to an instance of the sorting structure.

• pSrc[in] points to the block of input data.

• pDst[out] points to the block of output data

• blockSize[in] number of samples to process.

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

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

Parameters
• S[in] points to an instance of the sorting structure.

• pSrc[in] points to the block of input data.

• pDst[out] points to the block of output data

• blockSize[in] number of samples to process.

void riscv_merge_sort_init_f32(riscv_merge_sort_instance_f32 *S, riscv_sort_dir dir, float32_t *buffer)
Parameters
• S[inout] points to an instance of the sorting structure.

• dir[in] Sorting order.

• buffer[in] Working buffer.

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

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.

Parameters
• S[in] points to an instance of the sorting structure.

• pSrc[inout] points to the block of input data.

• pDst[out] points to the block of output data.

• blockSize[in] number of samples to process.

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

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.

Parameters
• S[in] points to an instance of the sorting structure.

• pSrc[in] points to the block of input data.

• pDst[out] points to the block of output data

• blockSize[in] number of samples to process.

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

Generic sorting function.

Parameters
• S[in] points to an instance of the sorting structure.

• pSrc[in] points to the block of input data.

• pDst[out] points to the block of output data.

• blockSize[in] number of samples to process.

void riscv_sort_init_f32(riscv_sort_instance_f32 *S, riscv_sort_alg alg, riscv_sort_dir dir)
Parameters
• S[inout] points to an instance of the sorting structure.

• alg[in] Selected algorithm.

• dir[in] Sorting order.