Функция сравнения qsort () в C

Опубликовано: 1 Января, 2022

Стандартная библиотека C предоставляет qsort (), который можно использовать для сортировки массива. Как следует из названия, функция использует алгоритм QuickSort для сортировки данного массива. Ниже приведен прототип qsort ().

 void qsort ( void * base, size_t num, size_t size,
            int (*comparator)( const void *, const void *)); 

Ключевым моментом в qsort () является компаратор функции компаратора . Функция компаратора принимает два аргумента и содержит логику для определения их относительного порядка в отсортированном выводе. Идея состоит в том, чтобы обеспечить гибкость, чтобы qsort () можно было использовать для любого типа (включая типы, определенные пользователем) и можно было использовать для получения любого желаемого порядка (увеличения, уменьшения или любого другого).

Функция компаратора принимает в качестве аргументов два указателя (оба приводятся к типу const void *) и определяет порядок элементов путем возврата (стабильным и транзитивным способом

int компаратор (const void * p1, const void * p2);
Значение возвращаемого значения
<0 элемент, на который указывает p1, идет до p2
0 эквивалентно p2
> 0 Элемент, на который указывает p1, идет после элемента, указанного p2

Источник: http://www.cplusplus.com/reference/cstdlib/qsort/

Например, пусть есть массив студентов, где следующий - тип студента.

 struct Student
 {
    int age, marks;
    char name[20];
 };

Допустим, нам нужно отсортировать студентов по оценкам в порядке возрастания. Функция компаратора будет выглядеть так:

См. Следующие сообщения для получения дополнительных примеров использования qsort ().
Учитывая последовательность слов, выведите все анаграммы вместе
Проблема с укладкой ящиков
Ближайшая пара точек

Ниже приводится интересная проблема, которую легко решить с помощью qsort () и функции компаратора.
Учитывая массив целых чисел, отсортируйте его таким образом, чтобы нечетные числа появлялись первыми, а четные - позже. Нечетные числа должны быть отсортированы в порядке убывания, а четные числа должны быть отсортированы в порядке возрастания.

Простой подход состоит в том, чтобы сначала изменить входной массив таким образом, чтобы четные и нечетные числа были разделены, а затем применить некоторый алгоритм сортировки к обеим частям (нечетным и четным) по отдельности.

Однако существует интересный подход с небольшой модификацией функции компаратора Quick Sort. Идея состоит в том, чтобы написать функцию компаратора, которая принимает в качестве аргументов два адреса p и q. Пусть l и r - числа, указанные p и q. Функция использует следующую логику:
1) Если оба (l и r) нечетные, сначала ставьте большее из двух.
2) Если оба (l и r) четные, сначала поставьте меньшее из двух.
3) Если один из них четный, а другой нечетный, сначала укажите нечетное число.

Ниже приведена реализация описанного выше подхода на языке C.

 #include <stdio.h>
 #include <stdlib.h>
 
// This function is used in qsort to decide the relative order
 // of elements at addresses p and q.
 int comparator( const void *p, const void *q)
 {
    // Get the values at given addresses
    int l = *( const int *)p;
    int r = *( const int *)q;
 
    // both odd, put the greater of two first.
    if ((l&1) && (r&1))
        return (rl);
 
    // both even, put the smaller of two first
    if ( !(l&1) && !(r&1) )
        return (lr);
 
    // l is even, put r first
    if (!(l&1))
        return 1;
 
    // l is odd, put l first
    return -1;
 }
 
// A utility function to print an array
 void printArr( int arr[], int n)
 {
    int i;
    for (i = 0; i < n; ++i)
        printf ( "%d " , arr[i]);
 }
 
// Driver program to test above function
 int main()
 {
    int arr[] = {1, 6, 5, 2, 3, 9, 4, 7, 8};
 
    int size = sizeof (arr) / sizeof (arr[0]);
    qsort (( void *)arr, size, sizeof (arr[0]), comparator);
 
    printf ( "Output array is
" );
    printArr(arr, size);
 
    return 0;
 }

Выход:

 Выходной массив
9 7 5 3 1 2 4 6 8

Упражнение:
Дан массив целых чисел, отсортируйте его альтернативным способом. Альтернативный способ означает, что элементы с четными индексами сортируются отдельно, а элементы с нечетными индексами сортируются отдельно.

Эта статья составлена Аашишем Барнвалом. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Хотите учиться на лучших видео и практических задачах, ознакомьтесь с Базовым курсом C для базового и продвинутого C.

C++ C

Функция сравнения qsort () в C

РЕКОМЕНДУЕМЫЕ СТАТЬИ