Starting from API version 26.0.0, FAST Kit provides the algorithm library for sorting generic data types. It supports full sorting, partial sorting, and natural language string sorting for any data type.
The algorithm library provides the following capabilities:
Generic sorting (HMS_FAST_Algo_Sort): fully sorts an array of any data type, leveraging a custom user-defined comparison function for flexible sorting logic.
Partial sorting (HMS_FAST_Algo_PartialSortAt): performs in-place partial sorting on an array so that the specified range [offset, offset + count) contains the exact elements that would occupy those positions when sorted. Ideal for scenarios such as Top-K selection.
Natural language sorting (HMS_FAST_Algo_NaturalSort): sorts an array of UTF-8 encoded C-strings using natural alphanumeric ordering, correctly handling numeric sequences (for example, file1, file2, file10 instead of file1, file10, file2).
Natural language partial sorting (HMS_FAST_Algo_NaturalPartialSortAt): combines natural language sorting with partial sorting to efficiently retrieve a specified range from a sorted string array.
The algorithm library is applicable to the following scenarios:
Generic sorting:
Partial sorting:
Natural language sorting:
SortData (sort data descriptor): describes the structure of the data to be sorted. It contains three fields: element size (sizeOf), array length (length), and data pointer (data), enabling support for sorting arbitrary data types.
Comparator (comparison function): a developer-provided comparison callback function. It takes pointers to two elements and returns a negative number if the first element is less than the second, zero if they are equal, or a positive number if the first element is greater than the second.
Natural Sort (natural language sorting): an intelligent string sorting method that treats numeric sequences within strings as single numeric values rather than comparing characters individually, producing results that align with human intuition.
Partial Sort (partial sorting): Only ensures that the elements in the specified range are in the correct positions after sorting. The elements outside the range only meet the size relationship with the elements in the range, and are not completely sorted.
For details about the APIs, please refer to the API Reference.
| API | Description |
|---|---|
| FAST_ErrorCode HMS_FAST_Algo_Sort (HMS_FAST_SortData *data, HMS_FAST_Sort_CompFunc comp) | Fully sorts an array of arbitrary type using a user-provided comparison function. |
| FAST_ErrorCode HMS_FAST_Algo_PartialSortAt (HMS_FAST_SortData *data, size_t offset, size_t count, HMS_FAST_Sort_CompFunc comp) | Performs an in-place partial sort on an array, making the specified range correspond to a sorted segment. |
| FAST_ErrorCode HMS_FAST_Algo_NaturalSort (HMS_FAST_SortData *data, int32_t ascend) | Sorts an array of UTF-8 strings using natural language rules. |
| FAST_ErrorCode HMS_FAST_Algo_NaturalPartialSortAt (HMS_FAST_SortData *data, size_t offset, size_t count, int32_t ascend) | Partially sorts an array of UTF-8 strings using natural language rules, making the specified range correspond to a sorted segment. |
Link the related dynamic library in the CMake script.
find_library(
lib_fast_utils
NAMES fast_utils
)
target_link_libraries(entry PRIVATE ${lib_fast_utils}) Define the comparison function.
Construct the HMS_FAST_SortData structure.
Call HMS_FAST_Algo_Sort to perform sorting.
Check the return value to determine whether the sorting is successful.
#include "FASTKit/fast_utils_algorithm.h"
#include <cstdio>
#include <cstdlib>
// Define the integer comparison function.
static int compareInt(HMS_FAST_SortElementConstPtr first, HMS_FAST_SortElementConstPtr second) {
int a = *static_cast<const int*>(first);
int b = *static_cast<const int*>(second);
if (a < b) return -1;
if (a > b) return 1;
return 0;
}
int main() {
int arr[] = {5, 2, 8, 1, 9, 3, 7, 4, 6, 0};
size_t length = sizeof(arr) / sizeof(arr[0]);
HMS_FAST_SortData data = {sizeof(int), length, arr};
FAST_ErrorCode ret = HMS_FAST_Algo_Sort(&data, compareInt);
if (ret != FAST_ERROR_CODE_SUCCESS) {
printf("Sorting failed with error code: %d\n", ret);
return -1;
}
// After sorting: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
for (size_t i = 0; i < length; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
} Define the comparison function (same as that for generic sorting).
Construct the HMS_FAST_SortData structure.
Specify the sorting range parameters (offset and count).
Call HMS_FAST_Algo_PartialSortAt to perform partial sorting.
Check the return value to determine whether the sorting is successful.
#include "FASTKit/fast_utils_algorithm.h"
#include <cstdio>
static int compareInt(HMS_FAST_SortElementConstPtr first, HMS_FAST_SortElementConstPtr second) {
int a = *static_cast<const int*>(first);
int b = *static_cast<const int*>(second);
if (a < b) return -1;
if (a > b) return 1;
return 0;
}
int main() {
int arr[] = {9, 4, 7, 1, 3, 8, 5, 6, 2, 0};
size_t length = sizeof(arr) / sizeof(arr[0]);
HMS_FAST_SortData data = {sizeof(int), length, arr};
// Obtain three elements starting from arr[2].
FAST_ErrorCode ret = HMS_FAST_Algo_PartialSortAt(&data, 2, 3, compareInt);
if (ret != FAST_ERROR_CODE_SUCCESS) {
printf("Partial sort failed with error code: %d\n", ret);
return -1;
}
// The three elements in the window are 2, 3, and 4 (sorted).
printf("Element 2~4: %d, %d, %d\n", arr[2], arr[3], arr[4]);
return 0;
} Construct the HMS_FAST_SortData structure. (Note that sizeOf must be sizeof(char)*.)
Specify the sorting direction. (ascend: non-zero value indicates ascending order, and zero indicates descending order.)
Call HMS_FAST_Algo_NaturalSort to perform natural language sorting.
Check the return value to determine whether the sorting is successful.
#include "FASTKit/fast_utils_algorithm.h"
#include <cstdio>
int main() {
const char* arr[] = {"file10.txt", "file2.txt", "file1.txt", "file20.txt", "file3.txt"};
size_t length = sizeof(arr) / sizeof(arr[0]);
HMS_FAST_SortData data = {sizeof(char*), length, const_cast<char**>(arr)};
// Sort in ascending order.
FAST_ErrorCode ret = HMS_FAST_Algo_NaturalSort(&data, 1);
if (ret != FAST_ERROR_CODE_SUCCESS) {
printf("Natural sort failed with error code: %d\n", ret);
return -1;
}
// After sorting: file1.txt, file2.txt, file3.txt, file10.txt, file20.txt
for (size_t i = 0; i < length; i++) {
printf("%s\n", arr[i]);
}
return 0;
}