C language: qsort library function implementation (arbitrary type array sorting) [implementation + understanding]

The qsort function is a C Standard Library - <stdlib.h> The next function, the following is the implementation process of the qsort library function. (Not a definition in the standard library, just to help understand)

We know that the qsort function requires four values ​​when used

For example: qsort ( arr, sizeof(arr)/sizeof(arr[0]) , sizeof(arr) , own arithmetic function)

1: The first address of the array.

2: The number of array elements.

3: The number of bytes occupied by a single element.

4: The algorithm defined by yourself. (We know that qsort is the sorting of any type of array, we must know the type of the array to be sorted, then we need to "tell" the qsort function the type of the elements we are comparing)

The following is an understanding of the implementation of the qsort function:

-------------------------------------------------------------------------------------------------------------------------------

#include <string.h>

void swap(char* arr1,char*arr2,int length)
{
	int i;
	for (i = 0; i < length; i++)
	{
		char tmp = *(arr1 + i);
		*(arr1+i) = *(arr2 + i);
		*(arr2 + i) = tmp;
	}
}

void my_qsort(void* arr, int sz, int length, int (*contrast)(void* x,void* y)) //The fourth element is of type int because the function pointed to by this pointer returns a value of type int.
{
	int i, j;
	for (i = 0; i < sz; i++)
	{
		for (j = 0; j < sz-1-i; j++)
		{
			if (contrast((char*)arr + j*length, (char*)arr + (j+1)*length) > 0) //contrast is a function, and the function address can be used directly as the function name. The essence of the function name is actually the function address.
			{
				swap((char*)arr + j*length, (char*)arr + (j+1)*length,length);
			}
		}
	}
}


int contrast_int(void* x, void* y)
{
	return *(int*)x - *(int*)y;
}

int main()
{
	int arr[] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
	int sz = sizeof(arr) / sizeof(arr[0]);
	my_qsort(arr, sz, sizeof(arr[0]), contrast_int);
	return 0;
}

The above is the implementation of the function of the int element type, but we know that the qsort function is for any type, and the implementation function can naturally do it. The following is the string ordering in the structure.

#include <string.h>

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

void swap(char* arr1,char*arr2,int length)
{
	int i;
	for (i = 0; i < length; i++)
	{
		char tmp = *(arr1 + i);
		*(arr1+i) = *(arr2 + i);
		*(arr2 + i) = tmp;
	}
}

void my_qsort(void* arr, int sz, int length, int (*contrast)(void* x,void* y)) //The fourth element is of type int because the function pointed to by this pointer returns a value of type int.
{
	int i, j;
	for (i = 0; i < sz; i++)
	{
		for (j = 0; j < sz-1-i; j++)
		{
			if (contrast((char*)arr + j*length, (char*)arr + (j+1)*length) > 0) //contrast is a function, and the function address can be used directly as the function name. The essence of the function name is actually the function address.
			{
				swap((char*)arr + j*length, (char*)arr + (j+1)*length,length);
			}
		}
	}
}



int contrast_str(const void* x,const  void* y)
{
	return strcmp(((struct bbb*)x)->name, ((struct bbb*)y)->name);
}


int main()
{
	struct bbb ppp[3] = { { "cc", 10 }, { "bb", 20 }, { "aa", 30 } };
	int szppp = sizeof(ppp) / sizeof(ppp[0]);
	my_qsort(ppp, szppp, sizeof(ppp[0]), contrast_str);
	return 0;
}

For the convenience of understanding, this time, the array sorting of integer types is explained through the first one.

int main()
{
    int arr[] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };  
    int sz = sizeof(arr) / sizeof(arr[0]);
    my_qsort(arr, sz, sizeof(arr[0]), contrast_int);

// This is our implementation of the qsort function. We can see that there is a contrast_int, which is the contrast rule we want to enter
    return 0;
}

void my_qsort(void* arr, int sz, int length, int (*contrast)(void* x,void* y))

//Why void type? Because void* pointers can contain all types of addresses.

//The fourth element is of type int because the function pointed to by this pointer returns a value of type int.

{
    int i, j;
    for (i = 0; i < sz; i++)
    {
        for (j = 0; j < sz-1-i; j++)
        {
            if (contrast((char*)arr + j*length, (char*)arr + (j+1)*length) > 0)

//contrast is a function, the function address can be used directly as the function name, the essence of the function name is actually the function address.

//Why cast to char* type?

// char* with length (the number of bytes occupied by a single element) can jump elements.

//For example, int*, char* and other pointer types, its meaning is not just as superficial as the storage address, but more importantly, when dereferencing or self-incrementing, it can jump bytes, such as int can jump four Byte, char can jump one byte.
            {
                swap((char*)arr + j*length, (char*)arr + (j+1)*length,length);
            }
        }
    }
}
 

void swap(char* arr1,char*arr2,int length)

//Replace function, realize the replacement between two elements through char* and length
{
    int i;
    for (i = 0; i < length; i++)
    {
        char tmp = *(arr1 + i);
        *(arr1+i) = *(arr2 + i);
        *(arr2 + i) = tmp;
    }
}

Here's what the above code looks like:

 

 

Tags: C++ Algorithm C programming language

Posted by ankrah on Mon, 24 Oct 2022 16:37:17 +1030