coffee/varch
1
0
Fork 0
mirror of https://gitee.com/Lamdonn/varch.git synced 2025-12-06 08:46:42 +08:00
Code Issues Packages Projects Releases Wiki Activity
varch/doc/sort.en.md

364 lines
15 KiB
Markdown
Raw Permalink Blame History

### Introduction
Sorting is an important operation in computer programming. Its function is to rearrange an arbitrary sequence of data elements (or records) into a sequence ordered by keys. Sorting means arranging the elements in a collection in a certain order. Generally, there are two types of sorting: ascending order and descending order.
The logic of sorting algorithms is fixed. However, the structures of the data sets and data items to be sorted can be different. If a set of sorting algorithm functions is written for each data set structure or data item structure, it will undoubtedly increase redundant code.
The sort module provided by varch aims to solve this problem. It abstracts the differences in data set and data item types required by the algorithm model. As long as the corresponding operation functions are provided for different data and sorting rules, the sorting algorithm can be uniformly called for sorting operations.
### Interface
```c
int sort_bubble(void *array, int begin, int end, SOPS* ops);
int sort_select(void *array, int begin, int end, SOPS* ops);
int sort_insert(void *array, int begin, int end, SOPS* ops);
int sort_shell(void *array, int begin, int end, SOPS* ops);
int sort_quick(void *array, int begin, int end, SOPS* ops);
int sort_heap(void *array, int begin, int end, SOPS* ops);
```
Here, six commonly used sorting methods are provided, namely bubble sorting, selection sorting, insertion sorting, Shell sorting, quick sorting, and heap sorting. The usage of these sorting methods is consistent. The `array` parameter is used to pass in an array or any other data container, `begin` and `end` are used to specify the interval that needs to be sorted, and `ops` is used to specify a set of function operations required for sorting.
```c
/* Sorting algorithm operation function set structure definition */
typedef struct
{
/**
* \brief ordering rules, e.g front < back ascending and front > back descending
* \param[in] front: address of front data
* \param[in] back: address of back data
* \return positive: following sorting rules
* negative: violating sorting rules
* 0: does't affect sorting rules
*/
int (*order)(void *front, void *back);
/**
* \brief get the address of the space where the element is located
* \param[in] array: data handle
* \param[in] index: item data index
* \return address of item data
*/
void* (*addr)(void *array, int index);
/**
* \brief Swap data between two spaces
* \param[in] array: data handle
* \param[in] index0: item data index0
* \param[in] index1: item data index1
* \return none
*/
void (*swap)(void *array, int index0, index1);
} SOPS;
```
Firstly, in `ops`, the `order` member needs to specify the sorting rule (ascending or descending order). If the item of `front` is greater than the item of `back`, it is a descending order rule, and vice versa.
Since `array` supports data structures of any type, the `addr` member in `ops` needs to specify the method to obtain the address of a specific member of a specific data structure item. For example, the addresses returned for `char` arrays and `int` arrays are different.
Sorting involves exchanging the positions of data, and the `swap` member of `ops` specifies the method for exchanging data (because not all data structures exchange data by directly swapping the contents of the data. For example, for a linked list, it is sufficient to exchange the pointers to the data).
The `ops` for commonly used data structure sorting has been encapsulated. Just select the actual `ops` according to the type.
```c
extern SOPS sops_char_ascend;
extern SOPS sops_char_descend;
extern SOPS sops_uchar_ascend;
extern SOPS sops_uchar_descend;
extern SOPS sops_short_ascend;
extern SOPS sops_short_descend;
extern SOPS sops_ushort_ascend;
extern SOPS sops_ushort_descend;
extern SOPS sops_int_ascend;
extern SOPS sops_int_descend;
extern SOPS sops_uint_ascend;
extern SOPS sops_uint_descend;
extern SOPS sops_float_ascend;
extern SOPS sops_float_descend;
extern SOPS sops_double_ascend;
extern SOPS sops_double_descend;
```
### Actual Test Examples
#### Basic Usage of Ascending and Descending Order Sorting
For the ascending and descending order sorting of basic data types, take the bubble sorting algorithm as an example.
```c
static void test_basic_usage(void)
{
/* For an int-type array, perform ascending order sorting */
int array_int[] = {1, 3, 6, 5, 0, 2, 9, 8, 7, -4}; // Arbitrary disordered when defined
// Pass in the base address of the array, the sorting interval, and specify the ascending order ops for the int type
sort_bubble(array_int, 0, sizeof(array_int)/sizeof(array_int[0]) - 1, &sops_int_ascend);
// Output the sorted array
for (int i = 0; i < sizeof(array_int)/sizeof(array_int[0]); i++)
{
printf("%d, ", array_int[i]);
}
printf("\r\n");
/* ---------------------------------------- Code divider ---------------------------------------- */
/* For a float-type array, perform descending order sorting */
float array_float[] = {-1.1, 2.1, 6.6, 5.0, 0.1, 2.8, 9.9, 9.8, 7.0, -4.5}; // Arbitrary disordered when defined
// Pass in the base address of the array, the sorting interval, and specify the descending order ops for the float type
sort_bubble(array_float, 0, sizeof(array_float)/sizeof(array_float[0]) - 1, &sops_float_descend);
// Output the sorted array
for (int i = 0; i < sizeof(array_float)/sizeof(array_float[0]); i++)
{
printf("%.2f, ", array_float[i]);
}
printf("\r\n");
}
```
**Test Results**:
```
-4, 0, 1, 2, 3, 5, 6, 7, 8, 9,
9.90, 9.80, 7.00, 6.60, 5.00, 2.80, 2.10, 0.10, -1.10, -4.50,
```
#### Sorting for a Specified Interval
Besides the common sorting for the entire interval, sorting within a certain specified interval can also be performed.
```c
static void test_interval(void)
{
int array_int[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; // First define an ascending order array
// Pass in the base address of the array, specify the sorting interval as [3, 7], and specify the descending order ops for the int type
sort_bubble(array_int, 3, 7, &sops_int_descend);
// Output the sorted array
for (int i = 0, i < sizeof(array_int)/sizeof(array_int[0]); i++)
{
printf("%d, ", array_int[i]);
}
printf("\r\n");
}
```
**Test Results**:
```
0, 1, 2, 7, 6, 5, 4, 3, 8, 9,
```
#### Sorting for Containers Other Than Arrays
The following takes the list container as an example to test the ascending order sorting of an int-type list. This test code depends on the `list` container.
```c
// Get the address of the list data item
static void* list_int_addr(void *array, int index)
{
return list_data((list_t)array, index);
}
// Swap the data of two members in the list
static void list_int_swap(void *array, int index0, int index1)
{
int temp = list_at((list_t)array, int, index0);
list_at((list_t)array, int, index0) = list_at((list_t)array, int, index1);
list_at((list_t)array, int, index1) = temp;
}
// Display the data stored in the list
static void list_int_show(list_t list)
{
for (int i = 0; i < list_size(list); i++)
{
printf("%d, ", list_at(list, int, i));
}
printf("\r\n");
}
static void test_list_sort(void)
{
list_t list = list(int); // Define an int-type list
SOPS ops; // Define a new ops
int array[] = {1, 3, 6, 5, 0, 2, 9, 8, 7, -4}; // Define the data to be loaded into the list
// Load the data into the list
for (int i = 0; i < sizeof(array)/sizeof(array[0]); i++)
{
list_push_back(list, &array[i]);
}
ops.order = sops_int_ascend.order; // Reuse the ascending order rule for int
ops.addr = list_int_addr; // Use the method to obtain the element address for the list
ops.swap = list_int_swap; // Use the method to swap data in the list
// Output the list before sorting
list_int_show(list);
// Perform sorting
sort_bubble(list, 0, list_size(list) - 1, &ops);
// Output the list after sorting
list_int_show(list);
// Release the list
_list(list);
}
```
**Test Results**:
```
1, 3, 6, 5, 0, 2, 9, 8, 7, -4,
-4, 0, 1, 2, 3, 5, 6, 7, 8, 9,
```
#### Sorting for Custom Data Structures
The previous examples provided are for basic data types. The following example is for custom data structures, such as structures, and sorting is performed according to certain member items of the structure.
```c
typedef struct
{
char *name;
int age;
char gender; /* 1 represents male, 0 represents female */
float weight;
} STUDENT;
static void student_print(STUDENT *s, int size)
{
for (int i = 0; i < size; i++)
{
printf("name: %s, \t\t age = %d, \t\t gender = %d, \t\t weight = %.2f\r\n", s[i].name, s[i].age, s[i].gender, s[i].weight);
}
}
static void* student_addr(void *array, int index)
{
return ((STUDENT *)array) + index;
}
static void student_swap(void *array, int index0, int index1)
{
STUDENT temp = ((STUDENT *)array)[index0];
((STUDENT *)array)[index0] = ((STUDENT *)array)[index1];
((STUDENT *)array)[index1] = temp;
}
static int student_name_ascend(void *front, void *back)
{
return -strcmp(((STUDENT *)front)->name, ((STUDENT *)back)->name);
}
static int student_gender_descend(void *front, void *back)
{
if (((STUDENT *)front)->gender > ((STUDENT *)back)->gender) return 1;
else if (((STUDENT *)front)->gender < ((STUDENT *)back)->gender) return -1;
else return 0;
}
static int student_age_descend(void *front, void *back)
{
if (((STUDENT *)front)->age > ((STUDENT *)back)->age) return 1;
else if (((STUDENT *)front)->age < ((STUDENT *)back)->age) return -1;
else return 0;
}
static int student_weight_ascend(void *front, void *back)
{
if (((STUDENT *)front)->weight < ((STUDENT *)back)->weight) return 1;
else if (((STUDENT *)front)->weight > ((STUDENT *)back)->weight) return -1;
else return 0;
}
static void test_struct(void)
{
SOPS ops;
STUDENT table[] = {
{"ZhanSan", 18, 1, 56.3},
{"LiSi", 17, 1, 62.2},
{"WangWu", 21, 0, 58.9},
{"ZhaoLiu", 22, 1, 65.5},
{"SunQi", 18, 1, 71.7},
{"ZhouBa", 30, 0, 48.8},
{"WuJiu", 16, 1, 56.3},
{"ZhenShi", 19, 0, 52.1},
};
ops.addr = student_addr;
ops.swap = student_swap;
// Specify sorting in ascending order by name
ops.order = student_name_ascend;
sort_bubble(table, 0, sizeof(table)/sizeof(table[0])-1, &ops);
printf("sorting by name in ascending order\r\n");
student_print(table, sizeof(table)/sizeof(table[0]));
printf("---------------------------------\r\n");
// Specify sorting in descending order by age
ops.order = student_age_descend;
sort_bubble(table, 0, sizeof(table)/sizeof(table[0])-1, &ops);
printf("sorting by age in descending order\r\n");
student_print(table, sizeof(table)/sizeof(table[0]));
printf("---------------------------------\r\n");
// Specify sorting in descending order by gender
ops.order = student_gender_descend;
sort_bubble(table, 0, sizeof(table)/sizeof(table[0])-1, &ops);
printf("sorting by gender in descending order\r\n");
student_print(table, sizeof(table)/sizeof(table[0]));
printf("---------------------------------\r\n");
// Specify sorting in ascending order by weight
ops.order = student_weight_ascend;
sort_bubble(table, 0, sizeof(table)/sizeof(table[0])-1, &ops);
printf("sorting by weight in ascending order\r\n");
student_print(table, sizeof(table)/sizeof(table[0]));
printf("---------------------------------\r\n");
}
```
**Test Results**:
```
sorting by name in ascending order
name: LiSi, age = 17, gender = 1, weight = 62.20
name: SunQi, age = 18, gender = 1, weight = 71.70
name: WangWu, age = 21, gender = 0, weight = 58.90
name: WuJiu, age = 16, gender = 1, weight = 56.30
name: ZhanSan, age = 18, gender = 1, weight = 56.30
name: ZhaoLiu, age = 22, gender = 1, weight = 65.50
name: ZhenShi, age = 19, gender = 0, weight = 52.10
name: ZhouBa, age = 30, gender = 0, weight = 48.80
---------------------------------
sorting by age in descending order
name: ZhouBa, age = 30, gender = 0, weight = 48.80
name: ZhaoLiu, age = 22, gender = 1, weight = 65.50
name: WangWu, age = 21, gender = 0, weight = 58.90
name: ZhenShi, age = 19, gender = 0, weight = 52.10
name: ZhanSan, age = 18, gender = 1, weight = 56.30
name: SunQi, age = 18, gender = 1, weight = 71.70
name: LiSi, age = 17, gender = 1, weight = 62.20
name: WuJiu, age = 16, gender = 1, weight = 56.30
---------------------------------
sorting by gender in descending order
name: ZhaoLiu, age = 22, gender = 1, weight = 65.50
name: ZhanSan, age = 18, gender = 1, weight = 56.30
name: SunQi, age = 18, gender = 1, weight = 71.70
name: LiSi, age = 17, gender = 1, weight = 62.20
name: WuJiu, age = 16, gender = 1, weight = 56.30
name: WangWu, age = 21, gender = 0, weight = 58.90
name: ZhenShi, age = 19, gender = 0, weight = 52.10
name: ZhouBa, age = 30, gender = 0, weight = 48.80
---------------------------------
sorting by weight in ascending order
name: ZhouBa, age = 30, gender = 0, weight = 48.80
name: ZhenShi, age = 19, gender = 0, weight = 52.10
name: ZhanSan, age = 18, gender = 1, weight = 56.30
name: WuJiu, age = 16, gender = 1, weight = 56.30
name: WangWu, age = 21, gender = 0, weight = 58.90
name: LiSi, age = 17, gender = 1, weight = 62.20
name: ZhaoLiu, age = 22, gender = 1, weight = 65.50
name: SunQi, age = 18, gender = 1, weight = 71.70
---------------------------------
```
Reference in New Issue View Git Blame Copy Permalink