QSort C: алгоритм быстрой сортировки в языке C

Функция qsort в языке программирования C

Функция qsort представлена в стандартной библиотеке C (stdlib.h) и используется для сортировки массивов. Она представляет собой быструю сортировку, которая работает на основе алгоритма разделения и завершается, когда вся последовательность отсортирована.

Прототип функции qsort

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*));

Где:

• base - указатель на начало массива, который нужно отсортировать.
• nitems - количество элементов в массиве.
• size - размер каждого элемента массива.
• compar - указатель на функцию-компаратор, которая сравнивает два элемента и возвращает значение, которое указывает их относительный порядок.

Проще говоря, функция qsort сравнивает пары элементов массива и меняет их местами до тех пор, пока весь массив не будет отсортирован. Для этого она использует указатель на пользовательскую функцию-компаратор, которая сравнивает два элемента и возвращает значение, указывающее их порядок.

Пример использования функции qsort

#include 
#include 

// Пример пользовательской функции-компаратора, сравнивающей два целых числа
int compare(const void *a, const void *b) {
    int num1 = *((int*)a);
    int num2 = *((int*)b);
    
    if (num1 < num2) return -1;
    if (num1 > num2) return 1;
    
    return 0;
}

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

    qsort(arr, n, sizeof(int), compare);

    printf("Отсортированный массив: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

В этом примере мы создали массив arr с неупорядоченными целочисленными значениями. Затем мы передали этот массив в функцию qsort, указав его размер и размер каждого элемента (в данном случае int). Также мы передали указатель на функцию compare, которая сравнивает два элемента массива типа int.

Результат выполнения программы будет выглядеть так:

Отсортированный массив: 1 2 3 4 5 6 7 8 9

Таким образом, функция qsort позволяет упорядочить массивы любого типа, используя пользовательскую функцию-компаратора для определения порядка сравнения элементов. Это мощный инструмент, который значительно облегчает сортировку массивов в языке программирования C.