Рубрики

Компараторная функция qsort () в C

Стандартная библиотека 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 comparator(const void* p1, const void* p2);
Return value meaning
0 The element pointed by p1 goes after the element pointed by p2

Source: http://www.cplusplus.com/reference/cstdlib/qsort/

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

struct Student

{

    int age, marks;

    char name[20];

};

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

int comparator(const void *p, const void *q) 

{

    int l = ((struct Student *)p)->marks;

    int r = ((struct Student *)q)->marks; 

    return (l - r);

}

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

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

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

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

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

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

  
// Эта функция используется в qsort для определения относительного порядка
// элементов по адресам p и q.

int comparator(const void *p, const void *q)

{

    // Получить значения по заданным адресам

    int l = *(const int *)p;

    int r = *(const int *)q;

  

    // оба нечетные, сначала поместите большее из двух.

    if ((l&1) && (r&1))

        return (r-l);

  

    // оба четных, сначала поместите меньшее из двух

    if ( !(l&1) && !(r&1) )

        return (l-r);

  

    // Я чётный, сначала ставим r

    if (!(l&1))

        return 1;

  

    // l странно, сначала ставим l

    return -1;

}

  
// Вспомогательная функция для печати массива

void printArr(int arr[], int n)

{

    int i;

    for (i = 0; i < n; ++i)

        printf("%d ", arr[i]);

}

  
// Программа драйвера для проверки вышеуказанной функции

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\n");

    printArr(arr, size);

  

    return 0;

}

Выход:

Output array is
9 7 5 3 1 2 4 6 8

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

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

Рекомендуемые посты:

Компараторная функция qsort () в C

0.00 (0%) 0 votes