sort.h File Reference

The C Container Collection Sorting Interface. More...

#include "buffer.h"
#include "doubly_linked_list.h"
#include "singly_linked_list.h"
#include "types.h"

Include dependency graph for sort.h:

Go to the source code of this file.

Detailed Description

The C Container Collection Sorting Interface.

These functions sort various containers with different algorithms depending on the container. Many more sorting algorithms will likely be added here in the future. Containers such as the buffer and linked lists do not own comparators upon initialization because sorting is not the most common use case. Therefore comparators are adaptors we can pass while performing an algorithm. They then implement this algorithm internally with the passed ordering and comparator. A container such as a linked list may also be able to report back if it is sorted or insert an element in a sorted position.

Sorting Algorithms
Various sorting algorithms for different containers in the collection.
#define	CCC_sort_mergesort(list_pointer, order, comparator_pointer)
	Sorts the list in user specified order as defined by the provided order and comparator. O(N * log(N)) time, O(1) space.
CCC_Result	CCC_sort_heapsort (CCC_Buffer *buffer, void *temp, CCC_Order order, CCC_Comparator const *comparator)
	Sorts the input buffer in O(N * log(N)) time and O(1) space according to the desired input order.
CCC_Result	CCC_sort_doubly_linked_list_mergesort (CCC_Doubly_linked_list *list, CCC_Order order, CCC_Comparator const *comparator)
	Sorts the doubly linked list in user specified order as defined by the provided order and comparator. O(N * log(N)) time, O(1) space.
CCC_Result	CCC_sort_singly_linked_list_mergesort (CCC_Singly_linked_list *list, CCC_Order order, CCC_Comparator const *comparator)
	Sorts the singly linked list in user specified order as defined by the provided order and comparator. O(N * log(N)) time, O(1) space.

Macro Definition Documentation

CCC_sort_mergesort

#define CCC_sort_mergesort	(		list_pointer,
			order,
			comparator_pointer
	)

Value:

    _Generic((list_pointer), CCC_Singly_linked_list *: CCC_sort_singly_linked_list_mergesort, CCC_Doubly_linked_list *: CCC_sort_doubly_linked_list_mergesort)( \
        list_pointer, order, comparator_pointer                                                                                                                 \
    )

Sorts the list in user specified order as defined by the provided order and comparator. O(N * log(N)) time, O(1) space.

Parameters

[in]	list_pointer	a pointer to the list to sort.
[in]	order	the desired order of the sorted list. CCC_ORDER_LESSER places elements in non-decreasing order starting from index [0, N), where N is the count of the list. CCC_ORDER_GREATER places elements in non-increasing order starting from index [0, N), where N is the count of the list. This is done to remain consistent with heap order, where CCC_ORDER_LESSER places the minimum element at index 0 and CCC_ORDER_GREATER places the maximum element at index 0 because 0 is the first node in the list.
[in]	comparator_pointer	the pointer to the comparator context for comparing list elements.

Returns

the result of the sort, usually OK. An argument error for bad input.

Function Documentation

CCC_sort_doubly_linked_list_mergesort()

CCC_Result CCC_sort_doubly_linked_list_mergesort	(	CCC_Doubly_linked_list *	list,
		CCC_Order	order,
		CCC_Comparator const *	comparator
	)

Sorts the doubly linked list in user specified order as defined by the provided order and comparator. O(N * log(N)) time, O(1) space.

Parameters

[in]	list	a pointer to the doubly linked list to sort.
[in]	order	the desired order of the sorted list. CCC_ORDER_LESSER places elements in non-decreasing order starting from index [0, N), where N is the count of the list. CCC_ORDER_GREATER places elements in non-increasing order starting from index [0, N), where N is the count of the list. This is done to remain consistent with heap order, where CCC_ORDER_LESSER places the minimum element at index 0 and CCC_ORDER_GREATER places the maximum element at index 0 because 0 is the first node in the list.
[in]	comparator	the comparator context for comparing list elements.

Returns

the result of the sort, usually OK. An argument error if doubly_linked_list is null.

CCC_sort_heapsort()

CCC_Result CCC_sort_heapsort	(	CCC_Buffer *	buffer,
		void *	temp,
		CCC_Order	order,
		CCC_Comparator const *	comparator
	)

Sorts the input buffer in O(N * log(N)) time and O(1) space according to the desired input order.

Parameters

[in]	buffer	the buffer to be modified and sorted in place.
[in]	temp	a pointer to a dummy user type that will be used for swapping.
[in]	order	the desired order of the sorted buffer. CCC_ORDER_LESSER places elements in non-decreasing order starting from index [0, N), where N is the count of the buffer. CCC_ORDER_GREATER places elements in non-increasing order starting from index [0, N), where N is the count of the buffer. This is done to remain consistent with heap order, where CCC_ORDER_LESSER places the minimum element at index 0 and CCC_ORDER_GREATER places the maximum element at index 0 because 0 is the root of the tree in either heap ordering.
[in]	comparator	the comparator context for comparing buffer elements.

Returns

the result of the sorting operation. If an argument input error occurs an input error result is provided. Allocation is not needed to sort elements in the buffer so memory related errors are not possible if the provided buffer is initialized correctly.

Warning

Assumes the input buffer has been correctly initialized via its interface.

An easy way to provide a temp slot is with an anonymous compound literal such as &(My_type){}, passed directly as an argument.

The sort is not inherently stable and uses the provided comparison function to order the elements.

CCC_sort_singly_linked_list_mergesort()

CCC_Result CCC_sort_singly_linked_list_mergesort	(	CCC_Singly_linked_list *	list,
		CCC_Order	order,
		CCC_Comparator const *	comparator
	)

Sorts the singly linked list in user specified order as defined by the provided order and comparator. O(N * log(N)) time, O(1) space.

Parameters

[in]	list	a pointer to the singly linked list to sort.
[in]	order	the desired order of the sorted list. CCC_ORDER_LESSER places elements in non-decreasing order starting from index [0, N), where N is the count of the list. CCC_ORDER_GREATER places elements in non-increasing order starting from index [0, N), where N is the count of the list. This is done to remain consistent with heap order, where CCC_ORDER_LESSER places the minimum element at index 0 and CCC_ORDER_GREATER places the maximum element at index 0 because 0 is the first node in the list.
[in]	comparator	the comparator context for comparing list elements.

Returns

the result of the sort, usually OK. An argument error if singly_linked_list is null.