[C language] qsort function

---

Preface

qsort Function is a quick sort among the eight sorting algorithms , Can sort arrays of any data type , Including the implementation of integer , floating-point , Structure , Sorting of strings .

One 、qsort The function prototype

The header file ：#include<stdio.h>

void qsort(void* base,// Address of the first element of the data to be sorted 
	       int num,// Number of data to sort 
	       int width,// The byte size of the element 
	       void(*cmp)(const void* e1, const void* e2));// A function pointer - Receive comparison function , The comparison function needs to be implemented by ourselves 

About why to use void* The pointer ： First of all, make it clear void** Is a pointer without a specific type , Can accept any type of address , and qsort Function can sort various types of data , So we use null pointers to accept addresses . It should be noted that the null pointer has no definite step size , So null pointers cannot add or subtract integers , Null pointers cannot be dereferenced .

Two 、

1.qsort Function to realize integer sorting

(1) Ascending

#include<stdio.h>
#include<stdlib.h>
// Integer comparison function 
int cmp_int(const void* e1, const void* e2)
{
    
	return *(int*)e1 - *(int*)e2;
}
int main()
{
    
	int arr[] = {
     9,8,7,6,5,4,3,2,1,0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	//qsort The use of library functions 
	qsort(arr, sz, sizeof(arr[0]), cmp_int);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
    
		printf("%d ", arr[i]);
	}
	return 0;
}

(2) Descending

#include<stdio.h>
#include<stdlib.h>
int cmp_int(const void* e1, const void* e2)
{
    
	return *(int*)e2 - *(int*)e1;// The latter element is larger than the former , Just exchange 
}
int main()
{
    
	int arr[] = {
     0,1,2,3,4,5,6,7,8,9,10 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	qsort(arr, sz, sizeof(arr[0]), cmp_int);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
    
		printf("%d ", arr[i]);
	}
	return 0;
}

2.qsort Function to sort the structure

(1) Sort by age

#include<stdio.h>
#include<stdlib.h>
// Define the structure type 
struct Stu
{
    
    // Structural members 
	int age;
	char name[20];
};
int cmp_stu_by_age(const void* e1, const void* e2)
{
       
    // need e1 Need parentheses , To access the structure data 
	return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}
int main()
{
    
	struct Stu s[] = {
     {
    30,"lisi"},{
    20,"wangwu"},{
    10,"zhangsan"} };
	int sz = sizeof(s) / sizeof(s[0]);
	qsort(s, sz, sizeof(s[0]), cmp_stu_by_age);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
    
		printf("%d %s\n", s[i].age, s[i].name);
	}
	return 0;
}

(2) Sort by first name

#include<stdio.h>
#include<stdlib.h>
struct Stu
{
    
	int age;
	char name[20];
};
int cmp_stu_by_name(const void* e1, const void* e2)
{
    
    // String comparison with strcmp
	return strcmp(  ((struct Stu*)e1)->name, ((struct Stu*)e2)->name  );
}
int main()
{
    
	struct Stu s[] = {
     {
    30,"lisi"},{
    20,"wangwu"},{
    10,"zhangsan"} };
	int sz = sizeof(s) / sizeof(s[0]);
	qsort(s, sz, sizeof(s[0]), cmp_stu_by_name);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
    
		printf("%d %s\n", s[i].age, s[i].name);
	}
	return 0;
}

---

3、 ... and . Bubble sort algorithm simulation implementation qsort function

（1） Sort integers

#include<stdio.h>
// Comparison function 
int cmp_int(const void* e1, const void* e2)
{
    
	return *(int*)e1 - *(int*)e2;
}
// Exchange in bytes 
void Swap(char* buf1, char* buf2, int width)// Swap in bytes 
{
    
	int i = 0;
	for (i = 0; i < width; i++)
	{
    
		char temp = *buf1;
		*buf1 = *buf2;
		*buf2 = temp;
		buf1++;
		buf2++;
	}
}
void bubble_sort(char* base, int sz, int width, int(*cmp)(int, int))
{
    
	int i = 0;
	int j = 0;
	int flag = 0;
	for (i = 0; i < sz - 1; i++)
	{
    
		flag = 1;
		for (j = 0; j < sz - 1 - i; j++)
		{
    
		    // Force type to char* type 
			if (cmp_int((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;
		}
	}
}
int main()
{
    
	int arr[] = {
     1,3,5,7,9,2,4,6,8,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;
}

（2） Sort floating point number

#include<stdio.h>
float cmp_float(const void* e1, const void* e2)
{
    
	return *(float*)e1 - *(float*)e2;
}
void Swap(char* buf1, char* buf2, int width)// Swap in bytes 
{
    
	int i = 0;
	for (i = 0; i < width; i++)
	{
    
		char temp = *buf1;
		*buf1 = *buf2;
		*buf2 = temp;
		buf1++;
		buf2++;
	}
}
void bubble_sort(void* base, int sz, int width, int(*cmp)(void*, void*))
{
    
	int i = 0;
	int j = 0;
	int flag = 0;
	for (i = 0; i < sz - 1; i++)
	{
    
		flag = 1;
		for (j = 0; j < sz - 1 - i; j++)
		{
    
			if (cmp_float((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;
		}
	}
}
int main()
{
    
	float arr[] = {
     9.0,8.0,7.0,6.0,5.0,4.0,3.0,1.1,1.0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	int i = 0;
	bubble_sort(arr, sz, sizeof(arr[0]), cmp_float);
	for (i = 0; i < sz; i++)
	{
    
		printf("%.1f ", arr[i]);
	}
	return 0;
}