Laboratory 10 – Generic Sorting with qsort and Function Pointers

Laboratory Overview

What is new in this laboratory.

In Laboratory 8, you wrote sorting functions for arrays of long. In Laboratory 9, you adapted the same algorithms to arrays of strings. In this laboratory, you will learn how the standard C library solves this problem: instead of writing a separate sorting function for every type, qsort receives a pointer to a comparison function.

Main idea of this lab:

type-specific sorting → comparison function → function pointer → qsort → generic bsort/isort

The final goal is not to submit many small programs. The final goal is to prepare three groups of sorting programs. Each group sorts one kind of data using three possible algorithms: qsort, generic bsort, and generic isort.

Learning Outcomes

explain the purpose of qsort,
write comparison functions compatible with qsort,
understand why qsort uses const void *,
explain the idea of a function pointer,
convert type-specific sorting functions into generic sorting functions,
extend array.h and libarray.a with generic bsort and isort,
sort dynamic arrays of long values, strings, and dates,
test the same data type with three algorithms: qsort, bsort, and isort.

Submission Rules

Prepare all variants. The teacher chooses what is checked.

This laboratory has three assessed task groups: ex34, ex35, and ex36. For each task group, prepare all three algorithm variants. During assessment, the teacher may choose one variant from each group.

Task group	Data type	Required files
`ex34`	dynamic array of `long`	`ex34_qsort_long.c`, `ex34_bsort_long.c`, `ex34_isort_long.c`
`ex35`	dynamic array of strings	`ex35_qsort_strings.c`, `ex35_bsort_strings.c`, `ex35_isort_strings.c`
`ex36`	dynamic array of `DAY` structures	`ex36_qsort_dates.c`, `ex36_bsort_dates.c`, `ex36_isort_dates.c`

Example assessment: the teacher may ask you to show ex34_isort_long.c, ex35_bsort_strings.c, and ex36_qsort_dates.c. Therefore, all variants must be prepared and tested.

How this laboratory continues Lab 8 and Lab 9

The sorting algorithm becomes independent of the element type.

Previous labs	Laboratory 10
`bsort_l`, `isort_l`	generic `bsort`, `isort`
`bsort_s`, `isort_s`	same generic functions, different comparison function
direct comparison: `a > b`	comparison function: `compar(a, b)`
known element type	`void *` and element size
Lab 6 date structure: `DAY`	sorting dynamic arrays of dates using a comparison function

Task 0 — Reminder and preparation

Shown. Log in to the AGH server and prepare the working directory.

Step 1 — Log in to the AGH UNIX server

ssh your_login@student.agh.edu.pl

Step 2 — Go to the course directory

cd ~/I2PL

Step 3 — Create the directory for Laboratory 10

mkdir lab10
cd lab10

Step 4 — General rules

Work only in ~/I2PL/lab10.
Reuse array.h and libarray.a from previous laboratories.
Compile with warnings enabled.
Check all dynamic allocations.
Free all allocated memory.

gcc -Wall program.c -o program

Task 1 — Understand `qsort` and comparison functions

Auxiliary task. Study the interface of qsort before using it.

Step 1 — The declaration of `qsort`

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

Step 2 — Meaning of the parameters

Parameter	Meaning
`base`	address of the first element of the array
`nmemb`	number of elements
`size`	size of one element in bytes
`compar`	pointer to a function comparing two elements

Step 3 — What the comparison function returns

negative value — first element should go before the second one,
zero — elements are considered equal,
positive value — first element should go after the second one.

A function pointer allows a function to receive another function as an argument. Here, qsort receives the comparison rule from your program.

Task 2 — Write comparison functions

Auxiliary task. These functions are reused by qsort, bsort, and isort.

Step 1 — Comparator for `long`

Start with a complete comparator for long. This is the basic pattern used later for other data types.

int compare_long(const void *a, const void *b) {
    const long *pa = a;
    const long *pb = b;

    if (*pa < *pb) {
        return -1;
    }

    if (*pa > *pb) {
        return 1;
    }

    return 0;
}

Do not use return *pa - *pb;. For very large or very small values, the subtraction may overflow the range of long.

Step 2 — Comparator for strings

The array element is char *. Because the sorting function receives a pointer to an element, the comparator receives a pointer to char *.

int compare_string(const void *a, const void *b) {
    const char * const *pa = a;
    const char * const *pb = b;

    /* Return the result of comparing the two strings. */
}

Hint

Use strcmp. The actual strings are available as *pa and *pb.

Step 3 — Comparator for dates

Reuse the DAY structure from Laboratory 6. Compare dates chronologically: first by year, then by month, then by day.

int compare_day(const void *a, const void *b) {
    const DAY *da = a;
    const DAY *db = b;

    /* Compare years first. */
    /* If years are equal, compare months. */
    /* If months are equal, compare days. */
}

Hint

A comparator does not need the exact difference between two values. It only needs to return a negative value, zero, or a positive value.

Task 3 — Prepare generic sorting declarations

Library part. Add declarations of generic sorting functions to array.h.

Step 1 — Add declarations to `array.h`

void bsort(void *base, int size, size_t width,
           int (*compar)(const void *, const void *));

void isort(void *base, int size, size_t width,
           int (*compar)(const void *, const void *));

This interface is intentionally similar to qsort. The parameter width tells the function how many bytes one array element has.

Task 4 — Implement generic bubble sort

Library part. Convert bsort_l and bsort_s into one generic bsort.

Step 1 — Create the file

nano bsort.c

Step 2 — Use byte-level pointer arithmetic

char *array = base;

Pointer arithmetic on char * moves byte by byte. This allows you to compute the address of element i as array + i * width.

Step 3 — Swap two elements of unknown type

Since the element type is unknown, you cannot use a normal typed temporary variable. A beginner-friendly solution is to swap byte by byte.

static void swap_bytes(void *a, void *b, size_t width) {
    char *pa = a;
    char *pb = b;

    for (size_t i = 0; i < width; i++) {
        char tmp = pa[i];
        pa[i] = pb[i];
        pb[i] = tmp;
    }
}

Step 4 — Implement `bsort`

#include <stddef.h>
#include "array.h"

static void swap_bytes(void *a, void *b, size_t width) {
    char *pa = a;
    char *pb = b;

    for (size_t i = 0; i < width; i++) {
        char tmp = pa[i];
        pa[i] = pb[i];
        pb[i] = tmp;
    }
}

void bsort(void *base, int size, size_t width,
           int (*compar)(const void *, const void *)) {

    /* Implement generic bubble sort here. */

}

Hints:

Convert base to char *.
The address of element i is array + i * width.
Use compar(a, b) instead of direct comparison.
Use swap_bytes to exchange two elements.
The loop structure is the same as in ordinary bubble sort.

Task 5 — Implement generic insertion sort

Library part. Convert isort_l and isort_s into one generic isort.

Step 1 — Create the file

nano isort.c

Step 2 — Use temporary storage for one element

Insertion sort temporarily stores one element while shifting other elements. For a generic function, allocate a temporary byte buffer of length width.

void *value = malloc(width);

Step 3 — Implement `isort`

#include <stdlib.h>
#include <string.h>
#include "array.h"

void isort(void *base, int size, size_t width,
           int (*compar)(const void *, const void *)) {
    char *array = base;
    void *value = malloc(width);

    if (value == NULL) {
        return;
    }

    /* Implement generic insertion sort here. */

    free(value);
}

Hints:

Use value as temporary storage for one element.
Copy elements with memcpy, because the real type is unknown.
Shift elements while compar(previous, value) > 0.
After shifting, copy value into the correct position.
Do not forget to release the temporary buffer with free(value).

Task 6 — Build the library

Library part. Add bsort.o and isort.o to libarray.a.

Step 1 — Compile the new files

gcc -Wall -c bsort.c
gcc -Wall -c isort.c

Step 2 — Rebuild the library

ar rcs libarray.a print_l.o randomize_l.o statistics_l.o bsort_l.o isort_l.o bsort_s.o isort_s.o bsort.o isort.o

If you no longer need the old type-specific functions, you may omit bsort_l.o, isort_l.o, bsort_s.o, and isort_s.o. For comparison and testing, keeping them in the library is convenient.

Task 7 — Assessed group `ex34`: sort a dynamic array of `long`

Assessed task group. Prepare all three algorithm variants.

Required files

ex34_qsort_long.c
ex34_bsort_long.c
ex34_isort_long.c

Program requirements

Ask the user for the number of elements.
Ask the user for the random range: minimum and maximum value.
Dynamically allocate an array of long.
Fill the array with random values from the selected range.
Display the array before sorting.
Sort the array using the algorithm named in the file name.
Display the array after sorting.
Release all allocated memory.

Sorting calls

qsort(array, size, sizeof(*array), compare_long);
bsort(array, size, sizeof(*array), compare_long);
isort(array, size, sizeof(*array), compare_long);

The three files should have the same input/output behaviour. Only the sorting function changes.

Task 8 — Assessed group `ex35`: sort a dynamic array of strings

Assessed task group. Prepare all three algorithm variants.

Required files

ex35_qsort_strings.c
ex35_bsort_strings.c
ex35_isort_strings.c

Program requirements

Ask the user for the number of strings.
Dynamically allocate an array of pointers.
Read strings from the user.
Display the strings before sorting.
Sort the array using the algorithm named in the file name.
Display the strings after sorting.
Release every string and then release the outer array.

Important detail

Sorting an array of strings reorders the pointers stored in the array. The string contents stay in their allocated memory blocks.

Sorting calls

qsort(array, size, sizeof(*array), compare_string);
bsort(array, size, sizeof(*array), compare_string);
isort(array, size, sizeof(*array), compare_string);

Task 9 — Assessed group `ex36`: sort a dynamic array of dates

Assessed task group. Prepare all three algorithm variants.

Required files

ex36_qsort_dates.c
ex36_bsort_dates.c
ex36_isort_dates.c

Use the date type from Laboratory 6

If your date declarations are already stored in days.h, include that header. Otherwise, use the same structure as in Laboratory 6.

typedef struct {
    int day;
    int month;
    int year;
} DAY;

Program requirements

Ask the user for the number of dates.
Dynamically allocate an array of DAY objects.
Read dates from the user in the format day month year.
Display the dates before sorting.
Sort dates chronologically using the algorithm named in the file name.
Display the dates after sorting.
Release all allocated memory.

Example input and output format

5 5 2026
31 10 1972
2 11 1997

printf("%02d.%02d.%04d\n", dates[i].day, dates[i].month, dates[i].year);

Sorting calls

qsort(dates, size, sizeof(*dates), compare_day);
bsort(dates, size, sizeof(*dates), compare_day);
isort(dates, size, sizeof(*dates), compare_day);

Test Questions — Review before the next class

Try to answer these questions before opening the answers.

1. What does the last parameter of qsort represent?

It is a pointer to a comparison function. The sorting algorithm calls this function whenever it needs to decide which of two elements should come first.

2. Why does qsort receive void * instead of long * or char **?

Because qsort is generic. It does not know the real type of the array elements. It works on raw memory and uses the element size plus the comparison function to process the array.

3. What does sizeof(*array) mean in a call to qsort?

It gives the size of one array element. For long *array, it is the size of one long. For char **array, it is the size of one char * pointer.

4. Why is return *pa - *pb; not recommended in compare_long?

The subtraction may overflow the range of long. The comparison function does not need the exact difference; it only needs to return a negative value, zero, or a positive value.

5. Why does the string comparator use strcmp(*pa, *pb)?

The array element is char *. Since the sorting function passes a pointer to an element, the comparator receives a pointer to char *. Therefore, after conversion, we use *pa and *pb as the actual strings passed to strcmp.

6. When sorting an array of strings, are whole strings copied?

No. The array stores pointers to strings. Sorting reorders the pointers stored in the array. The actual string contents remain in their allocated memory blocks.

7. Why does generic bsort use char * internally?

Pointer arithmetic on char * moves byte by byte. This allows the function to compute the address of element i as array + i * width.

8. Why does generic isort need a temporary buffer?

Insertion sort temporarily saves one element before shifting other elements. Since the type is unknown, the function allocates a buffer of width bytes and copies the element using memcpy.

9. How should dates be compared in compare_day?

First compare years. If they are equal, compare months. If months are also equal, compare days. This gives chronological order.

10. What is the most important idea of this laboratory?

The sorting algorithm can be independent of the data type. The algorithm works on raw memory, while the comparison function knows how to interpret the actual elements.

Checklist before submission

array.h contains declarations of generic bsort and isort,
bsort.c implements generic bubble sort,
isort.c implements generic insertion sort,
libarray.a contains bsort.o and isort.o,
all three variants of ex34 are prepared and tested,
all three variants of ex35 are prepared and tested,
all three variants of ex36 are prepared and tested,
all programs display data before and after sorting,
all dynamically allocated memory is released correctly.

Quick Summary

Main topic: generic sorting
Standard function: qsort
Key concept: function pointer
Generic data: void * + width
Library: generic bsort and isort
Assessed groups: ex34, ex35, ex36

Assessed Files

ex34_qsort_long.c
ex34_bsort_long.c
ex34_isort_long.c

ex35_qsort_strings.c
ex35_bsort_strings.c
ex35_isort_strings.c

ex36_qsort_dates.c
ex36_bsort_dates.c
ex36_isort_dates.c

Library Files

array.h
bsort.c
isort.c
bsort.o
isort.o
libarray.a

Recommended Compile Sequence

gcc -Wall -c bsort.c
gcc -Wall -c isort.c

ar rcs libarray.a print_l.o randomize_l.o statistics_l.o bsort_l.o isort_l.o bsort_s.o isort_s.o bsort.o isort.o

gcc -Wall ex34_qsort_long.c -L. -larray -o ex34_qsort_long
gcc -Wall ex34_bsort_long.c -L. -larray -o ex34_bsort_long
gcc -Wall ex34_isort_long.c -L. -larray -o ex34_isort_long

gcc -Wall ex35_qsort_strings.c -L. -larray -o ex35_qsort_strings
gcc -Wall ex35_bsort_strings.c -L. -larray -o ex35_bsort_strings
gcc -Wall ex35_isort_strings.c -L. -larray -o ex35_isort_strings

gcc -Wall ex36_qsort_dates.c days.c -L. -larray -o ex36_qsort_dates
gcc -Wall ex36_bsort_dates.c days.c -L. -larray -o ex36_bsort_dates
gcc -Wall ex36_isort_dates.c days.c -L. -larray -o ex36_isort_dates

Important Pattern

int compare_long(const void *a, const void *b) {
    const long *pa = a;
    const long *pb = b;

    if (*pa < *pb) {
        return -1;
    }

    if (*pa > *pb) {
        return 1;
    }

    return 0;
}

A comparison function receives two addresses and returns negative, zero, or positive. Do not rely on subtracting values.

Common Mistakes

forgetting that sorting functions pass pointers to elements
using the wrong sizeof value
forgetting that for char *array[], the comparator receives pointers to elements
copying bytes with overlapping memory in the wrong direction
forgetting to include <stdlib.h>, <string.h>, or <stddef.h>
comparing only the year when sorting dates and forgetting month/day tie-breakers
testing only one algorithm variant from a task group

Laboratory Overview

Learning Outcomes

Submission Rules

How this laboratory continues Lab 8 and Lab 9

Task 0 — Reminder and preparation

Step 1 — Log in to the AGH UNIX server

Step 2 — Go to the course directory

Step 3 — Create the directory for Laboratory 10

Step 4 — General rules

Task 1 — Understand qsort and comparison functions

Step 1 — The declaration of qsort

Step 2 — Meaning of the parameters

Step 3 — What the comparison function returns

Task 2 — Write comparison functions

Step 1 — Comparator for long

Step 2 — Comparator for strings

Step 3 — Comparator for dates

Task 3 — Prepare generic sorting declarations

Step 1 — Add declarations to array.h

Task 4 — Implement generic bubble sort

Step 1 — Create the file

Step 2 — Use byte-level pointer arithmetic

Step 3 — Swap two elements of unknown type

Step 4 — Implement bsort

Task 5 — Implement generic insertion sort

Step 1 — Create the file

Step 2 — Use temporary storage for one element

Step 3 — Implement isort

Task 6 — Build the library

Step 1 — Compile the new files

Step 2 — Rebuild the library

Task 7 — Assessed group ex34: sort a dynamic array of long

Required files

Program requirements

Sorting calls

Task 8 — Assessed group ex35: sort a dynamic array of strings

Required files

Program requirements

Important detail

Sorting calls

Task 9 — Assessed group ex36: sort a dynamic array of dates

Required files

Use the date type from Laboratory 6

Program requirements

Example input and output format

Sorting calls

Test Questions — Review before the next class

Checklist before submission

Task 1 — Understand `qsort` and comparison functions

Step 1 — The declaration of `qsort`

Step 1 — Comparator for `long`

Step 1 — Add declarations to `array.h`

Step 4 — Implement `bsort`

Step 3 — Implement `isort`

Task 7 — Assessed group `ex34`: sort a dynamic array of `long`

Task 8 — Assessed group `ex35`: sort a dynamic array of strings

Task 9 — Assessed group `ex36`: sort a dynamic array of dates