[advanced pointer III] implement C language quick sorting function qsort & callback function

0. Classic quick sort algorithm -Quick_sort

First, let's implement it manually Quick_sort Sorting function

#include<stdio.h>
void Swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

void Quick_sort(int* arr, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	int keyi = begin;
	int left = begin, right = end;
	while (left < right)
	{
		while (left < right && arr[right] >= arr[keyi])
		{
			right--;
		}
		while (left < right && arr[left] <= arr[keyi])
		{
			left++;
		}
		Swap(&arr[left], &arr[right]);
	}
	int meeti = left;
	Swap(&arr[keyi], &arr[meeti]);

	Quick_sort(arr, begin, meeti-1);
	Quick_sort(arr, meeti+1, end);
	
}

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

int main()
{
	int arr[5] = { 12,43,5,23,6 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	Quick_sort(arr, 0,sz-1);
	Print(arr, sz);
	return 0;
}

Sorting result ：

 

 

But there is a problem : If next time I want to sort a structure , My changes to this sorting algorithm will be very big （ Almost everything has been changed ）, Below I also give the corresponding code implementation of the sorting structure , Let me show you .

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

void Swap(stu* a,stu* b)
{
	stu temp = *a;
	*a = *b;
	*b = temp;
}

void Quick_sort(stu* ps, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}
	int keyi = begin;
	int left = begin, right = end;
	while (left < right)
	{
		while (left < right && strcmp(ps[right].name, ps[keyi].name) >= 0)
		{
			right--;
		}
		while (left < right && strcmp(ps[left].name, ps[keyi].name) <= 0)
		{
			left++;
		}
		Swap(&ps[left], &ps[right]);
	}
	int meeti = left;
	Swap(&ps[keyi], &ps[meeti]);

	Quick_sort(ps, begin, meeti - 1);
	Quick_sort(ps, meeti+1, end);
}

void Print(stu* ps, int sz)
{
	for (int i = 0; i < sz; i++)
	{
		printf("%s\n", ps[i].name);
	}
}

int main()
{
	stu s[3] = { {" Zhang San ",18},{" Li Si ",20},{" Wang Wu ",19} };
	int sz = sizeof(s) / sizeof(s[0]);
	Quick_sort(s,0,sz-1);
	Print(s, sz);
	return 0;
}

Sorting result ：

 

  So we thought ： Can you design a function to add sorting functions when sorting elements of different data types Quick_sort Reusability of code , therefore , Library function qsort emerge as the times require , What does this function look like ？

1. qsort Basic introduction of sorting function

qsort The sort function is C Functions in the language standard library , The implementation principle is a quick sort algorithm , The function prototype is as follows :

 qsort Introduction and significance of the relevant parameters of the function :

• The header file : #include<stdlib.h>
• Return value : nothing
• void  base: The starting address of the data element to be sorted
• size_t num:  The number of data elements to be sorted
• size_t width: The size of data elements to be sorted , Unit is byte
• int( * cmp)(const void*,const void*): A function pointer - A function that compares the size of data elements , Sort by

for instance : 

#include<stdio.h>
#include<stdlib.h>
// With qsort The library function implements integer array sorting as an example 
int main()
{
	int arr[5] = { 12,43,5,23,6 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(arr[0]), cmp);
	//arr: Array name , It is also the address of the first element of the array , Numerically equal to... In the first element 4 The address of the byte with the lowest address in the bytes 
	//sz: Array arr Number of elements of 
	//sizeof(arr[0]): The number of bytes each array element occupies 
	//cmp_int: Callback function - Functions that compare array elements , It is implemented according to the needs of the caller 
	Print(arr, sz);
	return 0;
}

Throw it first qsort The specific implementation of the function will not be discussed , See here , You will know qsort The flexibility of the function lies in the fourth parameter （ Comparison function ） It can be designed according to the specific sorting requirements of users .

2. Comparison function

Design examples of comparison functions ： integer array , Structure array and so on

Integer array sort ：（ All the code ）

Worry about the calling relationship between functions ： Give you a picture to understand

 

#include<stdio.h>
#include<stdlib.h>

int cmp_int(const void* e1, const void* e2)
{
    // Compare two integer elements 
	//void* Is a pointer without a specific type 
	//void* Can receive any type of address , Like a trash can 
	//void* The pointer to has no specific type , You can't +1-1( Because I don't know how much to add )

	// Ascending :
	return *(int*)e1 - *(int*)e2;

	// Descending :
	//return *(int*)e2 - *(int*)e1;
}


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

void test1()
{
	int arr[6] = { 14,35,4,42,6,12 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(&arr[0], sz, sizeof(arr[0]), cmp_int);
	Print(arr, sz);
}


int main()
{
	test1();

	return 0;
}

because void Null pointer ：

• Can receive any type of pointer
• You cannot add or subtract integers directly , It needs to be forced to turn before use  

because cmp The comparison function needs to be designed by the user , So for different users in qsort Function passed to cmp The argument type of a function can be any type of pointer , So in cmp The comparison function uses void* Type to receive , When using, just put void* The pointer of type can make corresponding strong conversion .

Sorting result ：

 

 

Structure array sort ：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

typedef struct stu
{
	char name[20];
	int age;
}stu;

int cmp_struct_by_name(const void* e1, const void* e2)
{
	return strcmp(((stu*)e1)->name, ((stu*)e2)->name);// Wonderful place 
}

void Print(stu* ps, int sz)
{
	for (int i = 0; i < sz; i++)
	{
		printf("%s\n", ps[i].name);
	}
}


void test2()
{
	stu s[3] = { {"zhangsan",18},{"lisi",20},{"wangwu",19} };
	int sz = sizeof(s) / sizeof(s[0]);
	qsort(s,sz,sizeof(s[0]),cmp_struct_by_name);
	Print(s, sz);
}

int main()
{
	test2();

	return 0;
}

Sorting result ：

Compare strings with strcmp function , The header file #include<string.h> 

• Wonderful place ：strcmp Compare the function with the specified cmp The return value of the comparison function has the same meaning
• Return value >0             elem1>elem2
• Return value ==0           elem1==elem2
• Return value <0             elem1<elem2

 2. qsort The concrete realization of function

Study qsort The concrete realization of function , You will learn this C Another wonderful thing about library functions .

void Swap(char* buff1,char* buff2,int width)
{
	if (buff1 != buff2)
	{
		//way1
		//while (width--)
		//{
		//	char temp = *buff1;
		//	*buff1 = *buff2;
		//	*buff2 = temp;
		//	buff1++;
		//	buff2++;
		
		//way2
		for (int i = 0; i < width; i++)
		{
			char temp = *(buff1+i);
	        *(buff1+i) = *(buff2+i);
	        *(buff2+i) = temp;
		}
	}
}

void bubble_sort(void* base, int sz, int width, int(*cmp)(const void*, const void*))
{
	int flag = 1;
	// Number of trips 
	for (int i = 0; i < sz-1; i++)
	{
		for (int j = 0; j < sz - 1 - i; j++)
		{
			if (cmp_struct_by_name((char*)base + j * width, (char*)base + (j+1) * width)>0)
			{
				Swap((char*)base + j * width, (char*)base + (j+1) * width, width);
				flag = 0;
			}
		}
		if (flag == 1) break;
	}
}

The trick is to take the actual parameters void* Type of base The pointer turns to char* type .

analogy int arr[5]={34,5,35,62,1};
Print(arr,5), there arr In fact, it is the address of the first element , And the first element in number 4 The address of the lowest of the bytes is the same , therefore cmp The arguments to a function are even char* One byte address , stay cmp Function can also be forcibly converted to the required type , To dereference , Get the corresponding number of bytes for comparison , In this way, we can achieve in bubble_sort Get unified in the function , So whether we want to sort any type of data , Can be called directly bubble_sort function , Just change cmp Function , This increases bubble_sort Reusability of function code .