C library function - qsort()

Statement:

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*))

Parameter Description:

base -- Pointer to the first element of the array to sort.
nitems -- from base The number of elements in the array pointed to.
size -- The size of each element in the array, in bytes.
compar -- A function used to compare two elements.

Description:
The library function qsort sorts the array

Callback callback function:

Callback function, just listen to the name is higher than ordinary functions. What is a callback function? There are different opinions on accessing information on the Internet.
But what impressed me most was what Baidu Encyclopedia said:

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 this pointer is used to call the function it points to, we say it is a callback function.

Let's take a look at the use of callback function and experience it. Here, take integer array sorting as an example.

//The callback function is as follows
//If x and Y meet the sorting requirements, it will return 1, and if not, it will return 0;
typedef int(*Cmp)(int x, int y);       //Cmp here is the type of function pointer

int less(int x, int y)
{
	//This function is used for ascending sort
	//If x is smaller than y, it meets the sorting requirements
	return x < y ? 1 : 0;
}
int greater(int x, int y)
{
	//Descending sort
	return x>y ? 1 : 0;
}

//Bubble sorting
void bubbleSort(int arr[], int len, Cmp cmp)
{
	for (int bubble = 0; bubble < len; bubble++)
	{
		for (int cur = len - 1; bubble < cur; cur--)
		{
			if (cmp(arr[cur], arr[cur - 1])==1)
			{
				int tmp = arr[cur];
				arr[cur] = arr[cur - 1];
				arr[cur - 1] = tmp;
			}
		}
	}
}

int main()
{
	int arr[] = { 8,3, 9, 5, 7, 4, 6 };
	int len = sizeof(arr) / sizeof(arr[0]);
	bubbleSort(arr, len,greater);
	for (int i = 0; i < len; ++i)
	{
		printf("% d\n", arr[i]);
	}
	return 0;
}

In this code, the pointer of the cmp function is passed into the bubble function as a parameter, and the pointer returns to call the cmp function as a condition for bubble sorting.
When we write code everyday, we can also meet the different needs of callers through callback functions, so as to achieve the purpose of one piece of code and multiple purposes. For example, in this example, the cmp function pointer implements two different sorting methods (ascending and descending).

Let's experience the use of callback function in structure Sorting:

//Create structure
typedef struct Student
{
	int id;
	char name[100];
	int score;
}Student;

// Declaration of comparison rules
typedef int(*CmpStudent)(Student* x, Student *y);       //Structure is implicitly converted to a pointer when a function is passed in

//Bubble sorting
void bubblesortStudent(Student arr[], int len, CmpStudent cmp)
{
	for (int bubble = 0; bubble < len; bubble++)
	{
		for (int cur = len - 1; cur>bubble; cur--)
		{
			if (cmp(&arr[cur], &arr[cur - 1]))      //Exchange if it meets the sorting requirements
			{
				Student tmp = arr[cur - 1];
				arr[cur - 1] = arr[cur];
				arr[cur] = tmp;
			}
		}
	}
}

//ID ascending
int cmpIdless(Student* x, Student* y)
{
	return x->id < y->id ? 1 : 0;
}
//ID descending order
int cmpIdgreater(Student* x, Student* y)
{
	return x->id > y->id ? 1 : 0;
}
//If the scores are the same, sort by id in ascending order
//If the scores are different, they are sorted in ascending order
int cmpScorelessAndIdless(Student* x, Student* y)
{
	if (x->score == y->score)
		return x->id < y->id ? 1 : 0;
	return x->score < y->score ? 1 : 0;
}

int main()
{
	Student students[] = 
	{
		{ 1, "Zhang San", 96 },
		{ 2, "Li Si", 90 },
		{ 3, "Wang Wu", 94 },
		{ 4, "Zhao Liu", 98 },
		{ 5, "Chen Qi", 94 },
	};
	int n = sizeof(students) / sizeof(students[0]);
	bubblesortStudent(students, n, cmpScorelessAndIdless);
	for (int j = 0; j < n; ++j)
	{
		printf("%s\n", students[j].name);
	}

	return 0;
}

Simulation of qsort

Idea:
According to the description, we know that qsort is used to sort arrays, so the question is, which arrays are there?
For our daily learning, most of them are integer array, character array, string array, structure array and so on.
How to make a function that can uniformly sort these different types of arrays?
In C language, the usage of generic programming is very limited. What we need to know here is to use void * to realize generic programming and achieve the purpose of multiple usage of functions.
Use the function pointer to form a callback function as the sorting condition. Then, our sorting function only needs to add this sorting condition and sort normally.

Let's try to merge the above two pieces of code into a common one:

//Create structure
typedef struct Student
{
	int id;
	char name[100];
	int score;
}Student

//             Generic programming through void * to simulate qsort


//Specify comparison rules
//Void * here is a general type. If it is a comparison shaping, void * here is assigned with int *
//If it is a comparison structure type, assign a value with student *
typedef int(*Cmp)(void*, void*);


//Here, len represents the number of array elements, and unitlen represents the size of each element
//Originally, the size of each element is contained in the type of element, but here we use void *,
//To support many different types of arrays, so the length of each element is manually specified by the programmer as needed
void bubbleSortGeneral(void* arr, int len, int unitlen,Cmp cmp)
{
	//void * cannot be dereferenced here, so we can't use arr[i] to get array elements. What should we do?

	for (int bound = 0; bound < len; bound++)
	{	
		//We need to force the type conversion of the array, which is uniformly converted to char *, and then calculated according to the calculation method of char		
		//If the array passed in is an integer array
		//Normal method: arr [cur-1] = = > arr + (cur-1) because - 1 here is minus one integer and four bytes
		//How to convert to char: arr [cur-1] = = > arr + (cur-1) * unitlen where - 1 is minus 1 char and 1 byte
		for (int cur = len - 1; cur>bound; cur--)
		{
			char* carr = (char*)arr;
			//p1 points to the first address of cur-1
			char* p1 = carr + (cur - 1)*unitlen;
			//p2 points to the first address of cur	
			char* p2 = carr + cur*unitlen;
			if (cmp(p1, p2) != 1)
			{
				//exchange
				//There must be a temporary space first
				char tmp[1024] = { 0 };
				//Exchange triple company
				memcpy(tmp, p1, unitlen);
				memcpy(p1, p2, unitlen);
				memcpy(p2, tmp, unitlen);
			}
		}
	}
}

//Comparison function
//Exchange rules for integer arrays
int cmpint(void* x, void* y)
{
	//Think of x and y as two int s *
	int* ix = (int*)x;
	int* iy = (int*)y;
	return ix < iy ? 1 : 0;
}
//Exchange rules of student structure
int cmpStudent(void* x,void* y)      //Score comparison
{
	Student* sx = (Student*)x;
	Student* sy = (Student*)y;
	return sx->score < sy->score ? 1 : 0;   //String sorting and character sorting are no longer enumerated
}

int main()
{
	int arr[] = { 8, 3, 9, 5, 7, 4, 6 };
	int len = sizeof(arr) / sizeof(arr[0]);
	bubbleSortGeneral(arr, len, sizeof(arr[0]),cmpint);


	Student students[] = {
		{ 1, "Zhang San", 96 },
		{ 2, "Li Si", 90 },
		{ 3, "Wang Wu", 94 },
		{ 4, "Zhao Liu", 98 },
		{ 5, "Chen Qi", 94 },
	};
	int n = sizeof(students) / sizeof(students[0]);
	bubbleSortGeneral(students->score, n, sizeof(students->score), cmpStudent);
	return 0;
}

In the above code, the algorithm we use to cast the array during the exchange process: char* p1 = carr + (cur - 1)*unitlen; What's going on? Look at the following figure:

When the type is int, if you want to get the nth number of the array, you can only use the array name + N, but after it is converted to char, the size of each element in the array is only 1 byte, and the address difference between integers is 4 bytes. We have no choice but to use the array name + (n size of each element)