используя функцию qsort ()

Question

Я студент, и я посмотрел эту функцию в книге.Работает как надо, но я не совсем понимаю внутреннюю работу sortFunction(), которая передается функции qsort().Если кто-то может объяснить это подробно, пожалуйста.Заранее спасибо.

#include<iostream>
#include<stdlib.h>

using namespace std;

//form of sort function required by qsort()
int sortFunction(const void *intOne,const void *intTwo);

const int tableSize = 10;

int main()
{
    int i, table[tableSize];

    //fill the table with values
    for(i = 0; i < tableSize; i++)
    {
        cout << "Enter value " << (i + 1) << " : ";
        cin >> table[i];
    }
    cout << "\n";

    //sort values
    qsort((void*)table, tableSize, sizeof(table[0]), sortFunction);

    //print the results
    for(i = 0; i < tableSize; i++)
    {
        cout << "Value " << (i + 1) << " : " << table[i] << endl;
    }

    cout << "\nDone\n";

    return 0;
}

int sortFunction(const void *a, const void *b)
{
    int intOne = *((int*)a);
    int intTwo = *((int*)b);

    if (intOne < intTwo)
    {
        return -1;
    }
    if (intOne == intTwo)
    {
        return 0;
    }

    return 1;    
}

Answer 1

Если вы посмотрите на фактический вызов qsort ...

qsort((void*)table, tableSize, sizeof table[0], sortFunction); 

... вы увидите, что это обеспечивает:

• a void* адрес и размер (в байтах) всего массива данных для сортировки, затем
• размер одного элемента данных в этом массиве, тогда
• указатель на функцию сравнения «sortFunction».

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

int sortFunction(const void *a, const void *b)   
{   
    int intOne = *((int*)a);   
    int intTwo = *((int*)b);   

... и qsort вызывает это, вы получаете два указателя - они обращаются к адресам памяти, но когда qsort вызывает sortFunction, эти void указатели все еще ничего не сообщают об элементе данных напечатайте , поскольку qsort не имеет никакой проницательности. Последние две строки кода выше, где вы - программист, координирующий вызов qsort, - повторно применяете знания, которые у вас были все время о том, каков тип элемента данных: в данном случае это int s, поэтому вы преобразуете каждый void* в int* (используя (int*)a), а затем разыменовываете значение int*, чтобы получить int по адресу памяти a. Аналогично для b. При этом вы восстановили два числа, которые были там , как числа . Затем задание sortFunction состоит в том, чтобы указать, как они должны быть упорядочены после завершения сортировки. Чтобы указать, что a должно быть первым, sortFunction может вернуть любое отрицательное значение (например, -1); если они эквивалентны, return 0;, и если b должно быть первым, вернуть любое положительное значение (например, 1). qsort() получает эту информацию и использует ее, чтобы понять, как перемешивать элементы данных при сортировке.

FWIW, C позволяет вам выразить это более кратко, как ...

return intOne < intTwo ? -1 :
       intOne == intTwo ? 0 :
       1;

... или (быстрее, но полагаясь на логические результаты сравнения равные 0 и 1, что может запутать некоторых программистов, читающих ваш код) ...

return (intOne > intTwo) - (intOne < intTwo);

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

return intOne - intTwo;

Answer 2

sortFunction фактически не выполняет сортировку, она используется в качестве функции сравнения, чтобы определить, должен ли один элемент предшествовать другому в отсортированном списке.

Answer 3

То, что вы назвали «sortFunction», обычно называется компаратором.Он в основном сообщает общий код сортировки в qsort(), сравнивают ли два элемента в сортируемом массиве равные (0), или сортирует первый аргумент перед вторым (<0), или сортирует первый аргумент после второго (> 0).

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

Answer 4

Посмотрите, поможет ли эта статья. В нем рассказывается о том, как используются функции обратного вызова и как такие функции, как qsort, могут быть реализованы с использованием функций обратного вызова. http://learnwithtechies.com/index.php/component/content/article/4-c/18-callback-functions-in-c-can-be-very-handy

Answer 5

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