qsort() and bsearch() Functions in C

What is qsort() in C?

The qsort() function is a standard library function in C that implements the quicksort algorithm to sort arrays. It’s defined in the <stdlib.h> header file.

Syntax of qsort()

void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void *));

• base: Pointer to the first element of the array.
• nitems: Total number of elements in the array.
• size: Size of each element in bytes.
• compar: A pointer to a comparison function that determines the order.

Comparison Function in C: What It Returns

• Returns a negative number if the first item is less than the second.
• Zero if the arguments are equal.
• Positive value if the first item is greater than the second.

qsort() Example

#include <stdio.h>
#include <stdlib.h>
 
int compareMarks(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}
 
int main() {
    int quizMarks[] = {85, 78, 92, 60, 74};
    int n = sizeof(quizMarks)/sizeof(quizMarks[0]);
 
    qsort(quizMarks, n, sizeof(int), compareMarks);
 
    printf("Sorted Marks:\n");
    for (int i = 0; i < n; i++)
        printf("%d ", quizMarks[i]);
 
    return 0;
}

Output:

Sorted Marks:
60 74 78 85 92

• The program starts by including two header files: <stdio.h> for input and output, and <stdlib.h> for using the qsort() function.
• It defines a function called compareMarks() that compares two numbers and returns their difference.
• This helps qsort() know how to sort the values. The array quizMarks stores five quiz scores.
• The qsort() function sorts the marks in increasing order using the compare function.
• After sorting, a loop prints each mark one by one.

What is bsearch() in C?

The bsearch() function performs a binary search on a sorted array. It’s defined in the <stdlib.h> header file.

Syntax of bsearch():

void *bsearch(const void *key, const void *base,
              size_t nitems, size_t size,
              int (*compar)(const void *, const void *));

• key: Pointer to the item to search for.
• base: Pointer to the start of the array.
• nitems: Number of elements in the array.
• size: Size of each element in bytes.
• compar: A comparison function similar to that used in qsort().

Comparison Function:

Similar to qsort(), the comparison function should return:

• Returns negative value if the first item is less than the second.
• Zero if the items are equal.
• Positive value if the first item is greater than the second.

bsearch() Example

#include <stdio.h>
#include <stdlib.h>
 
int compareMarks(const void *a, const void *b)
{
    return (*(int *)a - *(int *)b);
}
 
int main()
{
    // Must be sorted
    int certificationScores[] = {60, 74, 78, 85, 92};
    int key = 85;
    int *found;
 
    found = (int *)bsearch(&key, certificationScores,
                           5, sizeof(int), compareMarks);
 
    if (found)
        printf("Sanfoundry Certification Score %d Found\n", *found);
    else
        printf("Score not found\n");
 
    return 0;
}

Output:

Sanfoundry Certification Score 85 Found

• The program includes <stdio.h> and <stdlib.h> to use input/output and the bsearch() function.
• It defines a compareMarks() function to compare two integers for searching.
• An array certificationScores stores five sorted scores.
• The program uses bsearch() to find the value 85 in the array.
• If found, it prints the score; if not, it shows a “Score not found” message.

Best Practices

• Sorting Before Searching: Always sort your array using qsort() before performing a binary search with bsearch().
• Consistent Comparison Functions: Use the same comparison function for both qsort() and bsearch() to ensure consistency.
• Handling Complex Data: For arrays of structures, customize the comparison function to compare specific fields.

Sanfoundry Global Education & Learning Series – 1000 C Tutorials.