Определение функции сравнения

Решение.

Использование стандартной функции qsort

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

#include <stdlib.h>
void qsort(void* base, size_t nmemb, size_t size,
int (* compar)(const void* p1, const void*p2));

Здесь:

· base – указатель на первый элемент массива, содержащего сортируемые элементы,

· nmemb – количество сортируемых элементов,

· size – размер памяти, занимаемый одним элементом,

· compar – указатель на функцию, выполняющую сравнение сортируемых элементов.

Остановимся отдельно на функции, которая должна выполнять сравнение. Эта функция должна получать два параметра, которые указывают на объекты, подлежащие сравнению. Эта функция должна возвращать отрицательное число, если первый элемент меньше второго, положительное число, если первое элемент больше второго и, наконец, возвращает нулевое число – в случае равентсва сравниваемых элементов.

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

Рассмотрим пример использования функции qsort().

Постановка задачи. Сортировать в порядке возрастания элементы массива ar. Массив состоит из n элементов типа double.

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

int compare(const void* p1,const void* p1);

Для упрощения алгоритма введем две вспомогательные переменные x1 и x2 типа double. Эти переменные должны представлять в разрабатываемой функции сравниваемые элементы массива. Для нахождения значений этих переменных необходимо нетипизированные указатели p1 и p2 преобразавать к указателям на тип сравниваемых элеменов (double*), а затем выполнить их разыменование. В результате можно получить следующее определение функции.

int compare(const void* p1, const void* p2)
{
double x1 = *(double*)p1;
double x2 = *(double*)p2;
if(x1 < x2)
return -1;
if(x1 > x2)
return 1;
return 0;
}

Клиентский код.

int compare(const void* p1, const void* p2);
int main(void)
{

double ar[] = {25, 4, 8, -1};
int n = sizeof(ar) / sizeof(*ar);
qsort(ar, n, sizeof(*ar), compar);
for(int i = 0; i < n; i++)
printf(“%0.4g”, ar[i]);
return 0;
}

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

-1

Дата добавления: 2014-01-06