The Qsort function implements sorting of elements in various types of arrays (simple idea)

Table of Contents

Function introduction

Function use case:

(1) Sorting of int arrays

(2) Sorting of char array

(3) Sorting floating-point arrays

(4) Sorting of structure types

(5) Imitate the function of qsort to implement a general bubble sort

Function introduction

Function:Quickly sort the array elements in the pointed array

Header file: stdlib.h

Function prototype:void qsort (void* base, size_t num, size_t size, int (*compar)(const void*,const void*));

Parameter explanation:

  • base: Pointer to the first element of the array to be sorted
  • num: Number of elements in the array
  • size: size of each element (in bytes)
  • compar: Comparison function, used to determine the order relationship between two elements

The comparison function needs to meet the following conditions:

  1. If the first parameter is less than the second parameter, a negative number is returned.
  2. If the two parameters are equal, zero is returned.
  3. If the first parameter is greater than the second parameter, a positive number is returned.

Void* type pointers are universal pointers that can accept any type of address

Function use case:

(1) Sorting of int type array

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//Sort integer array
int my_cmp(const void* a, const void* b)
{
return (*(int*)a - *(int*)b);
}

int main()
{
int num[3] = { 2,5,3 };
qsort(num, 3, sizeof(num[0]), my_cmp);
for (int i = 0; i < 3; i + + )
{
printf("%d ", num[i]);
}
return 0;
}

(2) Sorting of char arrays

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//Sort char array
int my_cmp(const void* a, const void* b)
{
return (*(char*)a - *(char*)b);
}

int main()
{
char num[] = { 'a','c','b' };
qsort(num, 3, sizeof(num[0]), my_cmp);
for (int i = 0; i < 3; i + + )
{
printf("%c ", num[i]);
}
return 0;
}

(3) Sorting of floating-point arrays

Note:Due to precision issues with floating point numbers, rounding errors may occur when represented internally by the computer. Therefore, if simple modifications are made based on the above, it will result in The situation of 3.14>3.20 happened, so it needs to be more rigorous

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//Sort floating point array
int my_cmp(const void* a, const void* b)
{
    double num1 = *(const double*)a;
    double num2 = *(const double*)b;

    if (num1 < num2)
        return -1;
    else if (num1 > num2)
        return 1;

    return 0; // Equality case
}

int main()
{
    double arr[] = { 3.14, 5.16, 3.20 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    qsort(arr, sz, sizeof(arr[0]), my_cmp);

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

(4) Sorting of structure types

Also includes sorting string arrays

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

//Swap positions by single byte
void Swap(char* buf1, char* buf2, size_t width)
{
int i = 0;
for (i = 0; i < width; i + + )
{
char tmp = *buf1;
*buf1 = *buf2;
*buf2 = tmp;
buf1 + + ;
buf2 + + ;
}
}

//Simulate qsort function
void bubble_sort(void* base, size_t sz, size_t 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)
{
Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
}
}
}
}

//Declare the structure (will write about it later, use it now)
structStu{
char name[20];
int age;
};

//Calculate the relationship between the age difference and 0
int cmp_stu_by_age(const void* e1, const void* e2)
{
return ((struct Stu*)e1)->age - ((struct Stu*)e2)->age;
}

//Use the strcmp function to compare the ASCII codes of characters
int cmp_stu_by_name(const void* e1, const void* e2)
{
return strcmp(((struct Stu*)e1)->name, ((struct Stu*)e2)->name);
}

//Test bubble_sort sorting structure data
void test2()
{
    struct Stu arr2[] = { {"zhansgan", 15}, {"lisi", 35},{"wangwu", 32} };
    int sz = sizeof(arr2) / sizeof(arr2[0]); //sz = 3, sizeof(arr2[0]) = 24
    //bubble_sort(arr2, sz, sizeof(arr2[0]), cmp_stu_by_age);
    bubble_sort(arr2, sz, sizeof(arr2[0]), cmp_stu_by_name);
}

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

For the sorting results of names:

Sorting results for age:

(5) Imitate the function of qsort to implement a universal bubble sort

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void Swap(char* buf1, char* buf2, size_t width)
{
int i = 0;
for (i = 0; i < width; i + + )
{
char tmp = *buf1;
*buf1 = *buf2;
*buf2 = tmp;
buf1 + + ;
buf2 + + ;
}

}

void bubble_sort(void* base, size_t sz, size_t 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)
{
Swap((char*)base + j * width, (char*)base + (j + 1) * width, width);
}
}
}
}

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]);
}
printf("\
");
}

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

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

~over~

The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. Algorithm skill tree Home page Overview 57421 people are learning the system