Function qsort is part of the C Standard Library. It is a general-purpose sorting function that sorts an array using a variant of the Quicksort algorithm. (We will not cover Quicksort in this course, but you should see it in another course.) You should include header file <cstdlib> to use qsort.
To use qsort to sort an array E of N edges by weight, first define a type,
typedef int (*QSORT_COMPARE_TYPE)(const void*, const void*);and define a function compareEdges that compares edges, as follows.
int compareEdges(const Edge* A, const Edge* B)
{
return A->weight - B->weight;
}
Then use the following statement to sort E.
qsort(E, N, sizeof(Edge), (QSORT_COMPARE_TYPE) compareEdges);Parameter N tells qsort how many edges there are. It should be the logical size of E. The compiler replaces sizeof(Edge) with the number of bytes that each edge occupies so that qsort knows how large the things are.
Notice that the fourth parameter of qsort is a function, compareEdges. C++ allows you to pass a function as a parameter to another function. You do not run the function yourself; qsort will run it for you, many times, since it needs to do many comparisons to sort the array. You are lending compareEdges to qsort.