catalogue

1, Simple bubble sort

1.1 meaning of bubble sorting

1.2 bubble sorting two steps

1.3 complete code

2, qsort function implementation

2.1qsort function analysis

2.2qsort function to sort structure types

2.3 implementation of qsort by user-defined functions

Third, callback function

1, Simple bubble sort

1.1 meaning of bubble sorting

The so-called bubble sorting, that is, the number is large, and this number rises like bubbles. So today, let's take a look at the specific implementation process. In order to facilitate the subsequent learning of qsort function, the bubble sorting program here is a little more complex.

First, we only use integer data for bubble sorting, so we use integer array. The function only needs to pass the array name and the number of array elements. Then, the main function implementation part is analyzed as follows:

1.2 bubble sorting in two steps

First, we sort in two steps. In the first step, we start from the first element of the array and compare it with the elements behind the first element. If the former element is larger than the latter element, we will exchange the positions of the two elements, otherwise, we will not change, and then compare the second and third elements in turn until all the elements of the group are compared, Change the last element of the array to the maximum number of this group.

This is the first step, and then the second step. After the first step, the last element is the maximum number, so there is no need to compare. At this time, you can narrow the troubleshooting scope to the array element minus one, and then carry out the first step. At this time, the next largest value is found, so keep looking until the first element of the array is the minimum value. This is the second step.

However, it should be noted that the judgment conditions in the first step can only be changed when the number in front is greater than that in the back. Secondly, it should be noted that after each sorting in step 2, the next table lookup element will be reduced by one bit. Here, the value of ， j should be subtracted from ， i.

1.3 complete code

#include<stdio.h>
void bubble_sort(int arr[],int sz)
{
	int i = 0;
	for (i = 0; i < sz - 1; i++)
	{
		int j = 0;
		for (j = 0; j < sz - 1 - i; j++)
 		{
			if (arr[j] > arr[j + 1])
			{
				int temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j+1] = temp;
			}
		}
	}
}
void print1(int arr[], int sz)
{
	int i = 0;
	int j = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ",arr[i]);
	}
}
int main()
{
	//int arr[10] = {0,1,2,3,4,5,6,7,8,9};
	int arr[10] = {9,8,7,6,5,4,3,2,1,0};
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr,sz);
	print1(arr,sz);
	return 0;
}

2, qsort function implementation

The first thing we need to know is that the qsort function is a bubble sort function. Therefore, the internal qsort function can help us realize many functions, but we know that since it is sorting, it cannot be just integer data. Of course, it may be floating-point, character and structure. Since it is not integer sorting, the above method must not work.

This is why we need to learn the qsort function, which can sort any type of data.

2.1qsort function analysis

Next, let's understand the basic format of this function:

//sort basic format
void qsort(void* base,
          size_t num, 
          size_t size,
	      int (*compar)(const void*, const void*));

As shown above, the parameter part of qsort function is divided into four parts. Next, we will interpret them one by one:

First, * void * base, that is, a pointer with a return type of void. The reason for setting the return value type to void is that there are many data types in reality. Setting void is convenient for us to cast when we need to use other types. Since this is a pointer, there can be many pointer types, which implements the concept that we can only implement integer pointers at the beginning of this article.  

In addition, the middle two parameters are the number of elements and the size of an element. Both are unsigned integers. Because the number and size of elements cannot be negative, size is used_ T = this unsigned integer.  

The last parameter is a function pointer. The function of this function is to compare the size of two elements. If the front one is greater than the back, it returns a number greater than 0. If it is equal, it returns a number equal to 0. If it is less than 0, it returns a number less than 0. Then, the qsort function determines whether to exchange the positions of the two elements according to the returned value type.

2.2qsort function to sort structure types

OK, after understanding its basic framework, let's write a sort of structure type elements:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct stu
{
	char name[10];
	int age;
};
int swap(const void* e1, const void*e2)
{
	return strcmp(((struct stu *)e1) ->name , ((struct stu*)e2) ->name);
}
int main()
{
	//The struct type is used in the qsort function
	struct stu s [3]= { {"zhangsan",29} ,{"lisi",26}, {"wangwu",30} };
	int num = sizeof(s) / sizeof(s[0]);
	qsort(s,num,sizeof(s[0]),swap);
	return 0;
}

As you can see here, we only need to pass parameters to qsort before implementing a specific exchange function. Of course, we can also compare ages here. Of course, we look at the sorting results in another way:

You can see that this is the result of sorting by name. Here is the result displayed through the debugging window.

2.3 the function of qsort realized by user-defined function

Because the qsort function can sort any type of data, we will customize this function according to the above qsort function implementation. The code is as follows:

#include<stdio.h>
#include<string.h>
struct stu
{
	char name[10];
	int age;

};
int cmp_sort_age(const void* x, const void* y)
{
	return ((struct stu*)x)->age - ((struct stu*)y)->age;
}
swap_cmp(char *buf1,char *buf2,int size)
{
    int i = 0;
	for (i = 0; i < size; i++)
	{
		char temp = *buf1;
		*buf1 = *buf2;
		*buf2 = temp;
		buf1++;
		buf2++;
	}
}
void q_sort(void * base, size_t num, size_t size, int (*cmp)(const void* ,const void*))
{
	size_t i = 0;
	size_t j = 0;
	for (i = 0; i < num-1; i++)
	{
		for (j = 0; j < num - 1 - i; j++)
		{
			if (cmp((char*)base + j * size, (char*)base + (j+1) * size) > 0)
				swap_cmp((char*)base + j * size, (char*)base + (j + 1) * size,size);
		}
	}
}
int main()
{
    struct stu s[3] = { {"zhangsan",34 },{"lisi",21},{"wangwu0",30} };
	int sz = sizeof(s) / sizeof(s[0]);
    //Sort by name
	//qsort(s,sz,sizeof(s[0]),cmp_sort_name);
	//Return value of strtmp function
	//Sort by age
	q_sort(s, sz, sizeof(s[0]), cmp_sort_age);
	return 0;
}

The first logic of this program is to customize the function Q after the structure is initialized_ Sort pass parameters in q_sort function internally implements the most basic cmp function. Compare two by two. At this time, cmp_ sort_ The age function returns whether the value of the comparison between two numbers is greater than 0. If so, swap is called_ cmp function exchanges the values of two variables, and finally completes the bubble sorting of the whole structure array by age.

What is not easy to understand here is the parameters of cmp function and swap_ Parameters of cmp function. The explanation is as follows:

Because the original function parameter is void *, the type must be forced to be converted to char type pointer first. Because char type is the smallest data type, any data can represent data in bytes in memory. Therefore, taking 1  byte as the minimum unit, the pointer plus  J  multiplied by  element size  size, and the other is  j+1  elements, representing the next bit element. That is, the size of two elements is compared. This is also swap_ Why does CMP function compare in char type.

As shown in the figure, the results are sorted by age:

Third, callback function

A callback function is a function called through a function pointer. If you pass the pointer (address) of a function as a parameter to another function, when the pointer is used to call the function it points to, we say it is a callback function. The callback function is not called directly by the implementer of the function, but by another party when a specific event or condition occurs, which is used to respond to the event or condition.

Therefore, if the function is not returned, the program will become very miscellaneous, and sometimes the function can not run.

So, guys, do you think the two go hand in hand? Welcome to leave a message for discussion!

That's all for today. Please correct any mistakes!! Thank you very much!!