Sorting of commonly used data structures and algorithms in the iOS standard library

A linked list of common data structures in iOS

🎢 sorting

Sorting refers to the process of changing an array of disorderly numbers into an ordered arrangement. IOS provides five sort functions: quicksort, heap sort, merge sort, parallel sort and radix sort. Please refer to the relevant documentation for a detailed description of each sort concept. The table below looks at sorting functions in terms of time complexity, stability, whether additional memory needs to be allocated, whether ordered arrays are optimized, range of applications, and platform support:

Fast, heap, merge, parallel sort

Function: These four kinds of sorting function parameters are consistent, so listed together for introduction.

#include

Platform: Qsort is supported by POSIX, psort is unique to iOS, and everything else is supported by BSD Unix

Function signature:

Void qsort(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *)); Void qsort_b(void *base, size_t nel, size_t width, int (^compar)(const void *, const void *)); Void qsort_r(void *base, size_t nel, size_t width, void *thunk, int (*compar)(void *, const void *, const void *)); // heapsort int heapsort(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *)); Int heapsort_b(void *base, size_t nel, size_t width, int (^compar)(const void *, const void *)); Void *base, size_t nel, size_t width, int (*compar)(const void *, const void *)); // mergesort int mergesort(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *)); Int mergesort_b(void *base, size_t nel, size_t width, int (^compar)(const void *, const void *)); Void psort(void *base, size_t nel, size_t width, int (*compar)(const void *, const void *)); Void psort_b(void *base, size_t nel, size_t width, int (^compar)(const void *, const void *)); Void psort_r(void *base, size_t nel, size_t width, void *thunk, int (*compar)(void *, const void *, const void *));Copy the code

Parameters:

Base :[in/out] The first address of the sorted array.

Nel :[in] The number of elements in the array.

Width :[in] The size of each element in the array.

Compar: [in] function comparator that determines sorting order by calling the function comparator on two elements in an array. The format of the function comparator is as follows:

/* @thunk: an additional argument to the function comparator, whose value is the thunk argument to the appraised version of the sorting function above. @element1, element2: The address of the element in the array. Note that this parameter is not the element itself, but the offset address of the element in the array. @return: Returns 0 if the comparison is equal, if element1 returns less than 0 before element2, Return greater than 0 if element1 is after elemen2 */ int compar(const void *element1, const void *element2); Int compar(void *thunk, const void *element1, const void *element2);Copy the code

Return :[out] For heapsort and merge sort, it is possible that the sort will fail. If the sort succeeds, it will return 0. Otherwise, it will return non-0.

Description:

1. The qsort function is used for quicksort, using the quicksort algorithm implemented by C.A.R. Hoare. Quicksort is an unstable sort, the fastest sort, with an average time of O(N*logN) because it does not optimize ordered arrays, so the worst possible time is O(N^2). Quicksort uses a recursive mechanism to sort internally, so there is no extra memory allocation. Of course, if the array has a large number of elements, excessive recursion may cause stack overflow, so its internal implementation will be converted to heap sort if it exceeds the agreed number of recursions.

2. The heapsort function is used for heapsort, using the heapsort algorithm implemented by J.W.J. William. Heap sort is an unstable sort whose time complexity is O(N*logN). Heapsort optimizes the processing of ordered arrays. Heap sort sorts with almost no additional memory allocation and consumption processing.

3. The mergesort function is used for mergesort, which is a stable sort with an average time complexity of O(N*logN) because it optimizes ordered arrays so that the best possible time is O(N). The disadvantage of merge sort is that it is possible to allocate a large amount of extra memory (the size of the sort array) within the sort implementation, so it is not suitable for sorting arrays with too many elements.

4. The psort function is used for parallel sorting, which is unique to iOS. Parallel sorting is also an unstable sort. When the number of elements in the array is less than 2000 or the CPU is single-core, the internal parallel sort is realized by using quicksort QSORT, while when the number is greater than 2000 and the CPU is multi-core, the system will open up multiple threads to perform parallel sort processing. So you can use this function to sort a large number of things that you want to do in parallel, but the downside is the overhead of thread creation and scheduling.

5. The above sort function ending in _r is a sort function with an additional argument, so that the additional argument can be used in the comparator to achieve some extended capability, which is the same as the element comparison capability ending in _B with block comparison.

Sample code:

int compar(const void *element1, Const char *p1 = *(const char **)element1; const char **)element1; const char *p2 = *(const char **)element2;return strcmp(p1, p2);
}

void main()
{
     char *arr[6] = {"Bob"."Max"."Alice"."Jone"."Lucy"."Lili"};
    
      qsort(arr, sizeof(arr)/sizeof(char*), sizeof(char*), compar); 
      heapsort(arr, sizeof(arr)/sizeof(char*), sizeof(char*), compar); 
      mergesort(arr, sizeof(arr)/sizeof(char*), sizeof(char*), compar); 
      psort(arr, sizeof(arr)/sizeof(char*), sizeof(char*), compar); 
}
Copy the code

Second, radix sort

Function: Radix sort is the use of some restrictions on the value of the sort elements to sort. So radix sort does not apply to any data structure. In the case of system-provided functions, only sorting based on byte arrays (byte arrays include strings) is currently supported. The system provides stable and unstable sorting functions for radix sort respectively. Refer to the documentation for more details on radix sorting.

Header: #include

, #include

Platform: BSD Unix

Function signature:

Int radixsort(const unsigned char **base, int nmemb, const unsigned char *table,unsigned endbyte); Int sradixsort(const unsigned char **base, int nmemb, const unsigned char *table,unsigned endbyte);Copy the code

Parameters:

Base: [in/out]: pointer to a byte array.

Nmemb :[in] Number of bytes in an array.

Table :[in] can be passed either NULL or an array of length 256. Because the encoding value of a byte symbol ranges from 0 to 255, the value of each element in the table indicates the weight value of each byte symbol, which also takes the value from 0 to 255. This table is used to determine whether the radix byte array is sorted in ascending or descending order, if the values in the table are 0 to 255, and descending if the values in the table are 255 to 0. At the same time, this table can also be used to determine whether characters are case-sensitive. For example, characters A-Z and A-Z have different byte encoding values. Therefore, if the specific gravity values of corresponding positions in the table are different, they are case-sensitive. So you can do case-insensitive sorting. The specific use of table is explained in the following examples. If we do not want to customize the collation then passing NULL this parameter indicates sorting in ascending order.

Endbyte :[in] The value of the last byte of each byte. Because radix sort is not limited to strings but can also be used on bytes, a flag is needed to identify each byte or what byte the string ends in. By default strings usually end with ‘\0’, so this argument is passed 0 for regular strings.

Return :[out] Returns whether the sort was successful or not, 0 on success, otherwise otherwise.

Function:

1. Radix sort can sort only byte array, but not arbitrary data structure, so its sort has some limitations. The time complexity of radix sort is O(N*D), where D refers to the length of the longest byte string to be sorted, so radix sort is almost linear time.
2. The table table in radix sort determines the order and result of radix sort. The weight value of each byte encoding expressed in this table. Since bytes are encoded from 0 to 255, the default weight value for each byte is equal to the code value, indicating that the bytes will be sorted in ascending order according to the size of the code.
3. Radix sort is classified into stable version and unstable version, the difference between the two is that when the value is the same, the position will not be changed. One drawback of the stable version of radix sort is that it can double the amount of extra memory allocated.

Example code 1:

void main()
{
   char *arr[6] = {"Bob"."Max"."Alice"."ada"."lucy"."Lili"}; Radixsort (arr, sizeof(arr)/sizeof(char*), NULL,'\ 0'); // Create a table with the order of gravity from large to small. unsigned char table1[UCHAR_MAX + 1] = {0};for(int i = 0; i < UCHAR_MAX + 1; i++) table1[i] = UCHAR_MAX - i; Radixsort (arr, sizeof(arr)/sizeof(char*), table1,'\ 0'); // In case insensitive ascending order, you need to build a table and set the proportion of uppercase letters and lowercase letters to be the same. Because the sorting content above is only the letter symbol so you only need to change the weight value of the letter symbol position. unsigned char table2[UCHAR_MAX + 1] = {0};for (int i = 'A'; i <='Z'; i++) { table2[i] = i; table2[i+32] = i; // The lower case proportion is set to the same as the upper case proportion. } radixsort(arr, sizeof(arr)/sizeof(char*), table2,'\ 0');
}

Copy the code

Example code 2:

Although radix sort is normally only used to sort arrays of bytes, if the bytes are members of a structure, we expect the entire structure to sort as well. In this case, we need to carry out the special design of the structure. We need to set the first data member of the structure as a byte array to implement the structure to apply radix sort. The specific code is as follows:

// Sort the structure. Requires a string as the first member of a structure, and the string members must be arrays, not string Pointers. typedef struct student { char name[16]; // The string in the structure must be defined as an array and be the first data member. int age; }student_t; student_t *a1 = malloc(sizeof(student_t)); strcpy(a1->name,"Bob");
    a1->age = 10;
    
    student_t *a2 = malloc(sizeof(student_t));
    strcpy(a2->name, "Jone");
    a2->age = 15;
    
    student_t *a3 = malloc(sizeof(student_t));
    strcpy(a3->name, "Alice");
    a3->age = 12;
    
    student_t *a4 = malloc(sizeof(student_t));
    strcpy(a4->name, "Tom");
    a4->age = 12;
    
    student_t *a5 = malloc(sizeof(student_t));
    strcpy(a5->name, "Lucy");
    a5->age = 8;
    
    student_t *a6 = malloc(sizeof(student_t));
    strcpy(a6->name, "Lily");
    a6->age = 18;
    
    student_t *arr[6] = {a1,a2,a3,a4,a5,a6};
    radixsort(arr, 6, NULL, '\ 0'); 

Copy the code