Take you to quickly learn how to use qsort and simulate qsort

1. How to use qsort

qsort yes C A library function in language , The method of quick sorting .
Let's take a look at the standard library qsort Parameter type ：

void* base It's a pointer , It passes the starting position of the target array .
size_t num It means the number of array elements .
size_t size It means the size of each element ( Unit is byte ).
int ( * compar)(const void * ,const void * )) This is a function pointer . It points to a comparison function .
Let's take a look at the requirements of this comparison function ？

p1 The element pointed to is less than p2 The element pointed to returns a negative number .
p1 The element pointed to is equal to p2 The element pointed to returns 0.
p1 The element pointed to is greater than p2 The element pointed to returns a positive number .

Now let's take an example , Arrange an integer array ：

We need to compare p1,p2 Be sure to de quote , But here p1,p2 Can't directly dereference , Because it is
void * Of .
Let's say something void * Some characteristics of ：
void * Is a typeless pointer .
void * The pointer variable of can store any type of address .
void * The pointer of cannot be dereferenced directly .
void * The pointer of cannot be added directly , Minus integer .
therefore , We are using void * When , You should force the type to be converted to the type you want .
give the result as follows ：

Next , We'll use qsort To sort the structure array
We define a student structure ：

We sort by grades ：

Then we force the type to be converted into a structure pointer for comparison ：

The operation results are as follows ：

We can see that the grades are sorted from small to large .

Then we sort by name ：

Note here that the name comparison is a string , You should use strcmp To compare .

The operation results are as follows ：

Come here , We should all be able to use qsort Is that right . Next , We will simulate qsort.

2. simulation qsort

Let's explain these parameters first ：
first , Why void* , Because when sorting , We may pass integers , floating-point , Character , Structure type and so on , So we have to accept all kinds of types , Can only be void * .

the second , We must know how many elements to sort in the array .

Third , We need to know the size of an element , Otherwise , We don't know where to find the next element .

The fourth one , Like bubble sort , Our comparison times , The number of elements compared with each time will not change , Only our method of comparison is different . therefore , We should separate this comparison method , Become a separate function .

Now? , Let's use the idea of bubble sorting to simulate qsort.
First , We will write out what doesn't need to be changed in the bubble sort ：

Only when compared, it is different . How can we write a general comparison ？
First ,cmp A function pointer , What parameters should we pass ？ We need to compare two adjacent elements , So you should pass the address of two elements .
Let's pass it on base+j and base+j+1, OK? , no way . because base yes void * Of . We should cast the type to char * Of . because char * It can meet any type .
then , We'll use width To find each element .
(char*)base + j * width, (char*)base + (j + 1) * width)
When j=0 when , The first one finds the first element , The second one is to skip 4 Bytes found the second element .
When j=1 when , First skip 4 The second element is found in bytes , The second one is to skip 8 Bytes found the third element .
…

Found adjacent elements , We began to exchange . Use one Swap Function in exchange for ：

Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);

then , Let's realize this Swap function .
Because we are char*, So we need to exchange bytes one by one .

Complete code ：

#include <stdio.h>
void Swap(char* buf1, char* buf2, int width)
{
    
	int i = 0;
	for (i = 0; i < width; i++)
	{
    
		char tmp = *buf1;
		*buf1 = *buf2;
		*buf2 = tmp;
		buf1++;
		buf2++;
	}
}
 
int cmp_int(const void* e1, const void* e2)
{
    
	return *(int*)e1 - *(int*)e2;
}
void bubble_sort(void* base, int sz, int width, int(*cmp)(const void* e1, const void* e2))
{
    
	int i = 0;
	for (i = 0; i < sz - 1; i++)
	{
    
		int j = 0;
		for (j = 0; j < sz - 1 - i; j++)
		{
    
			if (cmp((char*)base + j * width, (char*)base + (j + 1) * width) > 0)
			{
    
				// The exchange of two elements 
				Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
			}
		}
	}
}

int main()
{
    
	int arr[] = {
     9,8,7,6,5,4,3,2,1,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	bubble_sort(arr, sz, sizeof(arr[0]), cmp_int);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
    
		printf("%d ", arr[i]);
	}
	return 0;
}

Summary ：

The main problem here is that we should look at it from different perspectives , As the creator of sorting , We don't know what sort array is . But users know .
Because the array types of comparison are various , The comparison method is different , So the creator of the method of comparing functions doesn't know , But users know . therefore , The user should pass the function address written by himself .
therefore cmp You can find the comparison function method written by the user , Then we pass the addresses of the two adjacent elements , Why cast the type to char*, Because char Type is the smallest type , It can be easily used to skip the same number of bytes .

summary ：

Come here , This article ends first . If you think I have any shortcomings or mistakes in knowledge, you can tell me , I will correct it in time , Please forgive me . If you find this article useful , I also hope you can give me some praise , Your support is my greatest encouragement , See you in the next article .