catalogue

1. Introduction to qsort function

2. Application of qsort function

3. How to write qsort function

 1. Introduction to qsort function

First, a detailed explanation of qsort function on msdn is attached

 

void qsort(void* base, 
	       size_t num, //Number of elements to be sorted
	       size_t width, //The size of an element in bytes
	       int(* cmp)(const void* e1, const void* e2) //cmp refers to the function used to compare two elements when sorting
);

The qsort function contains the above parameters. base is what we need to sort (such as array). You can say that the first element of the array is used as a parameter, num is the number of elements to be sorted, width is the size of elements to be sorted, and finally a function to compare the methods of two elements. You may think it is very abstract, Let's use a few examples to help you understand this function in depth.

2. Application of qsort function

Here we first introduce the return value principle of the function used for comparison in the qsort function

We assume compare ((void *) elem1, (void *) elem2);

If elem1 > elem2, a value > 0 is returned

Returns 0 if elem1==elem2

If elem1 < elem2, a value of < 0 is returned

int cmp_int(const void* e1, const void*e2)
{
	return *(int*)e1 - *(int*)e2;
}

void print_arr(int arr[], int sz)
{
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", arr[i]);
	}
}

void test1()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(arr[0]), cmp_int);
	print_arr(arr, sz);
}

int main()
{
test1();
return 0;
}

This is a code for sorting integer arrays from small to large

struct Stu
{
	char name[20];
	int age;
};

int cmp_by_name(const void*e1, const void*e2)
{
	return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
}

int cmp_by_age(const void* e1, const void* e2)
{
	return ((struct Stu*)e1)->age -((struct Stu*)e2)->age;
}

void test2()
{
	struct Stu s[3] = { {"zhangsan", 15}, {"lisi", 30},{"wangwu", 10}};

	int sz = sizeof(s) / sizeof(s[0]);

	//Sort by name
	//qsort(s, sz, sizeof(s[0]), cmp_by_name);

	//Sort by age
	qsort(s, sz, sizeof(s[0]), cmp_by_age);
}

int main()
{
test2();
return 0;
}

This is a code for sorting different members in a structure

Next, we introduce how to write our own general sorting function

3. How to write qsort function

We use callback functions to accomplish this

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++;
	}
}

//Use callback function to implement a general bubble sorting function

void BubbleSort(void* base, size_t num, size_t width, int (*cmp)(const void*, const void*))
{
	size_t i = 0;
	//Number of trips
	for (i = 0; i < num - 1; i++)
	{
		//Logarithm of comparison
		size_t j = 0;
		for (j = 0; j < num - 1 - i; j++)
		{
			if (cmp((char*)base+j*width, (char*)base+(j+1)*width)>0)
			{
				//exchange
				Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
			}
		}
	}
}

Here we imitate the parameter form of qsort function, and use the same parameters in our own functions.

Pay attention to the line indicated by the arrow. Here is the difficulty!!!

Because we write a general sorting function, we don't know the data type here. In order to better compare each element to be sorted, we use this method.

We forcibly convert the base to char * type, plus the loop variable J * width (the size of each element), which can ensure that each element is included, and skip one element after each loop, so as to avoid the omission of elements.

//Test the custom BubbleSort();
void test3()
{
	int arr[] = { 9,8,7,6,5,4,3,2,1,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	BubbleSort(arr, sz, sizeof(arr[0]), cmp_int);
	//Print
	print_arr(arr, sz);
}

//Test the custom BubbleSort() sort structure
void test4()
{
	struct Stu s[3] = { {"zhangsan", 15}, {"lisi", 30},{"wangwu", 10} };
	int sz = sizeof(s) / sizeof(s[0]);
	//Sort by name
	//BubbleSort(s, sz, sizeof(s[0]), cmp_by_name);

	//Sort by age
	BubbleSort(s, sz, sizeof(s[0]), cmp_by_age);
}

After we write this function, we can also complete our sorting goal like the above code.

For the complete code of this article, see c language / December 2021 10/2021.12. 10/test. c. Wu Changsheng / code - Code cloud - Open Source China (gitee.com)

This is the end of this article. Thank you for your reading. Welcome to praise and comment on each other. I wish you all the best.