ListSort
Description
Sort the list using a quicksort over a temporary contiguous buffer of the element values, then write the sorted order back into the list nodes.
Parameters
| Name | Direction | Description |
|---|---|---|
l |
in,out | List to be sorted. |
compare |
in | Comparator returning a three-way ordering: negative when a < b, zero when equal, positive when a > b. |
Success
Returns true. Elements are now in non-decreasing order according to compare. The list length and node count are unchanged; the scratch buffer has been released.
Failure
Returns false if the temporary contiguous buffer cannot be allocated. The list order and contents are unchanged.
Usage example (Cross-references)
Usage examples (Cross-references)
- In
Ops.h:59:
#define ListMustSort(l, compare) \
do { \
if (!ListSort((l), (compare))) { \
LOG_FATAL("ListMustSort failed"); \
} \- In
ListInt.c:185:
// Advanced functions
case LIST_INT_SORT : {
ListSort(list, compare_ints);
break;
}- In
Ops.c:112:
static bool test_list_sort_and_reverse(void) {
WriteFmt("Testing ListSort and ListReverse\n");
DefaultAllocator alloc = DefaultAllocatorInit();- In
Ops.c:125:
ListPushBackR(&list, 2);
ListSort(&list, compare_ints);
bool result = list_matches(GENERIC_LIST(&list), (const int[]) {1, 2, 2, 3, 4}, 5);- In
Ops.c:137:
static bool test_list_sort_and_reverse_edge_cases(void) {
WriteFmt("Testing ListSort and ListReverse edge cases\n");
DefaultAllocator alloc = DefaultAllocatorInit();- In
Ops.c:145:
IntList singleton = ListInit(&alloc);
ListSort(&empty, compare_ints);
ListReverse(&empty);
ListPushBackR(&singleton, 42);- In
Ops.c:148:
ListReverse(&empty);
ListPushBackR(&singleton, 42);
ListSort(&singleton, compare_ints);
ListReverse(&singleton);- In
Ops.c:193:
// actually ascending afterward.
static bool test_sort_two_element_list(void) {
WriteFmt("Testing ListSort orders a two-element list\n");
DefaultAllocator alloc = DefaultAllocatorInit();- In
Ops.c:202:
ListPushBackR(&list, 1);
bool ok = ListSort(&list, compare_ints);
bool result = ok && (ListLen(&list) == 2);
result = result && (ListAt(&list, 0) == 1);- In
Deadend.c:325:
static bool test_list_sort_without_compare_fails(void) {
WriteFmt("Testing ListSort without compare function\n");
List(int) list = ListInit(get_test_alloc());- In
Deadend.c:329:
List(int) list = ListInit(get_test_alloc());
ListPushBackR(&list, 10);
ListSort(&list, NULL);
return false;
Last updated on