src/cdsa_algorithms.h File Reference

Provides some useful general algorithms and collects in one place the algorithms that are defined in other modules (like heapsort in heap.h). More...

#include <stdbool.h>
#include <time.h>
#include "utils.h"

Include dependency graph for cdsa_algorithms.h:

Go to the source code of this file.

Functions
cdsa_status_t	cdsa_heap_sort (void *arr, size_t nmemb, size_t ptrsize, cdsa_compare_func_t compare)
	Sort the first nmemb items in the given array of pointers.
cdsa_status_t	cdsa_partition_data (void *arr, size_t nmemb, size_t w, cdsa_compare_func_t compare, int *index)
	Perform an in-place partition of an array of data elements (e.g., int rather than int *) into two groups: those to the left of the index returned, which are less than or equal to the element at the index returned, and those to the right of the index returned, which are greater than or equal to the element at the index returned.
cdsa_status_t	cdsa_partition_ptrs (void *arr, size_t nmemb, size_t w, cdsa_compare_func_t compare, int *index)
	Perform an in-place partition of an array of pointers into two groups: those to the left of the index returned, which are less than or equal to the element at the index returned, and those to the right of the index returned, which are greater than or equal to the element at the index returned.
cdsa_status_t	cdsa_select_data (void *arr, size_t nmemb, size_t w, size_t k, cdsa_compare_func_t compare)
	Select the k smallest data elements from the array of data elements (e.g., int rather than int *), moving them to the front of the array.
cdsa_status_t	cdsa_select_ptrs (void *arr, size_t nmemb, size_t w, size_t k, cdsa_compare_func_t compare)
	Select the k smallest elements from the array of pointers, moving them to the front of the array.

---

Detailed Description

Provides some useful general algorithms and collects in one place the algorithms that are defined in other modules (like heapsort in heap.h).

Definition in file cdsa_algorithms.h.

---

Function Documentation

cdsa_status_t cdsa_heap_sort	(	void *	arr,
		size_t	nmemb,
		size_t	ptrsize,
		cdsa_compare_func_t	compare
	)

Sort the first nmemb items in the given array of pointers.

This function performs an in-place heap sort on the first nmemb pointers in the array. It requires no extra memory, and it has time complexity of O(n log n).

The array must contain only pointers, each of which is the same size, and the compare function will be passed the pointers that are stored in the array (and not pointers to the array locations themselves).

Parameters:

	arr	An array of pointers each of which is ptrsize bytes in size.
	nmemb	The number of items in the array to be sorted.
	ptrsize	The size of each pointer in bytes.
	compare	A non-NULL compare function for comparing elements.

cdsa_status_t cdsa_partition_data	(	void *	arr,
		size_t	nmemb,
		size_t	w,
		cdsa_compare_func_t	compare,
		int *	index
	)

Perform an in-place partition of an array of data elements (e.g., int rather than int *) into two groups: those to the left of the index returned, which are less than or equal to the element at the index returned, and those to the right of the index returned, which are greater than or equal to the element at the index returned.

Parameters:

	arr	The non-NULL base of the array.
	nmemb	The number of members to partition.
	w	The size of each member in bytes.
	compare	The function to use for comparing members.
	index	A non-NULL pointer to an int for recording the index of the pivot element after partitioning.

cdsa_status_t cdsa_partition_ptrs	(	void *	arr,
		size_t	nmemb,
		size_t	w,
		cdsa_compare_func_t	compare,
		int *	index
	)

Perform an in-place partition of an array of pointers into two groups: those to the left of the index returned, which are less than or equal to the element at the index returned, and those to the right of the index returned, which are greater than or equal to the element at the index returned.

Parameters:

	arr	The non-NULL base of the array.
	nmemb	The number of members to partition.
	w	The size of each pointer in bytes.
	compare	The function to use for comparing members.
	index	A non-NULL pointer to an int for recording the index of the pivot element after partitioning.

cdsa_status_t cdsa_select_data	(	void *	arr,
		size_t	nmemb,
		size_t	w,
		size_t	k,
		cdsa_compare_func_t	compare
	)

Select the k smallest data elements from the array of data elements (e.g., int rather than int *), moving them to the front of the array.

Parameters:

	arr	The non-NULL array.
	nmemb	The number of members in the array.
	w	The width (size in bytes) of each member.
	k	How many elements to select (e.g., k=1 puts the smallest element at arr[0]). The k selected elements will be moved to positions arr[0..k-1] and the array will be otherwise modified, but all elements originally in the array remain after the function completes.
	compare	The function to use for comparing elements. It receives two pointers, each of with is a pointer into the array to a data element.

This algorithm operates in expected linear time.

cdsa_status_t cdsa_select_ptrs	(	void *	arr,
		size_t	nmemb,
		size_t	w,
		size_t	k,
		cdsa_compare_func_t	compare
	)

Select the k smallest elements from the array of pointers, moving them to the front of the array.

Parameters:

	arr	The non-NULL array.
	nmemb	The number of members in the array.
	w	The width (size in bytes) of each pointer.
	k	How many elements to select (e.g., k=1 puts the smallest element at arr[0]). The k selected elements will be moved to positions arr[0..k-1] and the array will be otherwise modified, but all elements originally in the array remain after the function completes.
	compare	The function to use for comparing elements. It receives two pointers, each of which is a pointer that is stored in the array.

This algorithm operates in expected linear time.